大数阶乘的c语言算法心得
发布时间：2020-12-14 04:12:35 所属栏目：大数据 来源：网络整理
导读：? ? ? ?由于大数阶乘的位数超出了int的表示范围，我们只能用一个数组来放置它，那么首先确定结果数组的大小，这个可以根据阶乘位数的计算公式来计算，这里有个关键点，在定义数组的时候可以先给出一个指针，在原则上指针和数组是一致的，等确定了大小后就可
|
? ? ? ?由于大数阶乘的位数超出了int的表示范围，我们只能用一个数组来放置它，那么首先确定结果数组的大小，这个可以根据阶乘位数的计算公式来计算，这里有个关键点，在定义数组的时候可以先给出一个指针，在原则上指针和数组是一致的，等确定了大小后就可以利用malloc（）来申请一块内存来，这个内存就是我们最后的结果数组，如果直接定义数组就会遇到必须确定数组大小的麻烦，得到了数组后然后我们对初始化，注意必须个位赋值为一，这时候我们进入了关键的迭代，进入了for（）大循环，在这里结果数组就是一个寄存器，每循环一次，我们都把结果放在a[j]里面，此时a[j]里面很可能已经出现大于9的数字，这就需要向a[j+1]进位，此时我们设计一个子函数来实现这个功能，dgCal()函数，设置了一个进位标志位cy,传入此函数的是一个结果数组，和最高位非零的下标，首先遍历整个数组的非零部分，从个位开始，进位标志位赋初值为0，进入循环后，首先判读进位标志位是否需要进位，如果有值，肯定是从下面传上来的，加到自己的数字上面，然后开始判断自己的数字是属于下面三种那种情况，根据情况判断如何设置进位位。遍历完后，进入主函数进行下一轮的循环与（i+1）相乘。
这个算法的亮点就是结果数组的定义和，进位子函数的设计很好。
#include "math.h" ?
#include "stdio.h" ?
#include "stdlib.h" ?
??
void jinwei(int a[],int pos) ?
{ ?
? ? int i,cy=0; ? ? ?//进位值 ?，cy装载循环一次数组中需要进位的值
? ? for(i=0;i<=pos;i++)//从0-pos逐个检查是否要进位 ?
? ? { ?
? ? ? ? a[i]+=cy; ?
? ? ? ? if(a[i]<=9)//不需进位 ?
? ? ? ? { ?
? ? ? ? ? ? cy=0;//进位制为0 ?
? ? ? ? } ?
? ? ? ? else if(a[i]>9&&i<pos)//需进位，但未达到最高位 ?
? ? ? ? { ?
? ? ? ? ? ? cy=a[i]/10;//进位值 ?
? ? ? ? ? ? a[i]=a[i]%10; ?
? ? ? ? } ?
? ? ? ? else if(a[i]>9&&i>=pos)//需进位，已达到最高位 ?
? ? ? ? { ?
? ? ? ? ? ? while(a[i]>9)//循环向前进位 ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? cy=a[i]/10; ?
? ? ? ? ? ? ? ? a[i]=a[i]%10; ?
? ? ? ? ? ? ? ? i++; ?
? ? ? ? ? ? ? ? a[i]=cy; ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? } ?
} ?
??
int main( ) ?
{ ?
? ? int i,j; ?
? ? int *a;//结果数组 ?
? ? int num=200;//要求的阶乘数 ?
? ? int pos=0;//最高位下标 ?
??
? ? int digit=0;//阶乘的位数 ?
? ? double sum=0; ?
? ? for(i=1;i<=num;i++) ?
? ? { ?
? ? ? ? sum += log10((double)i);//计算阶乘的位数 ?
? ? } ?
? ? digit=(int)sum+1;//阶乘的位数 ?
??
? ? if(!(a=(int *)malloc( (digit+1) * sizeof(int) )))//分配内存 ?
? ? { ?
? ? ? ? printf("内存分配失败！n"); ?
? ? ? ? return 0; ?
? ? } ?
? ? for(i=0;i<=digit;i++) ?
? ? { ?
? ? ? ? a[i]=0;//初始化 ?
? ? } ?
? ? a[0]=1;//个位为1 ?
??
? ? for(i=2;i<=num;i++)//2-num逐个与原来的结果相乘 ?
? ? { ?
? ? ? ? for(j=digit;j>=0;j--)//查找最高位的下标 ?
? ? ? ? { ?
? ? ? ? ? ? if(a[j]!=0) ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? pos=j; ?
? ? ? ? ? ? ? ? break; ?
? ? ? ? ? ? } ?
? ? ? ? } ?
??
? ? ? ? for(j=0;j<=pos;j++) ?
? ? ? ? { ?
? ? ? ? ? ? a[j]*=i;//逐个相乘 ?
? ? ? ? } ?
?
? ? ? ? jinwei(a,pos);//乘完一轮后进位处理 ?
??
? ? } ?
??
? ? for(j=digit;j>=0;j--)//查找最高位的下标 ?
? ? { ?
? ? ? ? if(a[j]!=0) ?
? ? ? ? { ?
? ? ? ? ? ? pos=j; ?
? ? ? ? ? ? break; ?
? ? ? ? } ?
? ? } ?
??
? ? printf("200的阶乘：n"); ?
? ? printf("位数：%dn",pos+1); ?
? ? for(i=pos;i>=0;i--) ?
? ? { ?
? ? ? ? printf("%d",a[i]);//打印结果 ?
? ? } ?
? ? printf("n"); ?
??
? ? return 0; ?
} ?
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |