模拟与高精度计算ppt课件

1、第六讲第六讲模拟与高精度计算模拟与高精度计算ACMACM算法与程序设计算法与程序设计数学科学学院：汪小平数学科学学院：汪小平wxiaoping3251632/57n 现实中的有些问题难以找到公式或规律来处理。现实中的有些问题难以找到公式或规律来处理。只能按照一定步骤不停地做下去，最后才干得只能按照一定步骤不停地做下去，最后才干得到答案。这样的问题，用计算机来处理非常适到答案。这样的问题，用计算机来处理非常适宜，只需能让计算机模拟人在处理问题时的行宜，只需能让计算机模拟人在处理问题时的行为即可。这一类的问题可以称之为为即可。这一类的问题可以称之为“模拟题。模拟题。3/57摘花生摘花生 poj.g

2、rids/problem?id=2950问题描画问题描画 鲁宾逊先生有一只宠物猴，鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正名叫多多。这天，他们两个正沿着乡间小路散步，忽然发现沿着乡间小路散步，忽然发现路边的告示牌上贴着一张小小路边的告示牌上贴着一张小小的纸条：的纸条：“欢迎免费品味我种的欢迎免费品味我种的花生！花生！熊字。熊字。 鲁宾逊先生和多多都很开心，鲁宾逊先生和多多都很开心，由于花生正是他们的最爱。在由于花生正是他们的最爱。在告示牌背后，路边真的有一块告示牌背后，路边真的有一块花生田，花生植株整齐地陈列花生田，花生植株整齐地陈列成矩形网格如图成矩形网格如图1。4/57l 有阅历

3、的多多一眼就能看出，每棵花生植株下的花生有多有阅历的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：少。为了训练多多的算术，鲁宾逊先生说：“他先找出花生他先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过他一定要在我生最多的，去采摘它的花生；依此类推，不过他一定要在我限定的时间内回到路边。限定的时间内回到路边。 l 我们假定多多在每个单位时间内，可以做以下四件事情中我们假定多多在每个单位时间内，可以做以下四件事情中的一件：的一件： l(1) 从路边跳到最接近路

4、边即第一行的某棵花生植株；从路边跳到最接近路边即第一行的某棵花生植株；l(2) 从一棵植株跳到前后左右与之相邻的另一棵植株；从一棵植株跳到前后左右与之相邻的另一棵植株； l(3) 采摘一棵植株下的花生；采摘一棵植株下的花生； l(4) 从最接近路边即第一行的某棵花生植株跳回路边。从最接近路边即第一行的某棵花生植株跳回路边。 l如今给定一块花生田的大小和花生的分布，请问在限定时如今给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？留意能够只需部分植间内，多多最多可以采到多少个花生？留意能够只需部分植株下面长有花生，假设这些植株下的花生个数各不一样。株下面长有花生，假

5、设这些植株下的花生个数各不一样。5/57l 例如在图例如在图2所示的花生田里，只需位于所示的花生田里，只需位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为的植株下长有花生，个数分别为13, 7, 15, 9。沿。沿着图示的道路，多多在着图示的道路，多多在21个单位时间内，最多可以采到个单位时间内，最多可以采到37个花生。个花生。 6/57 输入格式输入格式 输入的第一行包括一个整数输入的第一行包括一个整数T，表示数据组数。，表示数据组数。 每组输入的第一行包括三个整数，每组输入的第一行包括三个整数，M, N和和K，用空，用空格隔开；表示花生田的大小为

6、格隔开；表示花生田的大小为M * N1 = M, N = 50，多多采花生的限定时间为，多多采花生的限定时间为K0 = K = 1000个单位时间。接下来的个单位时间。接下来的M行，每行包括行，每行包括N个非负整数，个非负整数，也用空格隔开；第也用空格隔开；第i + 1行的第行的第j个整数个整数Pij0 = Pij = 500表示花生田里植株表示花生田里植株(i, j)下花生的数目，下花生的数目，0表表示该植株下没有花生。示该植株下没有花生。 输出要求输出要求 输出包括输出包括T行，每一行只包含一个整数，即在限行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。定时间内，多多

7、最多可以采到花生的个数。 7/57 样例输入样例输入 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 样例输出样例输出 37 8/57n 找规律得到一个以花生矩阵作为自变量的公式来处理这个找规律得到一个以花生矩阵作为自变量的公式来处理这个问题，是不现实的。问题，是不现实的。n 结果只能是做了才知道。即走进花生地每次要采下一株结果只能是做了才知道。即走进花生地每次要采下一株花生之前，先计算一下剩下的时间够不够走到那株花生，采花生之前，先计算一下剩下的时间够不够

8、走到那株花生，采摘，并从那株花生走回到路上。假设时问够那么走过去采摘，并从那株花生走回到路上。假设时问够那么走过去采摘；假设时间不够，那么采摘活动到此终了。摘；假设时间不够，那么采摘活动到此终了。n 设二维数组设二维数组aField存放花生地的信息。然而，用存放花生地的信息。然而，用aField00还是还是aField11对应花生地的左上角是值得对应花生地的左上角是值得思索一下的。由于从地里到路上还需求思索一下的。由于从地里到路上还需求1个单位时间，标题个单位时间，标题中的坐标又都是从中的坐标又都是从1开场。所以假设开场。所以假设aField11对应花生对应花生地的左上角，那么从地的左上角，那

9、么从aFieldij点回到路上所需时间就是点回到路上所需时间就是i，这样更为方便和自然，不易出错。这样更为方便和自然，不易出错。解题思绪解题思绪9/57参考程序参考程序#include #include#include#includeint T, M, N, K;#define MAX_NUM 55int aFieldMAX_NUM MAX_NUM;main() scanf(“%d, &T); for(int t=0; tT; t+) scanf(“%d%dd, &M, &N, &K); /花生地的左上角对应的数组元素是花生地的左上角对应的数组元素是aField

10、11，路的纵坐标，路的纵坐标是是0 for(int m=1; m=M; m+) for(int n=1; n=N; n+) scanf(“d，&afieldmn); int nTotalPeanuts=0; /摘到的花生总数摘到的花生总数 int nTotalTime=O; /曾经花去的时问曾经花去的时问 int nCuri=0，nCurj; /当前位置坐标，当前位置坐标， /nCuri代表纵坐标，开场是在路上，所以初代表纵坐标，开场是在路上，所以初值为值为010/57 while(nTotalTimeK) /假设还有时间假设还有时间 int nMax=0, nMaxi, nMaxj;

11、 /最大的花生数目，最大的花生数目， /及其所处的位置及其所处的位置 for(int i=1; i=M; i+) /下面这个循环寻觅下一个下面这个循环寻觅下一个 /最大花生数目及其位置最大花生数目及其位置 for(int j=1; j=N; j+) if(nMaxaFieIdij) nMax=aFieIdij; nMaxi=i; nMaxj=j; if(nMax = = 0) /地里曾经没有花生了地里曾经没有花生了 break; if(nCuri = = 0) nCurj=nMaxj; /假设当前位置是在路上，那么假设当前位置是在路上，那么 /应走到横坐标应走到横坐标nMaxj处，再进人花生地

12、处，再进人花生地11/57 / 下一行看剩余时间能否足够走到下一行看剩余时间能否足够走到(nMaxi，nMaxj)处，处， /摘取花生，并回到路上摘取花生，并回到路上 if(nTotaITime+nMaxi+1+abs(nMaxi-nCuri) +abs(nMaxj-nCurj) =K) / 下一行加上走到新位置，以及摘花生的时问下一行加上走到新位置，以及摘花生的时问 nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; /走到新的位置走到新的位置 nTotaiPeanuts+=aFieldnMax

13、inMaxj; aFieldnMaxinMaxj=0; /摘走花生摘走花生 else break； printf(“%dn, nTotalPeanuts); 12/57常见问题常见问题 这个标题应该仔细阅读。往往没有看到每次只能拿剩下这个标题应该仔细阅读。往往没有看到每次只能拿剩下花生株中最大的，而是希望找到一种在规定时间内可以花生株中最大的，而是希望找到一种在规定时间内可以拿最多花生的组合，把标题变成了另外一道题。拿最多花生的组合，把标题变成了另外一道题。 没有读到没有读到没有两株花生株的花生数目一样的条件，因没有两株花生株的花生数目一样的条件，因此把标题复杂化了。此把标题复杂化了。 这个标

14、题是假设猴子在取花生的过程中不会回到大路上，这个标题是假设猴子在取花生的过程中不会回到大路上，而有些同窗思索能否能够在中间回到大路上，由于标题而有些同窗思索能否能够在中间回到大路上，由于标题没说在大路上挪动要花时间，所以有能够中途出来再进没说在大路上挪动要花时间，所以有能够中途出来再进去摘的花生更多。去摘的花生更多。 此题的解法虽然直观但是有一个弊端就是每次在寻此题的解法虽然直观但是有一个弊端就是每次在寻觅下一个最大花生植株时，都要遍历整个矩阵，效率不觅下一个最大花生植株时，都要遍历整个矩阵，效率不高。用什么方法才干高效率地找到下一个最大花生植株高。用什么方法才干高效率地找到下一个最大花生植株

15、?13/57显示器显示器1、链接地址、链接地址 poj.grids/problem?id=27452、问题描画、问题描画 他的一个朋友买了一台电脑。他以前只用过计算器，由他的一个朋友买了一台电脑。他以前只用过计算器，由于电脑的显示器上显示的数字的样子和计算器是不一样，于电脑的显示器上显示的数字的样子和计算器是不一样，所以当他运用电脑的时候会比较郁闷。为了协助他，他决所以当他运用电脑的时候会比较郁闷。为了协助他，他决议写一个程序把在电脑上的数字显示得像计算器上一样。议写一个程序把在电脑上的数字显示得像计算器上一样。14/57 输入数据输入数据 输入包括假设干行，每行表示一个要显示的数。每输入包括

16、假设干行，每行表示一个要显示的数。每行有两个整数行有两个整数s 和和n (1 = s = 10, 0 =n= 99999999)，这里这里n 是要显示的数，是要显示的数，s 是要显示的数的尺寸。假设是要显示的数的尺寸。假设某行输入包括两个某行输入包括两个0，表示输入终了。这行不需求处，表示输入终了。这行不需求处置。置。 输出要求输出要求 显示的方式是：用显示的方式是：用s 个个-表示一个程度线段，用表示一个程度线段，用s 个个|表示一个垂直线段。这种情况下，每一个数字需表示一个垂直线段。这种情况下，每一个数字需求占用求占用s+2 列和列和2s+3 行。另外，在两个数字之间要输行。另外，在两个数

17、字之间要输出一个空白的列。在输出完每一个数之后，输出一个出一个空白的列。在输出完每一个数之后，输出一个空白的行。留意：输出中空白的地方都要用空格来填空白的行。留意：输出中空白的地方都要用空格来填充。充。15/57 输入样例输入样例2 123453 678900 0 输出样例输出样例16/57一个计算器上的数字显示单元，可以看作由以下编一个计算器上的数字显示单元，可以看作由以下编号从号从1 到到7 的的7 个笔画组成：个笔画组成： 3 3、解题思绪、解题思绪17/57 那么，我们可以说，数字那么，我们可以说，数字8 覆盖了一切的笔画，数字覆盖了一切的笔画，数字7 覆盖笔画覆盖笔画1、3 和和6，

18、而数字，而数字1覆盖笔画覆盖笔画3、6。留意，每个。留意，每个笔画都是由笔画都是由s 个个-或或s 个个|组成。组成。 输出时，先输出第输出时，先输出第1 行，即整数行，即整数n 中一切数字里的笔中一切数字里的笔画画1，然后输出第，然后输出第2 行到第行到第s+1 行，即一切数字的笔画行，即一切数字的笔画2 和笔画和笔画3，接下来是第，接下来是第s+2 行，即一切数字的笔画行，即一切数字的笔画4，再，再接下来是第接下来是第s+3行到行到2s+2 行，就是一切数字的笔画行，就是一切数字的笔画 5 和笔画和笔画6，最后的第，最后的第2s+3 行，是一切数字的笔画行，是一切数字的笔画7。假。假设某个

19、数字设某个数字d 没有覆盖某个笔画没有覆盖某个笔画m (m = 17)，那么，那么，输出数字输出数字d 的笔画的笔画m 的时候，就应该都输出空格；假设的时候，就应该都输出空格；假设覆盖了笔画覆盖了笔画m，那么输出，那么输出s 个个-或或s 个个|，这取决于笔画，这取决于笔画m 是横的还是竖的。是横的还是竖的。解题思绪解题思绪18/57由上思绪，处理这道标题的关键，就在于如何记录每个数字由上思绪，处理这道标题的关键，就在于如何记录每个数字都覆盖了哪些笔画。实践上，假设我们记录的是每个笔画都都覆盖了哪些笔画。实践上，假设我们记录的是每个笔画都被哪些数字覆盖，那么程序实现起来更为容易。一个笔画被被哪

20、些数字覆盖，那么程序实现起来更为容易。一个笔画被哪些数字所覆盖，可以用一个数组来记录，比如记录笔画哪些数字所覆盖，可以用一个数组来记录，比如记录笔画1 覆盖情况的数组如下：覆盖情况的数组如下：char n111 = - - -;其中，其中，n1i(i = 09) 代表笔画代表笔画1 能否被数字能否被数字i 覆盖。假设覆盖。假设是，那么是，那么n1i 为为-，假设否，那么，假设否，那么n1i为空格。上面的数组为空格。上面的数组的值表达了笔画的值表达了笔画1 被数字被数字0, 2, 3, 5, 6, 7, 8, 9 覆盖。覆盖。对于竖向的笔画对于竖向的笔画2，由字符，由字符 | 组成，那么记录其覆

21、盖情况的组成，那么记录其覆盖情况的数组如下：数组如下：char n211 = | | |;该数组的值表达了笔画该数组的值表达了笔画2 被数字被数字0, 4, 5, 6, 8, 9 覆盖。覆盖。解题思绪解题思绪19/574、参考程序、参考程序#include #include char n111=- - -;/笔画笔画1 被数字被数字0,2,3,5,6,7,8,9 覆盖覆盖char n211=| | |;/笔画笔画2 被数字被数字0,4,5,6,8,9 覆盖覆盖char n311=| |;/笔画笔画3 被数字被数字0,1,2,3,4,7,8,9 覆盖覆盖char n411= - -;/笔画笔画4

22、 被数字被数字2,3,4,5,6,8,9 覆盖覆盖char n511=| | | | ;/笔画笔画5 被数字被数字0,2,6,8覆盖覆盖char n611=| |;/笔画笔画6 被数字被数字0,1,3,4,5,6,7,8,9 覆盖覆盖char n711=- - - -;/笔画笔画7 被数字被数字0,2,3,5,6,8,9 覆盖覆盖int main(void) int s; char szNumber20; int nDigit , nLength, i , j , k;20/57 while(1) scanf( %d%s, &s, szNumber); if (s = 0) break

23、; nLength = strlen(szNumber); for (i = 0 ; i nLength ; i+) /输出一切数字的笔画1 nDigit = szNumberi - 0; printf( ); for (j = 0 ; j s ; j+) /一个笔画由s 个字符组成 printf(%c, n1nDigit); printf( );/两个空格 printf(n);4、参考程序、参考程序21/57 for (i = 0 ; i s ; i+) /输出一切数字的笔画2 和笔画3 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0;

24、 printf(%c, n2nDigit); for (k = 0 ; k s ; k+) printf( ); /笔画2 和笔画3 之间的空格 printf(%c , n3nDigit);/有一个空格 printf(n); for (i = 0 ; i nLength ; i+) /输出一切数字的笔画4 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n4nDigit); printf( );/两个空格 printf(n);4、参考程序、参考程序22/574、参考程序、参考程序 for (i = 0 ;

25、 i s ; i+) /输出一切数字的笔画输出一切数字的笔画5 和笔画和笔画6 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n5nDigit); for (k = 0 ; k s ; k+) printf( ); /笔画笔画5 和笔画和笔画6 之间的空格之间的空格 printf(%c , n6nDigit);/有一个空格有一个空格 printf(n); for (i = 0 ; i nLength ; i+) /输出一切数字的笔画输出一切数字的笔画7 printf( ); nDigit = szNumberi

26、- 0; for (j = 0 ; j 1) l-; a0 = l; 28/57 当当 ai上的数据小于上的数据小于 0 的时候，就要由高位退位的时候，就要由高位退位了。由于该数组中下标越大，位数越高，故当了。由于该数组中下标越大，位数越高，故当 ai位小于位小于 0时，时，ai + 1位退位的操作位退位的操作 以十进制为以十进制为例为：例为： ai + 1-; ai += 10; 假设假设 aa0位等于位等于 0，在退位的同时就要思索，在退位的同时就要思索a0的值的改动了。此时要减小的值的改动了。此时要减小a0，直到到达准确，直到到达准确位数。位数。 while (aa0 = 0 &

27、 a0 1) a0-; 29/57高精度数加整型数算法：高精度数加整型数算法： 将整型加到将整型加到 a1后，再不断进位，直到后，再不断进位，直到 ai小于小于 10为止。但是假设为止。但是假设 a1+x就曾经溢出整型的范围的话，就需求就曾经溢出整型的范围的话，就需求a1+x%10，a2+x/10后后再进位。再进位。 memcpy(tmp, a, sizeof(tmp); /复制复制a到到tmp 中中 int l = 1; tmp1 += x; while (tmpl 9) tmpl + 1 += tmpl / 10; tmpl %= 10; l+; /inc(i) if (l tmp0) t

28、mp0 = l; memcpy(b, tmp, sizeof(b); 30/57 高精度数减整型数，假设高精度数小于整型，把高精度转化高精度数减整型数，假设高精度数小于整型，把高精度转化为整型直接减。这只讨论高精度数大于整型。为整型直接减。这只讨论高精度数大于整型。 将高精度数的对应位同将高精度数的对应位同 x 对应位相减，再进展退位。对应位相减，再进展退位。 memcpy(tmp, a, sizeof(tmp); int l = 1; while (x) tmpl -= x % 10, x /= 10, l+; for (int i = 1; i = tmp0; i+) if (tmpi 1

29、) tmp0-; memcpy(b, tmp, sizeof(b); 31/57斐波那契数列的准确计算斐波那契数列的准确计算 问题描画：试准确求出斐波那契数列的第问题描画：试准确求出斐波那契数列的第n 项。项。斐波那契数列的定义：斐波那契数列的定义：120111nnnffnfff ，给出给出n=61时的数，如下：时的数，如下：1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946、17711、28657、46368、75025、123、196418、317811、514229、832040、1346269

30、、2178309、3524578、5702887、9227465、14930352、24157817、39088169、63245986、102334155、165580141、267914296、433494437、701408733、1134903170、1836311903、2971215073、4807526976、7778742049、12586269025、20365011074、32951280099、53316291173、86267571272、583862445、225851433717、365435296162、591286729879、956722026041、1548

31、008755920、2504730781961、405273953788132/57斐波那契数列的准确计算斐波那契数列的准确计算 来看一个加法过程：来看一个加法过程：1548008755920+ 25047307819614052739537881为了作多位准确计算，设置为了作多位准确计算，设置a、b、c 三个数组。三个数组。 a0、b0存相邻两项的个位数字，存相邻两项的个位数字， a1、b1存储两项的存储两项的十位数字，其他类推。十位数字，其他类推。 1、算法分析、算法分析33/57斐波那契数列的准确计算斐波那契数列的准确计算 同一位求和同一位求和: ci=ai+bi+h，其中，其中h 为前

32、一位相加为前一位相加的进位数。这里得到的数的进位数。这里得到的数ci能够超越一位，求出其能够超越一位，求出其进位数进位数h=ci/l 0作为下一位相加的进位数，并让作为下一位相加的进位数，并让ci=ci%10。从。从i=0至至m求和全部完成后，即得到一求和全部完成后，即得到一个新项，把个新项，把b数组赋给数组赋给a数组，数组，c 数组赋给数组赋给b数组，为数组，为继续求下一项作预备。继续求下一项作预备。 当己求出第当己求出第n项，去掉项，去掉c数组的高位数组的高位0后从高位至低位后从高位至低位依次打印各位即为求得的数列第依次打印各位即为求得的数列第n 项。项。 34/57高精度数加高精度数高精

33、度数加高精度数 对应位相加，最后一致进位对应位相加，最后一致进位 memset(tmp, 0, sizeof(tmp); int l = max(a0, b0); for (int i = 1; i = l; i+) tmpi = ai + bi; l+; for (int i = 1; i 9) tmpi + 1+;tmpi - = 10; while (tmpl = 0 & l 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c);35/57斐波那契数列的准确计算斐波那契数列的准确计算 #include #include #define N 1000i

34、nt aN,bN,cN;int main(void) int h,i,j,n,k; while(scanf(%d,&n)=1) memset(a,0,sizeof(a); memset(b,0,sizeof(a); memset(c,0,sizeof(a); a0=b0=1;/赋初值赋初值 k=1;/开场时是开场时是1位数，用作循环上界位数，用作循环上界 for(i=2;i=n;i+)/一个一个运算一个一个运算 h=0; /开场时进位数为开场时进位数为0 for(j=0;j0) /最后一次单独处置最后一次单独处置 cj=h; k+;/位数添加位数添加 for(j=0;j=0;j-) /

35、输出输出 printf(%d,bj); printf(n); return 0;37/57大整数乘法大整数乘法 /ShowProblem.aspx?ProblemID=1092 Description 任给两个长度不超越任给两个长度不超越100位的大整数，求两个数相乘的准位的大整数，求两个数相乘的准确结果。确结果。 Input 此题有多组输入数据。第一行是输入数据的组数此题有多组输入数据。第一行是输入数据的组数T，每组，每组数据有两行，分别是两个非负的大整数，当数不为数据有两行，分别是两个非负的大整数，当数不为0时，不时，不会出现首位为会出现首位为0的情形。的情形。1

36、=T=1;i-)/把数字倒过来，使得高位在下把数字倒过来，使得高位在下标在的位置标在的位置 a i=sl-i-0;40/57n 在程序中，为了更好的保管大整数，用了一个构在程序中，为了更好的保管大整数，用了一个构造体：造体：n typedef structn n int numberLEN;n int len;n digit;n 用构造体用构造体a,b表示两个乘数，用表示两个乘数，用c表示积。计算的表示积。计算的过程根本上和小学生列竖式做乘法一样。为编程方过程根本上和小学生列竖式做乘法一样。为编程方便，个数存储在数组最低位，而不是下标高的位置。便，个数存储在数组最低位，而不是下标高的位置。在程

37、序中，可以不急于处置进位，而将进位问题留在程序中，可以不急于处置进位，而将进位问题留待最后一致处置。待最后一致处置。n 现以现以 83549 为例来阐明程序的计算过程。为例来阐明程序的计算过程。解题思绪解题思绪41/57先算先算8359。59 得到得到45 个个1，39 得到得到27 个个10，89 得到得到72 个个100。由于不急于处置进位，所以。由于不急于处置进位，所以8359 算完后，结果如下：算完后，结果如下：接下来算接下来算45。此处。此处45 的结果代表的结果代表20 个个10，因此要，因此要 c1+=20，变为：，变为：再下来算再下来算43。此处。此处43 的结果代表的结果代表

38、12 个个100，因此要，因此要 c2+= 12，变为：，变为：42/57最后算最后算 48。此处。此处48 的结果代表的结果代表 32 个个1000，因此要，因此要 c3+= 32，变为：，变为：乘法过程终了。接下来从乘法过程终了。接下来从 c0开场向高位逐位处置进位问题。开场向高位逐位处置进位问题。c0留下留下5，把，把4 加到加到c1上，上，c1变为变为51 后，应留下后，应留下1，把，把5 加到加到c2上上最终使得最终使得c 里的每个元素都是里的每个元素都是1 位数，结果就位数，结果就算出来了：算出来了：规律：一个数的第规律：一个数的第i 位和另一个数的第位和另一个数的第j 位相乘所得

39、的数，一位相乘所得的数，一定是要累加到结果的第定是要累加到结果的第i+j 位上。这里位上。这里i, j 都是从右往左，从都是从右往左，从0 开场数。开场数。43/574、参考程序#include #include #define LEN 210typedef struct/记录数的长度，减少循环记录数的长度，减少循环 int numberLEN; int len; digit;void multiply(digit *a, digit *b, digit *c);int main(void) char sLEN; int i,k,n,T; digit a,b,c; scanf(%d,&

40、T);/读入数据个数读入数据个数 getchar();/吸收回车符吸收回车符 for(n=0;nT;n+) gets(s); a.len=strlen(s); for(i=0;ia.len;i+)/把数字倒过来，使得高位在下标在的位置把数字倒过来，使得高位在下标在的位置 a.numberi=sa.len-i-1-0;44/574、参考程序 gets(s); b.len=strlen(s); for(i=0;i=0;i-) printf(%d,c.numberi); printf(n); return 0;/a,b是乘数，是乘数，c是积是积void multiply(digit *a, digi

41、t *b, digit *c) int i,j,t; if(a-len=1 & a-number0=0) | (b-len=1 & b-number0=0)/其中一个数为其中一个数为0 c-len=1; c-number0=0; return; 45/574、参考程序 c-len=a-len+b-len;/先乘，后进位先乘，后进位 memset(c-number,0,c-len*sizeof(int);/清零清零 for(i = 0; i len; i+) /逐位作乘法逐位作乘法 for(j = 0; j len; j+) c-numberi + j += a-numberj

42、* b-numberi; for(i = 0; i len-1; i+)/一致进位一致进位 if(c-numberi = 10) c-numberi+1+=c-numberi/10; c-numberi%=10; /积的最大长度为两数长度之和，最小为之和减积的最大长度为两数长度之和，最小为之和减1 if(c-numberi = 0) c-len-;46/57大整数除法大整数除法1、链接地址、链接地址 poj.grids/problem?id=27372、问题描画、问题描画 求两个大的正整数相除的商求两个大的正整数相除的商 输入数据输入数据 第第1 行是测试数据的组数行是测试数据的组数n，每组测

43、试数据占，每组测试数据占2 行，第行，第1 行是被除数，第行是被除数，第2 行是除数。每组测试数据之间有一个空行，行是除数。每组测试数据之间有一个空行，每行数据不超越每行数据不超越100 个字符个字符 输出要求输出要求 n 行，每组测试数据有一行输出是相应的整数商行，每组测试数据有一行输出是相应的整数商47/57 输入样例输入样例32405337312963373359009260457742057439230496493930355595797660791082739646298719258531870175258442993116087037290707924897109501250979

44、0550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451 输出样例输出样例01000000000000000000000000000000540965677509785089568705679806897093454654657567676867843543534548/57n 根本的思想是反复做减法，看看从被除数里最多能减去多根本的思想是反复做减法，看看从被除数里最多能减去多少个除数，

45、商就是多少。一个一个减显然太慢，如何减得更少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以快一些呢？以7546 除以除以23 为例来看一下：开场商为为例来看一下：开场商为0。先。先减去减去23 的的100 倍，就是倍，就是2300，发现够减，发现够减3 次，余下次，余下646。于是商的值就添加于是商的值就添加300。然后用。然后用646 减去减去230，发现够减，发现够减2 次，余下次，余下186，于是商的值添加，于是商的值添加20。最后用。最后用186 减去减去23，够减够减8 次，因此最终商就是次，因此最终商就是328。n 所以此题的中心是要写一个大整数的减法函数，然后反复

46、所以此题的中心是要写一个大整数的减法函数，然后反复调用该函数进展减法操作。调用该函数进展减法操作。 计算除数的计算除数的10 倍、倍、100 倍的时倍的时候，不用做乘法，直接在除数后面补候，不用做乘法，直接在除数后面补0 即可。即可。3、解题思绪、解题思绪49/574、参考程序、参考程序n#include n#include n#define MAX_LEN 200nchar szLine1MAX_LEN + 10;nchar szLine2MAX_LEN + 10;nint an1MAX_LEN + 10; /被除数被除数, an10对应于个位对应于个位nint an2MAX_LEN + 1

47、0; /除数除数, an20对应于个位对应于个位nint aResultMAX_LEN + 10; /存放商，存放商，aResult0对应于个位对应于个位n/长度为长度为 nLen1 的大整数的大整数p1 减去长度为减去长度为nLen2 的大整数的大整数p2n/结果放在结果放在p1 里，前往值代表结果的长度里，前往值代表结果的长度n/如不够减前往如不够减前往-1，正好减完前往，正好减完前往 0nint Substract( int * p1, int * p2, int nLen1, int nLen2)nn int i;n if( nLen1 = 0; i - ) n n if( p1i p

48、2i ) break; /p1p2n else if( p1i p2i ) return -1; /p1p2n n n for( i = 0; i =nLen2 时，时，p2i 0n p1i -= p2i; n if( p1i = 0 ; i- )n if( p1i )/找到最高位第一个不为找到最高位第一个不为0n return i + 1;n return 0;/全部为全部为0，阐明两者相等，阐明两者相等n51/574、参考程序nint main()nn int t, n;n scanf(%d, &n);n for( t = 0; t = 0 ; i -)n an1j+ = szLi

49、ne1i - 0;n int nLen2 = strlen(szLine2);n for( j = 0, i = nLen2 - 1;i = 0 ; i -)n an2j+ = szLine2i - 0;n if( nLen1 0)n n for( i = nLen1 -1; i = nTimes; i - ) n an2i = an2i-nTimes;/朝高位挪动朝高位挪动n for( ; i = 0; i-)/低位补低位补0n an2i = 0;n nLen2 = nLen1;n n for( j = 0 ; j = 0) n n nLen1 = nTmp;n aResultnTimes-

50、j+; /每胜利减一次，那么将商的相应位加每胜利减一次，那么将商的相应位加1n n 53/57参考程序参考程序n /下面输出结果，先跳过高位下面输出结果，先跳过高位0n for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - );n if( i = 0)n for( ; i=0; i-)n printf(%d, aResulti);n elsen printf(0);n printf(n);n n return 0;n54/57麦森数麦森数1、链接地址、链接地址 poj.grids/problem?id=27062、问题描画、问题描画 形如形如

51、2P-1 的素数称为麦森数，这时的素数称为麦森数，这时P 一定也是个素数。一定也是个素数。但反过来不一定，即假设但反过来不一定，即假设P 是个素数。是个素数。2P-1 不一定也是不一定也是素数。到素数。到2019 年底，人们已找到了年底，人们已找到了37 个麦森数。最大的个麦森数。最大的一个是一个是P=3027，它有，它有909526 位。麦森数有许多重要运用，位。麦森数有许多重要运用，它与完全数亲密相关。它与完全数亲密相关。 他的义务：输入他的义务：输入P (1000P3100000) , 计算计算2p-1 的位的位数和最后数和最后500 位数字用十进制高精度数表示位数字用十进制高精度数表示

52、55/57 输入数据输入数据 只包含一个整数只包含一个整数P(1000P0，思索，思索p 的二进制方式，那么不难得的二进制方式，那么不难得到：到：n这里，这里，ai 要么是要么是1，要么是，要么是0。3、解题思绪、解题思绪0121012122222nnnpaaaa 58/57n 因此：因此：n 计算计算2p 的方法就是：先将结果的值设为的方法就是：先将结果的值设为1，计算，计算21。假设。假设a0 值为值为1，那么结果乘以，那么结果乘以21；计算；计算22，假设假设a1 为为1，那么结果乘以，那么结果乘以22；计算；计算24，假设，假设a2 为为1，那么结果乘以，那么结果乘以24；总之，第总之

53、，第i 步步(i 从从0 到到n，an 是是1)就计算就计算22i，假设，假设ai 为为1，那么结果就，那么结果就乘以乘以22i。每次由。每次由22i22i就能算出就能算出22(i+1)。由于由于p能够很大，所以上面的乘法都应该运用高精能够很大，所以上面的乘法都应该运用高精度计算。由于标题只需求输出度计算。由于标题只需求输出500 位，所以这些乘位，所以这些乘法都是只须算出末尾的法都是只须算出末尾的500 即可。即可。解题思绪解题思绪101122242222222nnnaaaap 59/57n在前面的高精度计算中，我们用数组来存放大整在前面的高精度计算中，我们用数组来存放大整数，数组的一个元素

54、对应于十进制大整数的一位。数，数组的一个元素对应于十进制大整数的一位。此题假设也这样做，就会超时。为了加快计算速度，此题假设也这样做，就会超时。为了加快计算速度，可以用一个数组元素对应于大整数的可以用一个数组元素对应于大整数的4 位，即将大位，即将大整数表示为整数表示为10000 进制，而数组中的每一个元素就进制，而数组中的每一个元素就存放存放10000 进制数的进制数的1 位。例如，用位。例如，用int 型数组型数组 a 来存放整数来存放整数6373384，那么只需两个数组元素就可，那么只需两个数组元素就可以了，以了，a0=3384, a1=637。n由于只需求结果的最后由于只需求结果的最后

55、500 位数字，所以我们不位数字，所以我们不需求计算完好的结果，只需算出最后需求计算完好的结果，只需算出最后500 位即可。位即可。由于用每个数组元素存放十进制大整数的由于用每个数组元素存放十进制大整数的4 位，所位，所以此题中的数组最多只需求以此题中的数组最多只需求125 个元素。个元素。解题思绪解题思绪60/574、参考程序n#include n#include n#define LEN 125 /每数组元素存放每数组元素存放4 位，数组最多需求位，数组最多需求125 个元素个元素n#include n/计算高精度乘法计算高精度乘法 a * b, 结果的末结果的末500 位放在位放在a 中

56、中nvoid Multiply(int* a, int* b)nn int i, j;n int nCarry; /存放进位存放进位n int nTmp;n int cLEN; /存放结果的末存放结果的末500 位位n memset(c, 0, sizeof(int) * LEN);n for (i=0;iLEN;i+) n n nCarry=0;n for (j=0;jLEN-i;j+) n n nTmp=ci+j+aj*bi+nCarry;n ci+j=nTmp%10000;n nCarry=nTmp/10000;n n n memcpy( a, c, LEN*sizeof(int);n61/574、参考程序nint main(void)nn int i;n int p;n int anPowLEN; /存放不断增长的存放不断增长的2 的次幂的次幂n in