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

第一讲 高精度运算


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


相关文章:
高精度运算(加减)
安阳一中信息学奥赛辅导资料 高精度计算(一) 一、 教学目标 ? ? 二、 了解...第 3 页共 7 页 安阳一中信息学奥赛辅导资料 【例 2】 高精度减法(a-b)...
NOIP高精度讲解
高精度加法 所谓的高精度运算,是指参与运算的数(加...(如:第一位是'1',第二位是'34',第三位是'...noip讲义1-高精度运算讲... 7页 1下载券 pascal...
高精度算法大全
对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了 高精度算法: 由于计算机输入计算结果的精度通常受到计算机的限制,如:在双精度方式 下,计算机...
高精度运算及其应用
Jsoi2010 春季函授讲义(B2) Jsoi2010 春季函授讲义(B2) 1/13 高精度运算及其应用一,引言 利用计算机进行数值运算,经常会遇到数值太大,超出 Longint,int64 等...
高精度运算和简单优化方法(C语言)
高精度运算和简单优化方法(C语言)_IT/计算机_专业资料。高精度运算和简单优化方法...} //处理第一个加数,每九位划分后剩余的位数转化为一个 数 p=sa; for(i...
高精度加法
要编写一个高精度计算器的核心部分。所谓高精度计算器,就是可以计算很大很大的...2、开发工具(列出所使用的开发工具和第 3 方开发库) Code::block 3、主要...
C语言的高精度算法
C语言的高精度算法_工学_高等教育_教育专区。C语言的高精度算法 高精度计算一. 加法 先判断出两个数哪个较长,两个数从个位对齐后, 从个位数开始相加,先不...
科学计算当中的高精度浮点运算
科学计算当中的高精度浮点运算_IT/计算机_专业资料。高精度浮点运算 科学计算当中的高精度浮点运算 David H. Bailey 2005年1月25日 摘要: 摘要 目前,IEEE的64...
java中进行高精度精准计算
java中进行高精度精准计算_计算机软件及应用_IT/计算机_专业资料。java中进行高...(xxx); xxx 只能是数值类型 注意:推荐使用第一种方法,并采用 string 类型进行...
高精度算法报告
高精度算法研究秦雪洋,廖福轩,吴韩,顾仁杰,楼嘉豪 (陕西师范大学 计算机科学...第一步转换第二部运算第三部在转换 回字符串,这个程序进行了多次修改核心代码,...
更多相关标签: