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

第一讲 高精度运算


第一讲 高精度运算
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


相关文章:
第一讲小数运算技巧
第一讲 小数运算技巧 课前十分钟 1、18 和 24 的最大公约数是 最小公倍数是 ; 2、一个数由 6 个千万,3 个万,9 个百和 4 个一组成,这个数写作 3...
第一讲:整数的速算与巧算
戴氏教育 5 升 6 暑期奥数 第一讲:整数的速算与巧算在速算与巧算时要根据数的组成和算式的特点,善于发现规律,巧用运用性 质及运算定律,使计算简便。 1、...
第一讲分式的运算
第一讲分式的运算_数学_初中教育_教育专区。第一讲 分式的运算 (一) 、分式...各分母系数的最小公倍数; ②最简公分母的字母因式取各分母所有字母的最高次...
第一讲 四则运算
第一讲 四则运算(共 4 页) 1 C 语言程序设计 第一讲 四则运算 程序举例...④ double;g,h; /*定义为双精度实型量*/ 注:变量名要用小写字母表示(待...
第一讲速算巧算
第一讲 速算巧算(一)(在巧算方法里,蕴含着一种重要的解决问题的策略——转化问题 法。即将所给算式,根据运算定律和运算性质,改变它的运算顺序, 或凑整,从而...
第一讲:乘法简便运算
第一讲:乘法简便运算_数学_小学教育_教育专区。第一讲:小数乘法简便计算 知识目标: 1、应用乘法交换律和结合律进行简便运算。 2、应用乘法分配律进行简便运算。 ...
数学总复习第一讲集合概念及运算
数学总复习第一讲集合概念及运算_高一数学_数学_高中教育_教育专区。高一数学 第1 讲 集合的概念及运算【基础知识梳理】 1.集合的概念:某些指定的对象集在一起...
第一讲 定义新运算
第一讲教学目标: 定义新运算 定义新运算这类题目是在考验学生的适应能力,大家都习惯四则运算,定义新运算就打破了运算 规则,要求学生要严格按照题目的规定做题.新...
第一讲 数与式(含答案)
第一讲 数与式(含答案)_数学_初中教育_教育专区...(2010 年兰州市中考试题) 计算: 2 ? tan 60 ?...并且其上底为 2 b ,下底为 2 a , 高为( a...
第一讲 数与式的运算
课件园 http://www.kejianyuan.com 第一讲 数与式的运算在初中,我们已学习了实数,知道字母可以表示数用代数式也可以表示数,我们把实数和代 数式简称为数与式...
更多相关标签: