模拟与高精度计算.ppt

第六讲 模拟与高精度计算 ACM算法与程序设计 数学科学学院：汪小平 2/57 n 现实中的有些问题难以找到公式或规律来解决 。只能按照一定步骤不停地做下去，最后才能得 到答案。这样的问题，用计算机来解决十分合适 ，只要能让计算机模拟人在解决问题时的行为即 可。这一类的问题可以称之为“模拟题”。 3/57 摘花生 /practice/2950 问题描述 鲁宾逊先生有一只宠物猴，名叫 多多。这天，他们两个正沿着乡间小 路散步，突然发现路边的告示牌上贴 着一张小小的纸条：“欢迎免费品尝 我种的花生！熊字”。 鲁宾逊先生和多多都很开心，因 为花生正是他们的最爱。在告示牌背 后，路边真的有一块花生田，花生植 株整齐地排列成矩形网格（如图1） 。 4/57 l 有经验的多多一眼就能看出，每棵花生植株下的花生有多 少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最 多的植株，去采摘它的花生；然后再找出剩下的植株里花生 最多的，去采摘它的花生；依此类推，不过你一定要在我限 定的时间内回到路边。” l 我们假定多多在每个单位时间内，可以做下列四件事情中 的一件： (1) 从路边跳到最靠近路边（即第一行）的某棵花生植株； (2) 从一棵植株跳到前后左右与之相邻的另一棵植株； (3) 采摘一棵植株下的花生； (4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间 内，多多最多可以采到多少个花生？注意可能只有部分植株 下面长有花生，假设这些植株下的花生个数各不相同。 5/57 l 例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示 的路线，多多在21个单位时间内，最多可以采到37个花生。 6/57 输入格式 输入的第一行包括一个整数T，表示数据组数。 每组输入的第一行包括三个整数，M, N和K，用空格隔开；表示 花生田的大小为M * N（1 #include #include #include int T, M, N, K; #define MAX_NUM 55 int aFieldMAX_NUM MAX_NUM; int main() scanf(“%d”, for(int t=0; t #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 覆盖 char n711=“- - - -“;/笔画7 被数字0,2,3,5,6,8,9 覆盖 int main(void) int s; char szNumber20; int nDigit , nLength, i , j , k; 19/57 while(1) scanf( “%d%s“, if (s = 0) break; nLength = strlen(szNumber); for (i = 0 ; i #include #define N 1000 int aN,bN,cN; int main(void) int h,i,j,n,k; while(scanf(“%d“, memset(b,0,sizeof(b); memset(c,0,sizeof(c); a0=b0=1;/赋初值 k=1;/开始时是1位数，用作循环上界 for(i=2;i0) /最后一次单独处理 cj=h; k+;/位数增加 for(j=0;j=0;j-) /输出 printf(“%d“,bj); printf(“n“); return 0; 30/57 大整数乘法 /problem.php?pid=1092 Description 任给两个长度不超过100位的大整数，求两个数相乘的精 确结果。 Input 本题有多组输入数据。第一行是输入数据的组数T，每组 数据有两行，分别是两个非负的大整数，当数不为0时，不 会出现首位为0的情形。1 #include #define LEN 210 typedef 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“,/读入数据个数 getchar();/吸收回车符 for(n=0;n=0;i-) printf(“%d“,c.numberi); printf(“n“); return 0; /a,b是乘数，c是积 void multiply(digit *a, digit *b, digit *c) int i,j,t; if(a-len=1 c-number0=0; return; 37/57 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-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-; 38/57 大整数除法 1、链接地址 /practice/2737 2、问题描述 求两个大的正整数相除的商 输入数据 第1 行是测试数据的组数n，每组测试数据占2 行 ，第1 行是被除数，第2 行是除数。每组测试数据之 间有一个空行，每行数据不超过100 个字符 输出要求 n 行，每组测试数据有一行输出是相应的整数商 39/57 输入样例 3 2405337312963373359009260457742057439230496493930355595797660791082739646 2987192585318701752584429931160870372907079248971095012509790550883793197894 10000000000000000000000000000000000000000 10000000000 5409656775097850895687056798068970934546546575676768678435435345 1 输出样例 0 1000000000000000000000000000000 5409656775097850895687056798068970934546546575676768678435435345 40/57 n 基本的思想是反复做减法，看看从被除数里最多能减去多 少个除数，商就是多少。一个一个减显然太慢，如何减得更 快一些呢？以7546 除以23 为例来看一下：开始商为0。先 减去23 的100 倍，就是2300，发现够减3 次，余下646。 于是商的值就增加300。然后用646 减去230，发现够减2 次，余下186，于是商的值增加20。最后用186 减去23， 够减8 次，因此最终商就是328。 n 所以本题的核心是要写一个大整数的减法函数，然后反复 调用该函数进行减法操作。 计算除数的10 倍、100 倍的时 候，不用做乘法，直接在除数后面补0 即可。 3、解题思路 41/57 4、参考程序 n#include n#include n#define MAX_LEN 200 nchar szLine1MAX_LEN + 10; nchar szLine2MAX_LEN + 10; nint an1MAX_LEN + 10; /被除数, an10对应于个位 nint an2MAX_LEN + 10; /除数, an20对应于个位 nint aResultMAX_LEN + 10; /存放商，aResult0对应于个位 n/长度为 nLen1 的大整数p1 减去长度为nLen2 的大整数p2 n/结果放在p1 里，返回值代表结果的长度 n/如不够减返回-1，正好减完返回 0 nint Substract( int * p1, int * p2, int nLen1, int nLen2) n n int i; n if( nLen1 = 0; i - ) n n if( p1i p2i ) break; /p1p2 n else if( p1i =nLen2 时，p2i 0 n p1i -= p2i; n if( p1i = 0 ; i- ) n if( p1i )/找到最高位第一个不为0 n return i + 1; n return 0;/全部为0，说明两者相等 n 43/57 4、参考程序 nint main() n n int t, n; n scanf(“%d“, n for( t = 0; t = 0 ; i -) n an1j+ = szLine1i - 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-)/低位补0 n an2i = 0; n nLen2 = nLen1; n n for( j = 0 ; j = 0) n n nLen1 = nTmp; n aResultnTimes-j+; /每成功减一次，则将商的相应位加1 n n 45/57 参考程序 n /下面输出结果，先跳过高位0 n for( i = MAX_LEN ; (i = 0) i - ); n if( i = 0) n for( ; i=0; i-) n printf(“%d“, aResulti); n else n printf(“0“); n printf(“n“); n n return 0; n 46/57 麦森数 1、链接地址 /problem?id=2706 2、问题描述 形如2P-1 的素数称为麦森数，这时P 一定也是个素数。但 反过来不一定，即如果P 是个素数。2P-1 不一定也是素数。到 1998 年底，人们已找到了37 个麦森数。最大的一个是 P=3021377，它有909526 位。麦森数有许多重要应用，它与完 全数密切相关。 你的任务：输入P (10000，考虑p 的二进制形式，则不难得到 ： n这里，ai 要么是1，要么是0。 3、解题思路 50/57 n 因而： n 计算2p 的办法就是：先将结果的值设为1，计算 21。如果a0 值为1，则结果乘以21；计算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 即可。 解题思路 51/57 n在前面的高精度计算中，我们用数组来存放大整 数，数组的一个元素对应于十进制大整数的一位。 本题如果也这样做，就会超时。为了加快计算速度 ，可以用一个数组元素对应于大整数的4 位，即将 大整数表示为10000 进制，而数组中的每一个元素 就存放10000 进制数的1 位。例如，用int 型数组 a 来存放整数6373384，那么只需两个数组元素就 可以了，a0=3384, a1=637。 n由于只要求结果的最后500 位数字，所以我们不 需要计算完整的结果，只需算出最后500 位即可。 因为用每个数组元素存放十进制大整数的4 位，所 以本题中的数组最多只需要125 个元素。 解题思路 52/57 4、参考程序 n#include n#include n#define LEN 125 /每数组元素存放4 位，数组最多需要125 个元素 n#include n/计算高精度乘法 a * b, 结果的末500 位放在a 中 nvoid Multiply(int* a, int* b) n n int i, j; n int nCarry; /存放进位 n int nTmp; n int cLEN; /存放结果的末500 位 n memset(c, 0, sizeof(int) * LEN); n for (i=0;i0) /下面计算2 的p 次方 n / p = 0 则说明p 中的有效位都用过了，不需再算下去 n if ( p n p=1; n Multiply(anPow, anPow); n 54/57 参考程序 n aResult0-; /2p-1 n /输出结果 n for (i=LEN-1;i=0;i-) n n if (i%25=12) n printf(“%02dn%02d“, aResulti/100, n aResulti%100); n else n n printf(“%04d“, aResulti); n if (i%25=0) n printf(“n“); n n n return 0; n 55/57 高精度计算课外练习 1、CDOJ：1193 Love is Persistence 2、Exponentiation (POJ：1001) Description Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems. This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 R 99.999 ) and n is an integer such that 0 n = 25. 56/57 Input The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n val