6 模拟与高精度计算

1、第六讲模拟与高精度计算ACM算法与程序设计现实中的有些问题难以找到公式或规律来解决。只能按照一定步骤不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决问题时的行为即可。这一类的问题可以称之为“模拟题”。摘花生 问题描述 鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。 有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练

2、多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件： (1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；(2) 从一棵植株跳到前后左右与之相邻的另一棵植株； (3) 采摘一棵植株下的花生； (4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。 例如在图2所示的

3、花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。 输入格式 输入的第一行包括一个整数T，表示数据组数。 每组输入的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 = M, N = 50），多多采花生的限定时间为K（0 = K = 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 = Pij = 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下

4、没有花生。 输出要求 输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。 样例输入 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 找规律得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。 结果只能是做了才知道。即走进花生地每次要采下一株花生之前，先计算一下剩下的时间够不够走到那株花生，采摘，并从那株花生走回到路上。如果时问够则走过去采摘；如果时间不够，则采摘活动到此结束。 设二维数组aField存放

5、花生地的信息。然而，用aField00还是aField11对应花生地的左上角是值得思考一下的。因为从地里到路上还需要1个单位时间，题目中的坐标又都是从1开始。所以若aField11对应花生地的左上角，则从aFieldij点回到路上所需时间就是i，这样更为方便和自然，不易出错。解题思路参考程序#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,

6、 &N, &K); /花生地的左上角对应的数组元素是aField11，路的纵坐标是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代表纵坐标，开始是在路上，所以初值为0 while(nTotalTimeK) /如果还有时间 int nMax=0, nMaxi, nMaxj; /最大的花生数目， /及其所处的位置 for(int

7、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处，再进人花生地 / 下一行看剩余时间是否足够走到(nMaxi，nMaxj)处， /摘取花生，并回到路上 if(nTotaITime+nMaxi+1+abs(nMaxi-nCuri) +abs(nMa

8、xj-nCurj) =K) / 下一行加上走到新位置，以及摘花生的时问 nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; /走到新的位置 nTotaiPeanuts+=aFieldnMaxinMaxj; aFieldnMaxinMaxj=0; /摘走花生 else break； printf(“%dn”, nTotalPeanuts); 常见问题这个题目应该仔细阅读。往往没有看到每次只能拿剩下花生株中最大的，而是希望找到一种在规定时间内能够拿最多花生的组合，把题目变成了另外一道题。没有读到没有两

9、株花生株的花生数目相同”的条件，因此把题目复杂化了。这个题目是假设猴子在取花生的过程中不会回到大路上，而有些同学思考是否可能在中间回到大路上，因为题目没说在大路上移动要花时间，所以有可能中途出来再进去摘的花生更多。本题的解法虽然直观但是有一个弊端就是每次在寻找下一个最大花生植株时，都要遍历整个矩阵，效率不高。用什么办法才能高效率地找到下一个最大花生植株?显示器1、链接地址 2、问题描述 你的一个朋友买了一台电脑。他以前只用过计算器，因为电脑的显示器上显示的数字的样子和计算器是不一样，所以当他使用电脑的时候会比较郁闷。为了帮助他，你决定写一个程序把在电脑上的数字显示得像计算器上一样。 输入数据

10、输入包括若干行，每行表示一个要显示的数。每行有两个整数s 和n (1 = s = 10, 0 =n= 99999999)，这里n 是要显示的数，s 是要显示的数的尺寸。如果某行输入包括两个0，表示输入结束。这行不需要处理。 输出要求 显示的方式是：用s 个-表示一个水平线段，用s 个|表示一个垂直线段。这种情况下，每一个数字需要占用s+2 列和2s+3 行。另外，在两个数字之间要输出一个空白的列。在输出完每一个数之后，输出一个空白的行。注意：输出中空白的地方都要用空格来填充。 输入样例2 123453 678900 0 输出样例一个计算器上的数字显示单元，可以看作由以下编号从1 到7 的7 个

11、笔画组成： 3、解题思路 那么，我们可以说，数字8 覆盖了所有的笔画，数字7 覆盖笔画1、3 和6，而数字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。如果某个数字d 没有覆盖某个笔画m (m = 17)，那么，输出数字d 的笔画m 的时候，就应该都输出空格；如果覆盖了笔画m，则输出s 个-或s 个|，这取决

12、于笔画m 是横的还是竖的。解题思路由上思路，解决这道题目的关键，就在于如何记录每个数字都覆盖了哪些笔画。实际上，如果我们记录的是每个笔画都被哪些数字覆盖，则程序实现起来更为容易。一个笔画被哪些数字所覆盖，可以用一个数组来记录，比如记录笔画1 覆盖情况的数组如下：char n111 = - - -;其中，n1i(i = 09) 代表笔画1 是否被数字i 覆盖。如果是，则n1i 为-，如果否，则n1i为空格。上面的数组的值体现了笔画1 被数字0, 2, 3, 5, 6, 7, 8, 9 覆盖。对于竖向的笔画2，由字符 | 组成，则记录其覆盖情况的数组如下：char n211 = | | |;该数组

13、的值体现了笔画2 被数字0, 4, 5, 6, 8, 9 覆盖。解题思路4、参考程序#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 被数字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 覆盖cha

14、r n711=- - - -;/笔画7 被数字0,2,3,5,6,8,9 覆盖int main(void) int s; char szNumber20; int nDigit , nLength, i , j , k; while(1) scanf( %d%s, &s, szNumber); if (s = 0) break; nLength = strlen(szNumber); for (i = 0 ; i nLength ; i+) /输出所有数字的笔画1 nDigit = szNumberi - 0; printf( ); for (j = 0 ; j s ; j+) /一个笔画由s

15、 个字符组成 printf(%c, n1nDigit); printf( );/两个空格 printf(n);4、参考程序 for (i = 0 ; i s ; i+) /输出所有数字的笔画2 和笔画3 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n2nDigit); for (k = 0 ; k s ; k+) printf( ); /笔画2 和笔画3 之间的空格 printf(%c , n3nDigit);/有一个空格 printf(n); for (i = 0 ; i nLength ; i+) /输出所

16、有数字的笔画4 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n4nDigit); printf( );/两个空格 printf(n);4、参考程序4、参考程序 for (i = 0 ; 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(%

17、c , n6nDigit);/有一个空格 printf(n); for (i = 0 ; i nLength ; i+) /输出所有数字的笔画7 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j 1) l-; a0 = l; 当 ai上的数据小于 0 的时候，就要由高位退位了。因为该数组中下标越大，位数越高，故当 ai位小于 0时，ai + 1位退位的操作 （以十进制为例）为： ai + 1-; ai += 10;如果 aa0位等于 0，在退位的同时就要考虑a0的值的改变了。此时要减小a0，直到达到准确位数。 while (aa0 = 0 &

18、a0 1) a0-; 高精度数加整型数算法： 将整型加到 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) tmp0 = l; memcpy(b, tmp, sizeof(b); 高精度数减整型数，若高精度数小于整型，把高精度转化为整型直接减

19、。这只讨论高精度数大于整型。 将高精度数的对应位同 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) tmp0-; memcpy(b, tmp, sizeof(b); 斐波那契数列的准确计算 问题描述：试准确求出斐波那契数列的第n 项。斐波那契数列的定义：给出n=61时的数，如下：1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、15

20、97、2584、4181、6765、10946、17711、28657、46368、75025、121393、196418、317811、514229、832040、1346269、2178309、3524578、5702887、9227465、14930352、24157817、39088169、63245986、102334155、165580141、267914296、433494437、701408733、1134903170、1836311903、2971215073、4807526976、7778742049、12586269025、20365011074、32951280099、

21、53316291173、86267571272、5、225851433717、365435296162、591286729879、956722026041、1548008755920、25、41斐波那契数列的准确计算 来看一个加法过程：1548008755920+ 2541为了作多位准确计算，设置a、b、c 三个数组。 a0、b0存相邻两项的个位数字， a1、b1存储两项的十位数字，其余类推。 1、算法分析斐波那契数列的准确计算 同一位求和: ci=ai+bi+h，其中h 为前一位相加的进位数。这里得到的数ci可能超过一位，求出其进位数h=ci/l 0作为下一位相加的进位数，并让ci=ci%1

22、0。从i=0至m求和全部完成后，即得到一个新项，把b数组赋给a数组，c 数组赋给b数组，为继续求下一项作准备。 当己求出第n项，去掉c数组的高位0后从高位至低位依次打印各位即为求得的数列第n 项。 高精度数加高精度数对应位相加，最后统一进位 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; me

23、mcpy(c, tmp, sizeof(c);斐波那契数列的准确计算 #include #include #define N 1000int 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+;

24、/位数增加 for(j=0;j=0;j-) /输出 printf(%d,bj); printf(n); return 0;大整数乘法 Description 任给两个长度不超过100位的大整数，求两个数相乘的精确结果。 Input 本题有多组输入数据。第一行是输入数据的组数T，每组数据有两行，分别是两个非负的大整数，当数不为0时，不会出现首位为0的情形。1=T=1;i-)/把数字倒过来，使得高位在下标在的位置 a i=sl-i-0; 在程序中，为了更好的保存大整数，用了一个结构体： typedef struct int numberLEN; int len; digit; 用结构体a,b表示两

25、个乘数，用c表示积。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，个数存储在数组最低位，而不是下标高的位置。在程序中，可以不急于处理进位，而将进位问题留待最后统一处理。 现以 83549 为例来说明程序的计算过程。解题思路先算8359。59 得到45 个1，39 得到27 个10，89 得到72 个100。由于不急于处理进位，所以8359 算完后，结果如下：接下来算45。此处45 的结果代表20 个10，因此要 c1+=20，变为：再下来算43。此处43 的结果代表12 个100，因此要 c2+= 12，变为：最后算 48。此处48 的结果代表 32 个1000，因此要 c3+= 32

26、，变为：乘法过程完毕。接下来从 c0开始向高位逐位处理进位问题。c0留下5，把4 加到c1上，c1变为51 后，应留下1，把5 加到c2上最终使得c 里的每个元素都是1 位数，结果就算出来了：规律：一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i+j 位上。这里i, j 都是从右往左，从0 开始数。4、参考程序#include #include #define LEN 210typedef struct/记录数的长度，减少循环 int numberLEN; int len; digit;void multiply(digit *a, digit *b, digit *

27、c);int main(void) char sLEN; int i,k,n,T; digit a,b,c; scanf(%d,&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;4、参考程序 gets(s); b.len=strlen(s); for(i=0;i=0;i-) printf(%d,c.numberi); printf(n); return 0;/a,b是乘数，c是积voi

28、d multiply(digit *a, digit *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; 4、参考程序 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 * b-num

29、beri; 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-;大整数除法1、链接地址 2、问题描述 求两个大的正整数相除的商 输入数据 第1 行是测试数据的组数n，每组测试数据占2 行，第1 行是被除数，第2 行是除数。每组测试数据之间有一个空行，每行数据不超过100 个字符 输出要求 n 行，每组测试数据有一行输出是相应的整数商 输入样例3243733592649393

30、64629871925853429931167924897197894100000001000000000054859865465756767686784354353451 输出样例01000000005485986546575676768678435435345 基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546 除以23 为例来看一下：开始商为0。先减去23 的100 倍，就是2300，发现够减3 次，余下646。于是商的值就增加300。然后用646 减去230，发现够减2 次，余下186，于是商的值增加20。最后用1

31、86 减去23，够减8 次，因此最终商就是328。 所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。 计算除数的10 倍、100 倍的时候，不用做乘法，直接在除数后面补0 即可。3、解题思路4、参考程序#include #include #define MAX_LEN 200char szLine1MAX_LEN + 10;char szLine2MAX_LEN + 10;int an1MAX_LEN + 10; /被除数, an10对应于个位int an2MAX_LEN + 10; /除数, an20对应于个位int aResultMAX_LEN + 10; /存放

32、商，aResult0对应于个位/长度为 nLen1 的大整数p1 减去长度为nLen2 的大整数p2/结果放在p1 里，返回值代表结果的长度/如不够减返回-1，正好减完返回 0int Substract( int * p1, int * p2, int nLen1, int nLen2) int i; if( nLen1 = 0; i - ) if( p1i p2i ) break; /p1p2 else if( p1i p2i ) return -1; /p1p2 for( i = 0; i =nLen2 时，p2i 0 p1i -= p2i; if( p1i = 0 ; i- ) if(

33、p1i )/找到最高位第一个不为0 return i + 1; return 0;/全部为0，说明两者相等4、参考程序int main() int t, n; scanf(%d, &n); for( t = 0; t = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for( j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; if( nLen1 0) for( i = nLen1 -1; i = nTimes; i - ) an2i = an2i-nTimes

34、;/朝高位移动 for( ; i = 0; i-)/低位补0 an2i = 0; nLen2 = nLen1; for( j = 0 ; j = 0) nLen1 = nTmp; aResultnTimes-j+; /每成功减一次，则将商的相应位加1 参考程序 /下面输出结果，先跳过高位0 for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - ); if( i = 0) for( ; i=0; i-) printf(%d, aResulti); else printf(0); printf(n); return 0;麦森数1、链接地址 2、问题描述

35、形如2P-1 的素数称为麦森数，这时P 一定也是个素数。但反过来不一定，即如果P 是个素数。2P-1 不一定也是素数。到1998 年底，人们已找到了37 个麦森数。最大的一个是P=3021377，它有909526 位。麦森数有许多重要应用，它与完全数密切相关。 你的任务：输入P (1000P3100000) , 计算2p-1 的位数和最后500 位数字（用十进制高精度数表示） 输入数据 只包含一个整数P(1000P0，考虑p 的二进制形式，则不难得到：这里，ai 要么是1，要么是0。3、解题思路 因而： 计算2p 的办法就是：先将结果的值设为1，计算21。如果a0 值为1，则结果乘以21；计算

36、22，如果a1 为1，则结果乘以22；计算24，如果a2 为1，则结果乘以24；总之，第i 步(i 从0 到n，an 是1)就计算22i，如果ai 为1，则结果就乘以22i。每次由22i22i就能算出22(i+1)。由于p可能很大，所以上面的乘法都应该使用高精度计算。由于题目只要求输出500 位，所以这些乘法都是只须算出末尾的500 即可。解题思路在前面的高精度计算中，我们用数组来存放大整数，数组的一个元素对应于十进制大整数的一位。本题如果也这样做，就会超时。为了加快计算速度，可以用一个数组元素对应于大整数的4 位，即将大整数表示为10000 进制，而数组中的每一个元素就存放10000 进制数

37、的1 位。例如，用int 型数组 a 来存放整数，那么只需两个数组元素就可以了，a0=3384, a1=637。由于只要求结果的最后500 位数字，所以我们不需要计算完整的结果，只需算出最后500 位即可。因为用每个数组元素存放十进制大整数的4 位，所以本题中的数组最多只需要125 个元素。解题思路4、参考程序#include #include #define LEN 125 /每数组元素存放4 位，数组最多需要125 个元素#include /计算高精度乘法 a * b, 结果的末500 位放在a 中void Multiply(int* a, int* b) int i, j; int nC

38、arry; /存放进位 int nTmp; int cLEN; /存放结果的末500 位 memset(c, 0, sizeof(int) * LEN); for (i=0;iLEN;i+) 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);4、参考程序int main(void) int i; int p; int anPowLEN; /存放不断增长的2 的次幂 int aResultLEN; /存放最终结果的末500 位 scanf(%d, & p); printf(“%dn”, (int)(p*log10(2.0)+1); /下面将2 的次幂初始化为2(20)(ab 表示a 的b 次方)， / 最终结果初始化为1 anPow0=2; aResult0=1; for (i=1;i0) /下面计算2 的p 次方 / p = 0 则说明p 中的有效位都用过了，不需再算下去 if ( p & 1 ) /判断此时p 中最低位是否为1 Multiply(aResult, anPow); p=1; Multiply(anPow,