资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,00748067 张姣,1,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.,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.,Poj 1001,2,题目描述：,涉及到大数据的要求精确计算的问题是很常见的。比如要求计算国家借款对于许多电脑系统是一个非常繁重的任务。,本题中要求计算一个在零到一百以内的实数的n次方（0n=25)。,3,在计算机上进行高精度计算，首先要处理好以下几个基本问题：,1、数据的接收与存储；,2、计算结果位数的确定；,3、进位处理和借位处理；,4、商和余数的求法；,4,输入和存储,运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种：数组和字符串。,（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；优点：每一位都是数的形式，可以直接加减；运算时非常方便缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；,（2）字符串：字符串的最大长度是255，可以表示255位。优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便（注意0的问题）。,5,优化:,一个数组元素存放四位数,注意：是加减法时可以用interger，但是当是乘法的时候，就要用int64，否则会出现越界的情况。,还有就是：输出时对非最高位的补零处理。,6,另一个问题：,存储顺序,正序？,逆序？,还有就是一定不要忘了初始化！,7,计算结果位数的确定,两数之和的位数最大为较大的数的位数加1。,乘积的位数最大为两个因子的位数之和。,阶乘：lgn!=lgn+lg(n-1)+lg(n-2).+lg3+lg2+lg1,=lnn/ln10+ln(n-1)/ln10+ln(n-2)/ln10+.+ln3/ln10+ ln2/ln10+ln1/ln10,=trunc(1/ln10*(lnn+ln(n-1)+ln(n-2)+.+ln3+ln2+ln1),乘方：lg(ab)=trunc(lg(ab)+1=trunc(b*lga)+1=trunc(b*lna/ln10)+1,8,高精度的加法,ncarry=0;,for (i=0;i0时，len会变化！,9,高精度的减法,先比较大小，大的为a，用一个变量记录符号。,ncarry=0;,for (i=0;i=0),ai=ai-bi-ncarry,ncarry=0;,else,ai=ai+N-bi-ncarry,ncarry=1;,10,高精度的乘法,For (i=0;i=lena;i+),for (j=0;j=lenb;j+),ci+j+=ai*bj;,For (i=0;i=lena+lenb;i+),ci+j+1+=ci+j/N;,ci+j=ci+j/N;,11,这道题：,1.处理小数点问题，以及反序。,2.进行n次乘法。,3.进行输出，并加上小数点。,12,while,(,scanf,(%s%d,d,&n)!=EOF),int a150=0,b150=0,c150=0.,int temp,flag,i,j,k,digit,s;,int lend,lena,lenb,lenc,len;,lend=,strlen,(d)-1;,for,(i=0;di;i+),if,(di=.),break,;,digit=lend-i;,for,(j=i;dj;j+) dj=dj+1;,lend=lend-1;,13,for,(i=0;i=lend/2;i+),temp=di;di=dlend-i;,dlend-i=temp;,for,(i=0;di;i+) ai=di-48;,lena=lend;,for,(i=0;i=lena;i+)bi=ai;,lenb=lena;,14,for,(i=1;i=n-1;i+) ,for,(j=0;j=lenb;j+),for,(k=0;k=lena;k+) ,cj+k+=ak*bj;,ck+j+1+=cj+k/10;,cj+k%=10;,k-; j-;,if,(ck+j+1!=0) lenc=j+k+1;,else,lenc=j+k;,for,(j=0;j=0;i-),if,(bi!=0)flag=1;,break,;,if,(flag=0) ,for,(i=lenb;i=lenb-len+1;i-),printf,(%d,bi);,printf,(n);,continue,;,if,(len=1&blenb=0),printf,(.);,else,for,(i=lenb;i=lenb-len+1;i-),printf,(%d,bi);,printf,(.);,for,(i=0;i=temp;i-),printf,(%d,bi);,printf,(n);,16,一般来说，我们会构造函数。,还是要注意初始化。,以及 总的位数。,17,高精度的除法,AB精确值有两种情况：、A能被B整除，没有余数。、A不能被B整除，对余数进行处理。首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，三个变化的量分别是：被除数、商和余数。,18,可以用减法代替除法运算：不断比较A1.n与B1.n的大小，如果A1.n=B1.n则商C1.n+1C1.n，然后就是一个减法过程：A1.n-B1.nA1.n。,19,由于简单的减法速度太慢，故必须进行优化。,设置一个位置值J，当A1.nB1.n时，B1.n左移B0.n，j:=j+1，即令B1.n增大10倍。这样就减少了减法的次数。当j0且A1.nB1.n时，B0.n右移。,20,求n！,21,一个例子：计算5*6*7*8,方法一：顺序连乘,5*6=30，1*1=1次乘法,30*7=210，2*1=2次乘法,210*8=1680，3*1=3次乘法,方法二：非顺序连乘,5*6=30，1*1=1次乘法,7*8=56，1*1= 1次乘法,30*56=1680，2*2=4次乘法,22,若“n,位数*m位数=n+m位数,”,，则n个单精度数。,无论以何种顺序相乘，乘法次数一定为n(n-1)/2次。（n为积的位数）,证明：,设F(n)表示乘法次数，则F(1)=0，满足题设,设kn时，F(k)=k(k-1)/2，现在计算F(n),设最后一次乘法计算为“k位数*(n-k)位数”，则,F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2（与k的选择无关）,23,考虑k+t个单精度数相乘,a,1,*a,2,*a,k,*a,k+1,*a,k+t,设,a,1,*a,2,*a,k,结果为m位高进制数（假设已经算出）,a,k+1,*a,k+t,结果为1位高进制数,若顺序相乘，需要t次“m位数*1位数” ，共mt次乘法,可以先计算,a,k+1,*a,k+t,，再一起乘，只需要m+t次乘法,24,在设置了缓存的前提下，计算m个单精度数的积，如果结果为n位数，则乘法次数约为n(n1)/2次，与m关系不大,设S=a1*a2*am，S是n位高进制数,可以把乘法的过程近似看做，先将这m个数分为n组，每组的积仍然是一个单精度数，最后计算后面这n个数的积。时间主要集中在求最后n个数的积上，这时基本上满足“n位数*m位数=n+m位数”，故乘法次数可近似的看做n(n-1)/2次,25,10!=2,8,*3,4,*5,2,*7,n!分解质因数的复杂度远小于nlogn，可以忽略不计,与普通算法相比，分解质因数后，虽然因子个数m变多了，但结果的位数n没有变，只要使用了缓存，乘法次数还是约为n(n-1)/2次,因此，分解质因数不会变慢（这也可以通过实践来说明）,分解质因数之后，出现了大量求乘幂的运算，我们可以优化求乘幂的算法。这样，分解质因数的好处就体现出来了,26,二分法求乘幂,a,2n+1,=a,2n,*a,a,2n,=(a,n,),2,其中，a是单精度数,27,二分法求乘幂之优化平方算法,怎样优化,(a+b),2,=a,2,+2ab+b,2,例：12345,2,=,123,2,*10000+,45,2,+2*,123*45,*100,把一个n位数分为一个t位数和一个n-t位数，再求平方,怎样分,设求n位数的平方需要F(n)次乘法,F(n)=F(t)+F(n-t)+t(n-t)，F(1)=1,用数学归纳法，可证明F(n)恒等于n(n+1)/2,所以，无论怎样分，效率都是一样,将n位数分为一个1位数和n1位数，这样处理比较方便,28,优化：,计算S=a,x+k,b,x,=(ab),x,a,k,当ka,x+k,b,x,时，选用(ab),x,a,k,，反之，则采用a,x+k,b,x,。,a,x,b,x,a,k,a,x+k,b,x,(b,x,a,k,)(a,x,+1)0,b,x,a,k,这时kxlog,a,b,30,Poj,1131 1220 1640,2005 2050 2350,31,The end. Thanks for your attention !,32,
展开阅读全文