第七章 高精度计算.ppt

1、第七章 高精度计算,7.1 例题：大整数加法 7.2 例题：大整数乘法 7.3 例题：大整数除法 7.4 例题：麦森数,大整数加法,问题描述 求两个不超过200 位的非负整数的和。 输入数据 有两行，每行是一个不超过200 位的非负整数，没有多余的前导0。 输出要求 一行，即相加后的结果。结果里不能有多余的前导 0，即如果结果是342，那么就不能输出为 0342,解题思路 1)大整数以字符串方式输入 2) 用整型数组an来存放大整数 用unsigned an1201保存第一个数，用unsigned an2200表示第二个数， an0存放个位数，an1存放十位数，an2存放百位数 数字字符变数字

2、的方式是减去字符0 3）模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。 相加的结果直接存放在an1中。要注意处理进位。,大整数加法,#include #include #define MAX_LEN 200 int an1MAX_LEN+10; int an2MAX_LEN+10; char szLine1MAX_LEN+10; char szLine2MAX_LEN+10; int main() scanf(%s, szLine1); scanf(%s, szLine2); int i, j; memset( an1, 0, sizeof(an1); memset( an

3、2, 0, sizeof(an2); int nLen1 = strlen( szLine1); j = 0; for( i=nLen1-1;i=0;i-) an1j+=szLine1i - 0; int nLen2 = strlen(szLine2); j = 0; for( i=nLen2-1;i=0;i-) an2j+= szLine2i-0;,大整数加法,int an1MAX_LEN+10=0; int an2MAX_LEN+10=0;,大整数加法,for( i = 0;i = 10 ) an1i -= 10; an1i+1 +; bool bStartOutput = false;

4、/用于跳过多余的0 for( i = MAX_LEN; i = 0; i - ) if (bStartOutput) printf(%d, an1i); else if( an1i ) printf(%d, an1i); bStartOutput = true; return 0; ,大整数乘法,问题描述 求两个不超过200 位的非负整数的积。 输入数据 有两行，每行是一个不超过200 位的非负整数，没有多余的前导0。 输出要求 一行，即相乘后的结果。结果里不能有多余的前导 0，即如果结果是342，那么就不能输出为 0342。,解题思路 用unsigned an1200和unsigned an

5、2200分别存放两个乘数，用aResult400来存放积。计算的中间结果存在aResult中。aResult长度取400是因为两个200位的数相乘，积最多有400位。an10,an20, aResult0都表示个位。 一个数的第i位和另一个数的第j位相乘所得的数，是累加到结果的第i+j位上。这里i, j都是从右往左，从0开始数。 计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。,大整数乘法,现以 83549为例来说明程序的计算过程。 先算8359。59得到45个1，39得到27个10，89得到72个100。不急于处理进位，8359算完后，a

6、Result如下：,接下来算45。此处45的结果代表20个10，因此要aResult1+=20，变为：,再接下来算43。此处43的结果代表12个100，因此要 aResult2+= 12，变为：,最后算 48。此处48的结果代表 32个1000，因此要 aResult3+= 32，变为：,乘法过程完毕。接下来从 aResult0开始向高位逐位处理进位问题。aResult0留下5，把4加到aResult1上，aResult1变为51后，应留下1，把5加到aResult2上最终使得aResult里的每个元素都是1位数，结果为40915。,#include #include #define MAX_

7、LEN 200 unsigned an1MAX_LEN+10; unsigned an2MAX_LEN+10; unsigned aResultMAX_LEN * 2 + 10; char szLine1MAX_LEN+10; char szLine2MAX_LEN+10; int main() gets( szLine1); gets( szLine2); int i, j; int nLen1 = strlen( szLine1); memset( an1, 0, sizeof(an1); memset( an2, 0, sizeof(an2); memset( aResult, 0, s

8、izeof(aResult);,大整数乘法,大整数乘法,for( j = 0, i = nLen1 - 1;i = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for(j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; for( i = 0;i = 10 ) aResulti+1 += aResulti / 10; aResulti %= 10; ,大整数乘法,/下面输出结果 bool bStartOutput = false; for( i = MAX_LE

9、N * 2; i = 0; i - ) if( bStartOutput) printf(%d, aResulti); else if( aResulti ) printf(%d, aResulti); bStartOutput = true; If (! bStartOutput ) /若结果为0时的输出 printf(“0”); return 0; ,大整数除法,问题描述 求两个大的正整数相除的商 输入数据 第 1 行是测试数据的组数n，每组测试数据占2 行，第1行是被除数，第2 行是除数。 每组测试数据之间有一个空行，每行数据不超过 100 个字符 输出要求 n 行，每组测试数据有一行输

10、出是相应的整数商,基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。 本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。,大整数除法(整除),int Substract( int * p1, int * p2, int nLen1, int nLen2) int

11、i; if( nLen1 = 0; i - ) if( p1i p2i ) bLarger = true; else if( p1i =nLen2 时，p2i = 0 if( p1i = 0 ; i- ) if( p1i ) return i+1; return 0; ,大整数除法,#include #include #define MAX_LEN 200 char szLine1MAX_LEN + 10; char szLine2MAX_LEN + 10; int an1MAX_LEN + 10; /被除数, an10对应于个位 int an2MAX_LEN + 10; /除数 int aR

12、esultMAX_LEN + 10; /存放商 int main() int t, n; char szBlank20; scanf(%d, ,if( nLen1 0 ) for( i = nLen1 -1; i = 0; i - ) if( i = nTimes ) an2i = an2i-nTimes; else an2i = 0; nLen2 = nLen1; for( j = 0 ; j = 0) nLen1 = nTmp; aResultnTimes-j+; ,OutputResult: for( i = 0; i = 10 ) aResulti+1 += aResulti / 10

13、; aResulti %= 10; bool bStartOutput = false; for( i = MAX_LEN ; i = 0; i - ) /输出 if( bStartOutput) printf(%d, aResulti); else if( aResulti ) printf(%d, aResulti); bStartOutput = true; if (!bStartOutput ) printf(0n); printf(n); return 0; ,麦 森 数,问题描述 形如2p-1的素数称为麦森数，这时P 一定也是素数。但反过来不一定，即如果 P 是素数。2p-1不一定

14、是素数。 到1998 年底，人们已找到了 37个麦森数。最大的一个是P=3021377，它有909526 位。麦森数有许多重要应用，与完全数密切相关。 要求输入P (1000P3100000) , 计算2p-1 的位数和最后500位数字（用十进制高精度数表示） 输入数据 一个整数P(1000P3100000) 输出要求 第1 行：十进制高精度数2P-1的位数。 第 2-11 行：十进制高精度数 2P-1的最后500位数字。（每行输出 50 位，共输出 10 行，不足500 位时高位补0） 不必验证2p-1与P是否为素数。,解题思路 第一个问题，输出2p-1(和2p相同)有多少位 double

15、log10(double x) 函数 P=a020+a121+an-12n-1+2n 2P=2a0 * 22a1* 24a2 *2an-12n-1+22n,麦 森 数,麦森数,#include #include #define LEN 125 / 数组125 个元素，每个元素存放十进制的4 位。 #include void Multiply(int* a, int* b) int i, j; int nTmp; int nCarry; /存放进位 int cLEN; /存放结果的末 500 位 memset(c, 0, sizeof(int) * LEN); for (i=0;iLEN;i+)

16、 nCarry=0; for (j=0;jLEN-i;j+) nTmp=ci+j+aj*bi+nCarry; ci+j=nTmp%10000; nCarry=nTmp/10000; memcpy( a, c, LEN*sizeof(int); ,int main() int i , p; int anPowLEN; int aResultLEN; /存放最终结果的末 500 位 scanf(%d, ,例题：循环数,问题描述 当一个N位的整数X满足下列条件时，称其为循环数：X与任意一个整数1Y N相乘时，都将产生一个X的“循环”。即：分别将这两个整数的第1位数字与最后1位数字连在一起，可以得到一

17、个相同的数字循环；当然两个整数在该数字循环中的起始位置不同。例如，142857是一个循环数 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142,输入 写一个程序判断一个整数是否是循环数。输入文件是一个整数序列，每个整数长度为260。注意：每个整数前面的零被看作是该整数的一部分，在计算N时要统计。例如“01”是一个2位的整数，而“1”是一个1位的整数。 输出 对每个输入整数，输出一行，说明该整数是否是循环数。,样例输入 1

18、42857 142856 142858 01 0588235294117647 样例输出 142857 is cyclic 142856 is not cyclic 142858 is not cyclic 01 is not cyclic 0588235294117647 is cycl,解题思路,高精度的乘法：整数可能达60位 X*1: Y0 = X; X*2: Y1 = Y0+X X*3: Y2 = Y1+X Yi是否是X的“循环”？,解题思路: Yi是否是X的“循环”？,穷举：N位整数，循环移位可以有N种可能 循环移位方法： Yi是否是“XX” 的子串？,1,2,3,4,5,6,7,1,2,3,4,5,6,7,0,#include #include #define MAX_LEN 201 int an1MAX_LEN+10; int an2MAX_LEN+10; char szLine1MAX_LEN+10; char szLine2MAX_LEN+10; char szDouble2 * MAX_LEN + 10; int Add(int nMaxLen , int * an1, int