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

第一讲 高精度运算


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


相关文章:
第一讲 定义新运算
第一讲 定义新运算_数学_自然科学_专业资料。第一讲 定义新运算 【专题解析】 定义新运算是指运用某种特殊符号来表示特定的意义,从而解答 某些算式的一种运算。 ...
第一讲 简便运算
第一讲 简便运算_数学_小学教育_教育专区。第一讲 简便运算知识要点 首先必须掌握一些计算法则、定律、性质和拆、并等一些技巧性方法。其 次是要整体观察题目,...
第一讲 四则运算
第一讲 四则运算_四年级数学_数学_小学教育_教育专区。机构,讲义,教案,资料,成体系,一共15讲 四年级数学讲义(54 期) 第一讲 四则运算 一、知识提炼 1、四...
第一讲 速算与巧算
第一讲 速算与巧算 在速算中常用的三大基本思想:①凑整(整十,整百,整千 ②分拆(分拆后可以整十,整百, 整千 ③分组 常见的运算定律及其方法 一:加法交换律...
第一讲:速算与巧算(一)
第一讲:速算与巧算(一)_学科竞赛_小学教育_教育...用简便方法计算下面各题。 (1)375-88-12 (2)...(2)他们三人的最高成绩是多少分? 举一反三: 1....
第一讲速算巧算
第一讲 速算巧算(一)(在巧算方法里,蕴含着一种重要的解决问题的策略——转化问题 法。即将所给算式,根据运算定律和运算性质,改变它的运算顺序, 或凑整,从而...
第一讲分式的运算
第一讲分式的运算_数学_初中教育_教育专区。第一讲 分式的运算 (一) 、分式...各分母系数的最小公倍数; ②最简公分母的字母因式取各分母所有字母的最高次...
第一讲 速算与巧算
第一讲【教学目标】 1.掌握加减法的基本简便运算 【教学重点】 速算与巧算 2.培养良好的数感及观察能力 1.掌握加减法中的简便运算算理 2.理解加减法算理并...
1第一讲四则运算
1第一讲四则运算_数学_小学教育_教育专区。四升五暑假教材 第一讲 四则运算知识点: 1、同级运算顺序:在没有括号的算式里,如果只有加、减法或者只有乘、除法,...
第一讲:数与式的运算
第一讲:数与式的运算_高一数学_数学_高中教育_教育专区。初高中数学衔接教材第...——适用高次式; ⑥竖式除法(短除法) :先猜根,再用竖式除法——适用高次...
更多相关标签: