n的阶乘高精度算法解析

在n的阶乘中，n大于16时n的阶乘得出的结果用长整形保存时总是溢出，这对于刚刚学习c的学生来说总是感觉很棘手，于是就上百度，在搜索栏打上“阶乘”两个字，在搜索结果里面，有“百度百科”的解释，打开网页，使劲往下翻，就看到了关于“n的阶乘高精度运算”的c代码：#include<stdio.h>#defineN5000//modifyittoholdlargernumberintmain(void){intn,i,j,s,up,f[N]={0};scanf("%d",&n);for(i=2,f[0]=1;i<=n;i++)for(j=up=0;j<N;j++){s=f[j]*i+up;f[j]=s%10;up=s/10;}for(i=N-1;f[i]==0;i--);for(;i>=0;i--)printf("%d",f[i]);printf("\n");return0;}若是感觉不是很好明白，可以改成以下代码，可能就会好明白一点了：#include<stdio.h>#defineN5000//modifyittoholdlargernumberintmain(void){intn,i,j,s,up,f[N]={0};scanf("%d",&n);f[0]=1;for(i=2;i<=n;i++)//外循环控制阶乘的数{up=0;for(j=0;j<N;j++)//内循环用于得出前一个数的阶乘结果乘以当前数i得出的阶乘结果{s=f[j]*i+up;f[j]=s%10;up=s/10;}}for(i=N-1;f[i]==0;i--);for(;i>=0;i--)printf("%d",f[i]);printf("\n");return0;}当我们第一次接触这个代码的时候，你会不会感到很无奈呢？是不是不明白为什么这么做啊？下面说一说我对这串代码的理解：首先，要想要理解这串代码是怎么回事儿，最好的方法就是先找一个数带进去，找一张好的白纸，好好写一写，画一画，从0写到5。从更本质上来说，只把5带进去就行，因为0！*1=1！；1！*2=2!;2!*3=3!;3!*4=4!;4!*5=5!;但是3！=6<10;4!=24刚刚大于10,取5就更具有普遍性。下面就讨论当n=5时的情况。因为外循环是从i=2开始的所以我们也从i=2开始讨论。内循环中对于for（j=0,up=0;j<n;j++）一：i=2时1.j=0时：s=f[j]*i+up;----->s=f[0]*2+0=1*2+0=2；f[j]=s%10;----->f[0]=2%10=2;up=s/10;----->up=2/10=0;2.j=1时：s=f[j]*i+up;----->s=f[1]*2+0=0*2+0=0;f[j]=s%10;----->f[1]=0%10=0;up=s/10;----->up=0/10=0;当j大于等于2时的情况和“2.”时的情况相同，此时得到的结果为：f[0]=2;f[1]=0;f[2]=0;.....二：i=3时1.j=0时：s=f[j]*i+up;----->s=f[0]*3+0=2*3+0=6;f[j]=s%10;----->f[0]=6%10=6;up=s/10;----->up=6/10=0;2.j=1时：s=f[j]*i+up;----->s=f[1]*3+0=0*3+0=0;f[j]=s%10;----->f[1]=0%10=0;up=s/10;----->up=0/10=0;当j大于等于2时的情况和“2.”时的情况相同，此时得到的结果为：f[0]=6;f[1]=0;f[2]=0;......三：i=4时1.j=0时：s=f[j]*i+up;----->s=f[0]*4+0=6*4+0=24;f[j]=s%10;----->f[0]=24%10=4;up=s/10;----->up=24/10=2;2.j=1时:s=f[j]*i+up;----->s=f[1]*4+2=0*4+2=2;f[j]=s%10;----->f[1]=2%10=2;up=s/10;----->up=2/10=0;3.j=2时：s=f[j]*i+up;----->s=f[2]*4+0=0*4+0=0;f[j]=s%10;----->f[2]=0%10=0;up=s/10;----->up=0/10=0;当j大于等于2时的情况和“3.”时的情况相同，此时得到的结果为：f[0]=4;f[1]=2;f[2]=0;f[3]=0;......四：i=5时1.j=0时：s=f[j]*i+up;----->s=f[0]*5+0=20;f[j]=s%10;----->f[0]=s%10=20%10=0;up=s/10;----->up=20/10=2;2.j=1时：s=f[j]*i+up;----->s=f[1]*5+2=2*5+2=12;f[j]=s%10;----->f[1]=12%10=2;up=s/10;----->up=12/10=1;3.j=2时：s=f[j]*i+up;----->s=f[2]*5+1=0*5+1=1;f[j]=s%10;----->f[2]=1%10=1;up=s/10;----->up=1/10=0;4.j=3时：s=f[j]*i+up;----->s=f[3]*5+up=0*5+0=0;f[j]=s%10;----->f[3]=0%10=0;up=s/10;----->up=0/10=0;当j大于等于4时的情况和"3."时的情况相同，此时得到的结果是：f[0]=0;f[1]=2;f[2]=1;f[3]=0;f[4]=0;......到这个时候，我们已经把n=5时的情况带入程序并完全分解开写了出来，通过这个展开式我们能够发现什么呢？在这个问题得到解决以前，我们先看一看以下乘法：24*5=120，若是我们在小学，一定会这么算：运算1：24*5————————120我们先用4乘以5得到20然后写下0进2；然后让2乘以5得到10，用10加上2得到12,我们应该写下2进1；因为24前一位是0，我们可以认为是用0乘以5加上1得到1，此时写下1，24*5的乘法运算结束。算到这里你是不是有什么启发呢？再看下一个乘法运算的例子，或许你就会有一些灵感了：运算2：122*45——————————————————610488——————————————————5490这是我们在小学的时候就用的乘法运算，但是我们还能够将上面的那个乘法过程加以变形，然后得到另一个类似的乘法运算：运算3：122*(45)//在本次运算中把45视为一个整体______________________________________________先用122中的最高位2乘以45得到90，写下0进9；在让122中的次高位的2乘以45得到90，加上进位的9,得到99,写下最高位的9，进最低位的9；再让122中的最低位1乘以45得到45，用45加上进位的9,得到54，写下4，进5；因为122可以认为是0122，所以我们再用0乘以45得到0,用0加上进位的5,得到5,写下5，我们仍然能够得到5490这个答案，实际上，运算3可以等效为下面的运算4：运算4：45*122————————————————909045————————————————5490我们发现运算3和运算4实际上是一个运算，因为它们的运算过程完全相同，但是因为我们一般都是用运算2的运算方法运算两个数的乘积，就连运算4的方法人们都很少用，更何况运算3了。虽然说运算3的方法很少用，但是，实际上，在编程的时候，特别是在阶乘的高精度运算中，用的正是这个方法。在运算3中122*45的过程相当于内循环中的整个循环，122相当于前44（外循环中的i-1）个数的乘积（假设是，实际上不是，这个乘积相当于i-1的阶乘），45相当于外循环中的i；在运算的时候，程序把45当成一个整体来运算。我们来看看到底程序是怎样用数组来保存大整数的。还是用122*45这个例子。实际上数组中的每一个元素都保存有f[i]>=0&&f[i]<=9的元素。在122*45这个乘法运算中，则有122|||f[2]f[1]f[0]所以有运算3：122*（45）—————————————————等价于运算5：f[3]f[1]f[0]*i____________________________________________我们把运算3的运算过程带入运算5就能发现，这个过程和我们将n=5时的情况带入程序时的分析过程完全相同，到此，我们已经完全证明了，程序代码中的内循环就是i-1的阶乘结果乘以i的过程，而且这个过程用的方法就是我们在运算3中用的方法。到这里，我们已经能够完全明白百度百科中所提供的程序代码的运行过程了，外循环控制阶乘数，正如：0！*1=1！；1！*2=2!;2!*3=3!;3!*4=4!;4!*5=5!;内循环控制i-1！和i的乘积求积的过程，如4！*5的过程，其中4！在上个内循环已经求出并保存在了数组中。分析过程到此已经结束，亲爱的朋友们，你们是不是已经明白了呢？