ACM高精计算解析.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,/33,第九讲,高精度计算,ACM,算法与程序设计,2,/33,大整数加法,1,、链接地址,Sample:,55555555555555555555,4,/33,首先要解决的就是存储,200,位整数的问题。显然，任何,C/C+,固有类型的变量都无法保存它。最直观的想法是可以用一个字符串来保存它。字符串本质上就是一个字符数组，因此为了编程更方便，我们也可以用数组,unsigned an200,来保存一个,200,位的整数，让,an0,存放个位数，,an1,存放十位数，,an2,存放百位数,那么如何实现两个大整数相加呢？方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到,10,则进位。也就是说，用,unsigned an1201,保存第一个数，用,unsigned an2200,表示第二个数，然后逐位相加，相加的结果直接存放在,an1,中。要注意处理进位。另外，,an1,数组长度定为,201,，是因为两个,200,位整数相加，结果可能会有,201,位。,实际编程时，不一定要费心思去把数组大小定得正好合适，稍微开大点也无所谓，以免不小心没有算准这个“正好合适”的数值，而导致数组小了，产生越界错误。,3,、解题思路,5,/33,4,、参考程序,#include,#include,#define MAX_LEN 200,int an1MAX_LEN+10;,int an2MAX_LEN+10;,char szLine1MAX_LEN+10;,char szLine2MAX_LEN+10;,int main(void),scanf(%s,szLine1);,scanf(%s,szLine2);,int i,j;,memset(an1,0,sizeof(an1);,memset(an2,0,sizeof(an2);,6,/33,4,、参考程序,int nLen1=strlen(szLine1);,for(j=0,i=nLen1-1;i=0;i-),an1j+=szLine1i0;,int nLen2=strlen(szLine2);,for(j=0,i=nLen2-1;i=0;i-),an2j+=szLine2i-0;,for(i=0;i=10),/,看是否要进位,an1i-=10;,an1i+1+;/,进位,for(i=MAX_LEN;(i=0),if(i=0),for(;i=0;i-),printf(%d,an1i);,else printf(0);,return 0;,7,/33,大整数乘法,1,、链接地址,an1200和unsigned an2200分别存放两个乘数，用aResult400来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200 位的数相乘，积最多会有400 位。an10,an20,aResult0都表示个位。,计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。,现以 83549 为例来说明程序的计算过程。,3,、解题思路,10,/33,先算,8359,。,59,得到,45,个,1,，,39,得到,27,个,10,，,89,得到,72,个,100,。由于不急于处理进位，所以,8359,算完后，结果如下：,3,、解题思路,接下来算,45,。此处,45,的结果代表,20,个,10,，因此要,c1+=20,，变为：,再下来算,43,。此处,43,的结果代表,12,个,100,，因此要,c2+=12,，变为：,11,/33,3,、解题思路,最后算,48,。此处,48,的结果代表,32,个,1000,，因此要,c3+=32,，变为：,乘法过程完毕。接下来从,c0,开始向高位逐位处理进位问题。,c0,留下,5,，把,4,加到,c1,上，,c1,变为,51,后，应留下,1,，把,5,加到,c2,上,最终使得,c,里的每个元素都是,1,位数，结果就算出来了：,规律：一个数的第,i,位和另一个数的第,j,位相乘所得的数，一定是要累加到结果的第,i+j,位上。这里,i,j,都是从右往左，从,0,开始数。,12,/33,4,、参考程序,#include,#include,#define MAX_LEN 200,int main(void),int i,j;,int len1,len2;,int aMAX_LEN+10,bMAX_LEN+10,cMAX_LEN*2+10;,char str1MAX_LEN+10,str2MAX_LEN+10;,for(i=0;iMAX_LEN+10;i+)ai=bi=0;,for(i=0;i=0;i-)/,把数字倒过来,aj+=str1i-0;,len2=strlen(str2);,for(j=0,i=len2-1;i=0;i-)/,倒转第二个整数,bj+=str2i-0;,13,/33,4,、参考程序,for(i=0;ilen2;i+)/,用第二个数乘以第一个数,每次一位,for(j=0;jlen1;j+),ci+j+=bi*aj;/,先乘起来,后面统一进位,for(i=0;i=10),ci+1+=ci/10;,ci%=10;,for(i=MAX_LEN*2;(ci=0)/,跳过高位的,0,if(i=0),for(;i=0;i-),printf(%d,ci);,else,printf(0);,return 0;,14,/33,大整数除法,1,、链接地址,除以23 为例来看一下：开始商为0。先减去23 的100 倍，就是2300，发现够减3 次，余下646。于是商的值就增加300。然后用646 减去230，发现够减2 次，余下186，于是商的值增加20。最后用186 减去23，够减8 次，因此最终商就是328。,所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10 倍、100 倍的时候，不用做乘法，直接在除数后面补0 即可。,3,、解题思路,17,/33,4,、参考程序,#include,#include,#define MAX_LEN 200,char szLine1MAX_LEN+10;,char szLine2MAX_LEN+10;,int an1MAX_LEN+10;/,被除数,an10,对应于个位,int an2MAX_LEN+10;/,除数,an20,对应于个位,int aResultMAX_LEN+10;/,存放商，,aResult0,对应于个位,/,长度为,nLen1,的大整数,p1,减去长度为,nLen2,的大整数,p2,/,结果放在,p1,里，返回值代表结果的长度,/,如不够减返回,-1,，正好减完返回,0,int 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-=p2iif(p1i=0;i-),if(p1i)/找到最高位第一个不为0,return i+1;,return 0;/全部为0，说明两者相等,19,/33,4,、参考程序,int main(),int t,n;,scanf(%d,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;/,朝高位移动,for(;i=0;i-)/,低位补,0,an2i=0;,nLen2=nLen1;,for(j=0;j=0),nLen1=nTmp;,aResultnTimes-j+;/,每成功减一次，则将商的相应位加,1,21,/33,4,、参考程序,/,下面输出结果，先跳过高位,0,for(i=MAX_LEN;(i=0),if(i=0),for(;i=0;i-),printf(%d,aResulti);,else,printf(0);,printf(n);,return 0;,22,/33,麦森数,1、链接地址,的素数称为麦森数，这时P 一定也是个素数。但反过来不一定，即如果P 是个素数。2P-1 不一定也是素数。麦森数有许多重要应用，它与完全数,完全数,(又称完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和恰好等于它本身。)密切相关.,你的任务：输入P(1000P3100000),计算2p-1 的位数和最后500 位数字（用十进制高精度数表示）,23,/33,问题描述,输入数据,只包含一个整数,P(1000P0，考虑p 的二进制形式，则不难得到：,这里，a,i,要么是1，要么是0。,3,、解题思路,26,/33,因而：,计算2,p,的办法就是：先将结果的值设为1，计算2,1,。如果a,0,值为1，则结果乘以2,1,；计算2,2,，如果a,1,为1，则结果乘以2,2,；计算2,4,，如果a,2,为1，则结果乘以2,4,；总之，第i 步(i 从0 到n，a,n,是1)就计算2,2i,，如果a,i,为1，则结果就乘以2,2i,。每次由2,2i,2,2i,就能算出2,2(i+1),。由于p可能很大，所以上面的乘法都应该使用高精度计算。由于题目只要求输出500 位，所以这些乘法都是只须算出末尾的500 即可。,3,、解题思路,27,/33,在前面的高精度计算中，我们用数组来存放大整数，数组的一个元素对应于十进制大整数的一位。本题如果也这样做，就会超时。为了加快计算速度，可以用一个数组元素对应于大整数的,4,位，即将大整数表示为,10000,进制，而数组中的每一个元素就存放,10000,进制数的,1,位。例如，用,int,型数组,a,来存放整数,6373384,，那么只需两个数组元素就可以了，,a0=3384,a1=637,。,由于只要求结果的最后,500,位数字，所以我们不需要计算完整的结果，只需算出最后,500,位即可。因为用每个数组元素存放十进制大整数的,4,位，所以本题中的数组最多只需要,125,个元素。,3,、解题思路,28,/33,4,、参考程序,#include,#include,#define LEN 125/,每数组元素存放,4,位，数组最多需要,125,个元素,#include,/,计算高精度乘法,a*b,结果的末,500,位放在,a,中,void Multiply(int*a,int*b),int i,j;,int nCarry;/,存放进位,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);,29,/33,4,、参考程序,int main(void),int i;,int p;,int anPowLEN;/,存放不断增长的,2,的次幂,int aResultLEN;/,存放最终结果的末,500,位,scanf(%d,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,anPow);,30,/33,4,、参考程序,aResult0-;/2p-1,/,输出结果,for(i=LEN-1;i=0;i-),if(i%25=12),printf(%02dn%02d,aResulti/100,aResulti%100);,else,printf(%04d,aResulti);,if(i%25=0),printf(n);,return 0;,31,/33,练习：,Exponentiation,Description,(,POJ：1001,),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.,32,/33,Description,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 value will be in columns 8 and 9.,Output,The output will consist of one line for each line of input giving the exact value of Rn.Leading zeros should be suppressed in the output.Insignificant trailing zeros must not be printed.Dont print the decimal point if the result is an integer.,33,/33,Description,Sample Input,95.123 12,0.4321 20,5.1234 15,6.7592 9,98.999 10,1.0100 12,Sample Output,548815620517731830194541.899025343415715973535967221869852721,.00000005148554641076956121994511276767154838481760200726351203835429763013462401,43992025569.928573701266488041146654993318703707511666295476720493953024,29448126.764121021618164430206909037173276672,90429072743629540498.107596019456651774561044010001,1.126825030131969720661201,