另一种求大数阶乘的算法

发布时间：2020-12-14 03:55:41 所属栏目：大数据来源：网络整理

导读：大数阶乘 ?? ? 问题描述：编写程序，对给定的n(n = 100),计算并输出k的阶乘k!的全部有效数字。 ????注意：如果要求一个5的阶乘，用整型可以存储，求10的阶乘可以用长整型表示，但若要求100的阶乘，就无法用长整型表示，此时就必须考虑别的方法。 ??? 要求的k

大数阶乘

??? 问题描述：编写程序，对给定的n(n <= 100),计算并输出k的阶乘k!的全部有效数字。

????注意：如果要求一个5的阶乘，用整型可以存储，求10的阶乘可以用长整型表示，但若要求100的阶乘，就无法用长整型表示，此时就必须考虑别的方法。

??? 要求的k!的值，必定已求得（k-1)!的值，依次地推，当 k = 2时，要求的1！ = 1为已知。求得(k-1)!的值后，对（k-1)!连续累加k-1此后即可求得K!值。

??? 例如：5！= 120，计算6！,可对原来的120累加5次120后得到720.

?? 由于k!可能大大超出一般整数的位数，因此程序用一个一维数组存储长整型，存储长整数数组的每个元素只存储长整数的一位数字。如有m位长整数N用数组a[]存储,并用a[0]存储长整数N的位数m，即a[0] = m。按上述约定，数组的每个元素存储k的阶乘k!的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素....

? 例如：6！ = 720，在数组中的存储形式为：

?a[0]?????? a[1]??????? a[2]???? a[3]

? 3?????????0?????????? 2?? ?????7

?a[0] = 3表示长整数是一个3位数，接着从低位到高位依次是0、2、7，表示成整数720.

程序实现：

[cpp]? 
   view plain 
   copy 
    
   
 /*?
 ?*程序功能：计算任意位数的阶乘?
?*作者Blog:http://blog.csdn.net/u012027907?
?*/??
 #include?<stdio.h>??
 #include?<malloc.h>??
 #define?MAXN?1000??
 ??
//已知a中的(k-1)!,求k!??
 void?PreNext(int?a[],int?k)???
 {??
 ????int?*b,m?=?a[0],i,j,r,carry;??
 ????b?=?(int*)malloc(sizeof(int)*(m+1));??
 ????for(i?=?1;?i?<=?m;?i++)????
 ????????b[i]?=?a[i];??
for(j?=?1;?j?<?k;?j++)???//控制累加k-1次??
 ????{??
 ????????for(carry=0,i?=?1;i?<=?m;i++)??
 ????????{??
 ????????????r?=?(i?<=?a[0]?a[i]+b[i]:a[i])+carry;?//计算加的结果??
 ????????????a[i]?=?r?%?10;?//计算本位结果??
 ????????????carry?=?r?/?10;?//计算进位数字??
 ????????}??
if(carry)??//向最高为进位??
 ????????????a[++m]?=?carry;??
 ????}??
 ????free(b);??
 ????a[0]?=?m;??
 }??
void?Print(int?*a,87); background-color:inherit; font-weight:bold">int?k)??
int?i;??
 ????int?m?=?0;??
for(i?=?a[0];?i?>0;?i--){??
 ????????printf("%d",a[i]);??
 ????????m++;??
 ????????if(m?%?5?==?0)?????????????//每5个数字空一格?????
 ????????????printf("?");????
if(40?==?m)????????????????//每行输出40个数字?????
 ????????{????
 ????????????printf("n");????
 ????????????m?=?0;????????????
 ????printf("n");??
 }??
 void?main()??
 {??
int?a[MAXN],n,k;??
 ????n?=?1;??
 ????printf("本程序计算任意位数的阶乘！n");??
 ??????
 ????while(n){??
 ????????printf("请输入一个数：");??
 ????????scanf("%d",&n);??
 ????????a[0]?=?a[1]?=?1;??
for(k?=?2;?k?<=?n;?k++)??
 ????????{??
 ????????????PreNext(a,k);?????????
 ????????????if(k?==?n)??
 ????????????????Print(a,k);??
 ????????}??
 ????}??
 }??

运行截图：

转载请标明出处：http://blog.csdn.net/u012027907

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!