当前位置:首页 >> 学科竞赛 >>

第一讲 高精度运算


第一讲 高精度运算
2014.07.16

1

引例:A+B Problem 背景 for beginngers,特设此题,^_^ 描述 输入两个自然数,输出他们的和 格式

输入格式
输出格式

两个自然数x和y (0<=x,y<=32767)
一个数,

即x和y的和

样例
样例输入 123 500

样例输出

623
2

Free Pascal Code program Plus; var a,b:longint; begin readln(a,b); writeln(a+b); end. C Code #include <stdio.h> int main(){ int a,b; scanf(“%d %d”,&a,&b); printf(“%d\n”,a+b); return 0; }

C++ Code #include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; cout<<a+b<<endl; return 0; }

3

如果调整数据范围: 30% 0<=a,b<=10^15; 100% 0<=a,b<=10^500。

4

?高精度运算
? 在数值运算中,如果参与运算的数据或者运算结 果的范围超出了标准的数据类型(整数和实数) ,这种运算称为高精度运算。

5

8字节: long long 的最大值: 9223372036854775807 long long 的最小值:-9223372036854775808 unsigned long long 的最大值:18446744073709551615 Int64 的最大值: 9223372036854775807 int64 的最小值:-9223372036854775808 Qword 的最大值:18446744073709551615

整数最大:10^19 实数有效位:18-19位

6

内容:
1
2

高精度加法
高精度*单精度

7

?如:
? 1、求a+b的值,a和b的范围是[0..10250]。 ? 2、求200!=1*2*3*…*200。

8

?思想:
? 用数组来保存大数的每一位: …… a[7] a[6] a[5] a[4] a[3] a[2] a[1]

…… 1

4

1

5

9

2

6

9

…… 1 …… 0 …… 1

1 0 1

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

+

…… a[7] a[6] a[5] a[4] a[3] a[2] a[1] …… 0

+

0

b[5] b[4] b[3] b[2] b[1]

…… c[7] c[6] c[5] c[4] c[3] c[2] c[1]

10

1 . 大整数加法
? ? ? ? ? ? ? ? ? ? ? 编程实现:输入正整数a和b,输出a+b的值。0<a,b<=10500 【输入】 第一行:a 第二行:b 【输出】 a+b的和。 【样例输入】 6789 999 【样例输出】 7788
11

?(1).数的输入和保存:
? 字符串输入; ? S1=‘6789’ ? S2=‘999’

12

?(1).数的输入和保存:
? ? ? ? 字符串输入; S1=‘6789’ S2=‘999’ 数组保存;

la=length(s1) for i:= 1 to la do a[i]:=ord(s1[la+1-i])-48;

S1[1 S1[2 S1[3 S1[4 ] ] ] ] 6 7 8 9 a[4] a[3] a[2] a[1]

S2[1 S2[2 S2[3 ] ] ] 9 9 9 b[3] b[2] b[1]

13

?(2).加法运算:
a[4] a[3] a[2] a[1]

+ b[3] b[2] b[1]
= c[4] c[3] c[2] c[1]

14

?(2).加法运算:
a[4] a[3] a[2] a[1]

+ b[3] b[2] b[1]
= a[4] a[3] a[2] a[1]

15

?(2).加法运算:
a[4] a[3] a[2] a[1]

+ b[3] b[2] b[1]
= a[4] a[3] a[2] a[1] for i:=1 to len do begin a[i+1]:=a[i+1]+(a[i]+b[i]) div 10; a[i]:=(a[i]+b[i]) mod 10; end; if a[len+1]>0 then len:=len+1;
16

?(3).输出运算结果:
? 先输出高位: ? for i:=len downto 1 do write(c[i]);

17

?大整数加法的算法描述:
? ? ? ? ? ? 输入s1; // 第一个加数 输入s2; // 第二个加数 a[ ] s1; //第一个加数保存到数组a b[ ] s2; //第二个加数保存到数组b a[ ] a[ ]+b[ ]; // 把b的每一位加到a的相应的位上 输出a[ ]; // 从高位输出结果

18

2.斐波那契数列(Fibonacci)
? 斐波那契数列又因数学家列昂纳多·斐波那契以兔子 繁殖为例子而引入,故又称为“兔子数列”。 ? 问题: ? 正常情况下,兔子在出生两个月后,就有繁殖能力 ,1对兔子每个月能生出1对小兔子来。 ? 如果所有兔子都不死,那么12个月以后可以繁殖多 少对兔子?

1月

1对 1对 2对 3对 5对

成长
生出

2月 3月
4月

5月 6月

8对

月 数 对 数

1 1

2 1

3 2

4 3

5 5

6 8

7

8

9

10 11 12

13 21 34 55 89 144

? 斐波那契数列,又称黄金分割数列,指的是这样一 个数列: ? 1、1、2、3、5、8、13、21、…… ? 在数学上,斐波纳契数列以如下递归的方法定义: ? F[1]=1 ? F[2]=1 ? F[n]=F[n-2]+F[n-1] (n>=3,n∈N*)

求n个月以后共多少对兔子(n<=1200)?

23

?方法1
? ? ? ? ? readln(n); f[1]:=1; f[2]:=1; for i:=3 to n do f[i]:=f[i-2]+f[i-1]; writeln(f[n]);

24

?方法2:
? readln(n); ? a:=1; ? b:=1; ? for i:=3 to n do ? begin ? c:=a+b; ? a:=b; ? b:=c; ? end; ? writeln(c);
25

?高精度运算
? ? ? ? ? ? ? ? ? ? ? //a[],b[],c[] readln(n); a[1]:=1; a[0]:=1; b[1]:=1; b[0]:=1; for i:=3 to n do begin add; //c=a+b a:=b; b:=c; end; print; //输出结果数组c
26

? procedure add; ? begin ? k:=b[0]; ? for j:=1 to k do c[j]:=a[j]+b[j]; ? for j:=1 to k do ? begin ? c[j+1]:=c[j+1]+c[j] div 10; ? c[j]:=c[j] mod 10; ? end; ? if c[k+1]>0 then k:=k+1; ? c[0]:=k; ? end;
27

?一个有趣的问题:
? 现有长为144cm的铁丝,要截成n小段( n>2)。 ? 每段的长度不小于1cm。 ? 如果其中任意三小段都不能拼成三角形。 ? 则n的最大值为多少? ? 铁丝长度不超过100000。

3. 求1*2*3*…*n的值。(n<=1000) 高精度*单精度
? ? ? ? ? 如: 输入: 20 输出: 2432902008176640000

29

?算法描述:
? ? ? ? ? ? ? ? ? ? ? ? ? a[1]=1; a[0]=1;长度 for i=2 to n do k:=a[0]; for j=1 to k do a[j]:=a[j]*i; for j=1 to k do a[j+1]=a[j+1]+a[j] div 10; a[j]=a[j] mod 10; m=a[k+1]; while m>0 do inc(k); a[k]=m mod 10; m=m div 10; a[0]=k; 输出数组a
30

?高精度运算的优化(时间+空间):扩大进制
? ? ? ? ? ? ? 数组的每一位存4位: 10变为10000; 输出: a[i]div 1000 (a[i]div 100)mod 10 (a[i]div 10)mod 10 a[i]mod 10

31

?任务扩展:
? ? ? ? ? ? ? ? 输入 n 输出: 1!+2!+…+n!的值(n<=1000)。 输入: 5 输出: 153

32

4.高精度*高精度 c=a*b
? for i:=1 to la do ? for j:=1 to lb do ? begin ? c[i+j-1]:=c[i+j-1]+a[i]*b[j]; ? c[i+j]:=c[i+j]+c[i+j-1] div 10; ? c[i+j-1]:=c[i+j-1] mod 10; ? end; ? len:=la+lb; ? while (len>1) and (c[len]=0) do dec(len);

33


相关文章:
高精度运算讲稿
高精度运算讲稿_英语学习_外语学习_教育专区。第一讲 PASCAL 高精度运算程序所处理加工的各类数据都有相应的值域限定。一旦某类型的数据超出了规定的范 围, 运算结...
高精度运算练习题
高精度运算练习题 1.正整数加法 输入两个不超过 200 位的正整数,输出它们的和。 输入:第一行只有一个正整数:m 第二行只有一个正整数:n 输出:只有一行且只有...
第四讲 高精度计算
授课教师:滨海县实验小学仇大成 small_jiajia@163.com 第四讲 高精度计算 由于计算机具有运算速度快,计算精度高的特点,许多过去由人来完成的烦琐、复杂的 数学计算...
高精度运算
高精度运算_IT/计算机_专业资料。PASCAL 程序设计基本方法 第二讲 高精度运算(加法) 高精度运算(加法) 一、高精度加法运算学习中级本书上的 P180 页到 183 页...
高精度计算
高精度计算 模板 12页 1下载券 高精度计算c 3页 免费 第四讲 高精度计算 ...高精度计算朴素高精度由于待处理的数据超过了任何一种数据类型所能容纳的范围, ...
高精度运算(加减)
安阳一中信息学奥赛辅导资料 高精度计算(一) 一、 教学目标 ? ? 二、 了解...第 3 页共 7 页 安阳一中信息学奥赛辅导资料 【例 2】 高精度减法(a-b)...
高精度运算(C++)
乘法的计算过程 首先看一下单精度数乘高精度数的实现过程,如图六所示:初始化 ...其中乘数中的第 J 位与被乘数中的第 I 位相乘时,结果应该保存到结果的第 I...
高精度运算和简单优化方法(C语言)
高精度运算和简单优化方法(C语言)_IT/计算机_专业资料。高精度运算和简单优化方法...} //处理第一个加数,每九位划分后剩余的位数转化为一个 数 p=sa; for(i...
高精度运算及其应用
Jsoi2010 春季函授讲义(B2) Jsoi2010 春季函授讲义(B2) 1/13 高精度运算及其应用一,引言 利用计算机进行数值运算,经常会遇到数值太大,超出 Longint,int64 等...
高精度算法大全
对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了 高精度算法: 由于计算机输入计算结果的精度通常受到计算机的限制,如:在双精度方式 下,计算机...
更多相关标签:
高精度运算 | 高精度运算放大器 | c高精度运算 | java高精度运算 | 高精度乘法运算 | 重载运算符 高精度 | 高精度运算库 | 李丰吉特巴教学第一讲 |