… 18
17
… …
5
4
3
2
1
…
18
17
… …
5
4
3
2
1
a
…
0 1
5 4
1
3 4
3 0
8 3 9
7 6
b
0 … 0
9
9
2
7
5
9
la la 最高位a[la]=0，则a的长度-1
lb
高精度运算
高精度运算中需要处理的问题： 1.数据的接收与存储 2.进位、借位处理
加法进位：a[i]=a[i]+b[i];
{将a,b数组对应元素相加的和存入a数组}
图4
i 100 … a … 4
8
7
6
5 20 0 1
4 81 1 6
3 96 6 8
2 0
1 0
47 119 110 0 7 3 9 9
la
g
4g
11g
11g
2g
8g
9g
0g
0
编写精确计算n的阶乘 （ 编写精确计算 的阶乘n!（7<n<50）的程序 的阶乘 ）
∵ 50!<5050<10050=(102)50=10100 ！可以用 个数组元素a[1],a[2],…,a[100]来存放 一个数组元 来存放,一个数组元 ∴ 50！可以用100个数组元素 个数组元素 来存放 素存放一个数位上的数字。 素存放一个数位上的数字。
5468 0001 4096 75468 1200001 494096 322 5128 2111
la
7 i
120i 120i
49 i
122
3.改善高精度运算的效率 3.改善高精度运算的效率
⑴.扩大进制数 扩大进制数 ⑵.建立因子表 建立因子表
应用的前提：只用于乘和除运算， 应用的前提：只用于乘和除运算，不能用于加减运算 同底两数相乘除，底数不变， 同底两数相乘除，底数不变，指数相加减 依据：任何自然数都可以表示为: 依据：任何自然数都可以表示为:
a[i]>9 : a[i+1]=a[i+1]+1; {处理进位} a[i]=a[i] -10; {整理本位}
300
… …
18 1
17 4
… …54321
a
0
1
4
8 1 0
9 10 19 9
15 5 6
la x
300
… …
18 0
17 9
… …
5
4
3
2
1
b
0
9
2
7
9
9
lb
高精度运算
高精度运算中需要处理的问题： 92099 1.数据的接收与存储 - 14796 2.进位、借位处理
③ 几个基本运算
整数数组-1（借位） Ⅰ.整数数组 （借位） 整数数组 j:=1；while (n[j]=0) do j:=j+1； {从n[1]出发往左扫描，寻找第一个非零的元素} ； ； n[j]:=n[j]-1；{由于该位接受了底位的借位，因此减1} ； for k:=1 to j do n[k]:=9999；{其后缀全为9999} ； if ((j=ln) and (n[j]=0)) then ln:=ln-1；{如果最高位为0，则n的长度减1} ；
高精度乘法运算
1.高精度乘以单精度 39916800
单精度乘以单精度:
×
c=12 a[i]=a[i]*c+g; {黄色g表示低位向高位的进位} g=a[i] / 10; a[i]=a[i] % 10;
12
856 × 25 4280 1712 21400
图3
A3A2A1 B2B1 × C ’4 C ’3 C ’2 C ’1 C”5C”4C”3C”2 C6C 5C4C 3C2C1
9999 … …
6
5
4
3
2
1
n
1003 9999 9999 9999 9999 9999 1004 0000 0000 0000 0000 0000
Ⅱ.整数数组除以整数 Ⅱ.整数数组除以整数 a←a/b， 为整数数组， 为整数） （a←a/b，a为整数数组，b为整数）
…
234 145789546800014096
a[i]>9 : a[i+1]=a[i+1]+1; {处理进位} a[i]=a[i] -10; {整理本位} 减法借位：a[i]<b[i]： {将a,b数组对应元素相减的差存入a数组} a[i+1]=a[i+1]-1 {a的高位减1} a[i]=a[i]+10- b[i]; {a本位加10} 乘法进位：s=a[i]*b[j]+g; {将a,b数组相乘的积存入c数组} g=s /10; {向高位的进位g} c[i+j-1]:=c[i+j-1]+s % 10;
标准整型Integer 标准整型 长整型Longint 长整型 短整型Shortint 短整型 字节型Byte 字节型 字型Word 字型 -32768..32767 -2147483648..2147483647 -128..127 0..255 0..65535
从键盘读入两个很大的正整数（不超过 从键盘读入两个很大的正整数（不超过255位） 位 145789546800014096 和99298975843692799，求它 99298975843692799， 们的和。 们的和。
数值问题
一、高精度运算
从键盘读入两个很大的正整数（不超过 从键盘读入两个很大的正整数（不超过255位） 位 145789546800014096 和99298975843692799，求它 99298975843692799， 们的和。 们的和。
怎样输入、接收与存储数据？ 怎样输入、接收与存储数据？
加法进位：a[i]=a[i]+b[i];
77303 A5 A4 A3 A2 A1 - B5 B4 B3 B2 B1 C5 C4 C3 C2 C1
图4 图3 {将a,b数组对应元素相加的和存入a数组}
a[i]>9 : a[i+1]=a[i+1]+1; {处理进位} a[i]=a[i] -10; {整理本位} 减法借位：a[i]<b[i]：a[i+1]=a[i+1]-1 {a的高位减1} a[i]=a[i]+10- b[i]; {a本位加10} a[i]=a[i]-b[i] {将a,b数组对应元素相减的差存入a数组}
(文件名：mason.pas，输入文件：mason.in，输入文件： mason.out)
【问题描述】形如2P-1的素数称为麦森数，这时P一定也是 问题描述】形如2 的素数称为麦森数，这时P 个素数。但反过来不一定，即如果P是个素数，2 个素数。但反过来不一定，即如果P是个素数，2P-1不一定也 是素数。到1998年底，人们已找到了37个麦森数。最大的一 是素数。到1998年底，人们已找到了37个麦森数。最大的一 个是P=3021377，它有909526位。麦森数有许多重要应用， 个是P=3021377，它有909526位。麦森数有许多重要应用， 它与完全数密切相关。 任务：从文件中输入P 1000<P<3100000），计算2 任务：从文件中输入P（1000<P<3100000），计算2P-1的 位数和最后500位数字（用十进制高精度数表示） 位数和最后500位数字（用十进制高精度数表示） 【输入格式】文件中只包含一个整数P（1000<P<3100000） 输入格式】文件中只包含一个整数P 1000<P<3100000） 【输出格式】 输出格式】 第一行：十进制高精度数2 第一行：十进制高精度数2P-1的位数。 第2-11行：十进制高精度数2P-1的最后500位数字。（每 11行：十进制高精度数2 的最后500位数字。（每 行输出50位，共输出10行，不足500位时高位补0 行输出50位，共输出10行，不足500位时高位补0） 不必验证2 不必验证2P-1与P是否为素数。
6 13
s[6]
7 17
s[7]
8 19
s[8]
… … … … … … … …
360:
3
s[1]
2
s[2]
1
s[3]
0
s[4]
0
s[5]
0
s[6]
0
s[7]
0
s[8]
26: 360*26:
1
s[1]
0
s[2]
0
s[3]
0
s[4]
0
s[5]
1
s[6]
0
s[7]
0
s[8]
4
2
1
0
0
1
0
0
4.麦森数 4.麦森数
…
8
7
6
5
4
3
2
1
…
3
la
9
9
1
6
8
0
0
1
lb …
8
2
3
4
5
6
7
8
7
6
5
4
3
2
1
整数数组除以整数 a←a/b， 为整数数组， 为整数） （a←a/b，a为整数数组，b为整数）
i=0；{余数初始化} for (int j=la;j>=1;j--) {按照由高位到底位的顺序，逐位相除} j=la; >=1 --) a[j]=a[j]+i 10；{ a[j]=a[j]+i*10；{接受了来自第j+1位的余数} j+1 } i=a[j]%b；{计算第j位的余数} =a[j]% a[j]=a[j]/b； a[j]=a[j]/b；{计算商的第j位} while (a[la]==0) la=la-1；{计算商的有效位数} (a[la]==0 la=la-