高精度的十进制运算.ppt

,高精度运算,在变量运算对象的数值范围为任何数据类型所无法容纳的情况下,采用整数数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）。1、采用数串形式输入，并将其转化为整数数组。2、用一个整数变量记录数据的实际长度（即数组的元素个数）3、该数组的运算规则如同算术运算。,数据结构与转换方法,typenumtype=array1.500ofword；/*整数数组类型*/vara，b:numtype；/*a和b为整数数组*/la，lb:integer；/*整数数组a的长度和b的长度*/s:string；/*输入数串*/将数串s转化为整数数组a的方法如下：klength(s)；fori1tokdoak-i+1ord(si)-ord(0)；,vara,b,c:array1.201of0.9;n:string;lena,lenb,lenc,i,x:integer;readln(n);lenalength(n);/*读加数串并记录长度*/fori1tolenado/*加数放入a数组*/alena-i+1ord(ni)-ord(0);readln(n);lenblength(n);/*读被加数串并记录长度*/fori1tolenbdo/*被加数放入b数组*/blenb-i+1ord(ni)-ord(0);,i1;while(i=10/*处理最高进位*/thenlenci;ci1elselenci-1;forilencdownto1do/*输出结果*/write(ci);writeln.,求回文数,1.将数串s转化为整数数组m,设数串s=s1sp，串长为p。其中si为第p-i+1位n进制数（1ip）。我们将s转化为整数数组m=mpm1，其中mi对应第i位n进制数。typemtype=array1.100ofinteger；Varm：mtype；按下述方法将s转化为整数数组m：plength(s)；/*计算s的串长*/fori1topdo/*从最高位开始计算整数数组m*/kp-i+1；/*计算si对应于的m数组下标*/casesiof/*转换si*/af：mk10+ord(si)-ord(a)；09：mkord(si)-ord(0)；else输出错误信息并退出程序；end；/*case*/；/*for*/,2.判别整数数组m是否为回文数,functioncheck(m：mtype)：boolean；/*若整数数组m为回文数，则返回true，否则返回false*/vari：integer；checkfalse；fori1todo/*返回m非回文数标志*/ifmimp-i+1thenexit；checktrue；/*返回m为回文数标志*/；/*check*/,3.n进制加法运算,整数数组m1与其反序数m2进行n进制加法运算，得到结果m1proceduresolve(varm1：mtype)；varm2：mtype；fori1topdom2im1p-i+1；/*计算反序数m2*/fori1topdo/*由右而左逐位相加*/m1im1i+m2i；m1i+1；/*进位*/m1im1imodn；/*确定当前位*/；/*for*/ifm1p+10thenpp+1；/*最高位进位*/ifcheck(m1)then输出步数并退出程序；/*solve*/,4.主程序,输入进制数n和数串s；fillchar(m，sizeof(m)，0)将s转换为整数数组m；ifcheck(m)then输出步数0；halt；/*then*/步数初始化为0；while步数30do步数+1；solve(m)；/*while*/输出无解信息；,vara,b,c:array1.200of0.9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;输入被减数s1和减数s2，计算s1的长度lena，s2的长度lenb；if(lena1)dodec(lenc);/*最高位的0不输出*/forilencdownto1dowrite(ci);writeln/*输出差*/.,1、整数数组除以整数（aa/i，a为整数数组，i为整数）2、高精度除法xx/y(被除数x和除数y为整数，解决计算精度和循环节的问题),aa/i(a为整数数组，i为整数）,按照由高位到底位的顺序，逐位相除。在除到第j位时，该位在接受了来自j+1位的余数（ajaj+(j+1位相除的余数)*10）后与i相除。如果最高位为0（nln=0），则n的长度减1。l0；/*余数初始化*/forjla-1downto0do/*按照由高位到底位的顺序，逐位相除*/inc(aj，l*10)；/*接受了来自第j+1位的余数*/lajmodi；/*计算第j位的余数*/ajajdivi；/*计算商的第j位*/；/*for*/while(ala-1=0)dodec(la)；/*计算商的有效位数*/,高精度运算不仅能够扩大整数的值域，而且能够通过扩大小数的位数减低除法的精度误差，甚至还可以计算出循环节。循环节的特征：当前余数的第j位先前在第i位出现过，则第i位小数第j位小数组成循环节。记录每个余数值的位序号,计算x/y(x和y为整数）的高精度实数,设小数部分的位数上限为limit；小数部分的指针为len；st为循环节的首指针；s为小数序列，其中si为第i位小数；posi为余数的位序列，其中posix表示余数为x的位序号。记下第1位的余数和小数（posixmody1，s1（xmody）*10divy，xxmody）；然后按照除法的运算规则计算第2位、第3位的余数和小数。若下一位余数先前出现过（posix0），则先前出现的位置posix为循环节的开始（stposix），退出计算过程；否则依次类推，直至小数位数达到上限limit为止。,fillchar(s,sizeof(s),0);/*小数部分初始化*/fillchar(posi,sizeof(posi),0);/*小数值的位序列初始化*/len0;st0;/*小数部分的指针和循环节的首指针初始化*/read(x,y);/*读被除数和除数*/write(xdivy);/*输出整数部分*/xxmody;/*计算x除以y的余数*/ifx=0thenexit;/*若x除尽y，则成功退出*/whilelen0/*若下一位余数先前出现过，则先前出现的位置为循环节的开始*/thenstposix;break;/*then*/ifx=0thenbreak;/*若除尽，则成功退出*/;/*while*/,iflen=0thenwriteln;exit;/*若小数部分的位数为0，则成功退出；否则输出小数点*/write(.);ifst=0/*若无循环节，则输出小数部分，否则输出循环节前的小数和循环节*/thenfori1tolendowrite(si)Elsefori1tost-1dowrite(si);write();foristtolendowrite(si);write();/*else*/,1、高精度数组a乘整数I2、两个高精度数组相乘,设x为当前位乘积和进位xx+aj*i;/*当前位乘积*/ajxmod10;/*当前位规整*/xxdiv10；/*计算进位*/,高精度数组a*整数i,精确计算n的阶乘n!（7n50）,a,a1,a2,amax的值可以是0到9的任意数字,数组长度为100（因为50!1)dodec(lenc);forilencdownto1dowrite(ci);writeln/*输出*/.,Hanoi双塔问题,递推关系式,设fi代表i个尺寸的盘子移动到目标柱的最少步数。移动分三个步骤：把前i-1尺寸的个盘子由起始柱移动到中间柱，移动步数为fi-1；把第i个尺寸的盘子由起始柱移动到目标柱，移动步数为fi=2；把前i-1个尺寸的盘子由中间柱移动到目标柱，移动步数为fi-1因此递推关系式为：fi=fi-1*2+2=(1ki)2k,(2in),边界：f1=2,由于n的上限为200，因此fi需要采用数组存储方式，且需进行采用f+整数和f*整数的运算。,设fi,0为fi的长度；fi,fi,01为fi对应的高精度整数readln(n);/*读盘子的尺寸数*/fillchar(f,sizeof(f),0);f1,01;f1,12;/*f1=2*/fori2tondo/*计算fi=fi-1*2+2*/fifi-1*2;fifi+2;输出整数数组fn;,矩阵取数游戏,给出一个N*M的矩阵，每次取每行的行首和行末的一个数，得分=被取走的元素值*2i（i表示第i次取数）。求最大得分。,动态规划。对每行分别处理求最大得分。定义Fi,j表示当前从某行的第i个元素取到第j个元素的最大得分。有两种取法：取末尾的第j个元素，得分为（Fi,j-1+Gj）*2；取首部的第i个元素，得分为(Fi+1,j+Gi)*2；显然Fi,j=max(Fi,j-1+Gj，Fi+1,j+Gi)*2。边界：Fi,i=Gi*2。（1im）当前行的最大得分为F1,m。累加n行的最大得分即为问题解。注意：由于最终答案位数在30位左右，需要高精度计算：F和结果为高精度数组涉及高精度运算：f*整数，f数组相加,计算s行的状态转移方程,functioncalc(s:longint):anstype;vari,j,l:longint;temp1,temp2:anstype;fillchar(f,sizeof(f),0);/*状态转移方程初始化为*/fori1tomdofi,imaps,i*2;/*fi,i为s行的第i个元素值*/forl2tomdo/*枚举区间长度*/fori1tom-l+1do/*枚举区间首指针*/ji+l-1;/*计算尾指针*/temp1(fi+1,j+maps,i)*2;/*取区间首元素*/temp2(fi,j-1+maps,j)*2;/*取区间尾元素*/iftemp1temp2/*取两个方案的大者作为该区间的状态转移方程值*/thenfi,jtemp1elsefi,jtemp2;calcf1,m/*返回s行的状态转移方程值*/;,主程序,readln(n,m);/*读矩阵规模*/fori1tondo/*读矩阵元素（存储方式为高精度数组）*/forj1tomdomapi,j01;read(mapi,j1);fillchar(ans,sizeof(ans),0);/*最大得分初始化为*/fori1tondoansans+calc(i);/*累加n行的状态转移方程值*/输出高精度数组ans；,麦森数,使用倍增思想，优化幂运算,首先，看一个简单的例子已知整数a，计算a17。很显然，一种最简单的方法就是令b=a，然后重复16次进行操作b=b*a。这样，为了得到a17，共进行了16次乘法。现在考虑另外一种方法，令a0=a，a1=a2，a2=a4，a3=a8，a4=a16，可以看出，ai=ai-12，(1i4)。于是，得到a0，a1，a2，a3，a4共需要4次乘法。而a17=a*a16=a0*a4，也就是说，再进行一次乘法就可以得到a17。这样，总共进行5次乘法就算出了a17。,已知a，计算an:,将n表示成为二进制形式，并提取出其中的非零位，即n=2(b1)+2(b2)+2(bw)，(2(i)=2i)不妨设b1b20do/*由低向高位逐位分析p的每一个二进制位*/ifpmod2=1/*若p的当前二进制位为1，则连乘当前项，取乘积的后500位*/thenansans*l；ppdiv2;ll2；/*处理高一位*/;/*while*/dec(ans0);/*计算2p-1*/fori499downto0do/*按50位数一行的格式输出2p-1的后500位数*/write(ansi);ifimod50=0thenwriteln;/*for*/,循环,【问题描述】乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。,众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：,这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？注意：1如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。2如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a+L次幂的最后k位都相同。【输入文件】输入文件circle.in只有一行，包含两个整数n（1n10100）和k（1k100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。【输出文件】输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。,问题的规模要求采用高精度计算,本题要求计算n（1n10100）的正整数次幂的最后k位（1k100）的循环长度，因此必须采用k位高精度运算。不仅每次乘幂运算需要通过高精度乘法保留后k位，而且由于最小循环长度是任何整数类型无法容纳的，因此其计算过程也需要用到k位高精度加法。,必须采用倍增思想提高时效,如果采用简单的连乘运算，是根本不可能满足时效要求的，只能采用倍增思想逐位递推：先保证第1位循环，求出最小的循环长度l1；接下来计算第2位循环的最小循环长度：连乘，直至出现2位循环为止。此时得出2位的最小循环长度l2；然后连乘，直至出现3位循环为止，由此得出第3位循环的最小循环长度；，依次类推，直至递推出第k位的最小的循环长度lk。在计