大数的阶乘算法
http://m.blog.csdn.net/petershina/article/details/45070359
发表于2015/4/16 9:08:24 2146人阅读
分类: 数据结构
用data数组来存放阶乘的每一位数字,首先令第一位的数值为1,位数为1,然后将每次相乘的乘积存回数组,并循环处理每个数组中超过10的数,若数值超过10,则需要进位,将位数加1,原来的数除以10,商数加前一位数的数值后存回前一位数的数组中,再将余数存回原来位数的数组中。
例如求5!的值
步骤一:
1!=1
位数1
数组内容0 0 0 1
步骤二:
2!=2*1!=2
位数1
数组内容0 0 0 2
步骤三:
3!=3*2!=3*2=6
位数1
数组内容0 0 0 6
步骤四:
4!=4*3!=4*6=24
位数1
数组内容0 0 0 24
因为24大于10,需要进位
data[1]=data[1]+data[0]/10=0+2=2
data[0]=data[0]%10=4
所以数组内容为0 0 2 4
位数2
步骤五:
5!=5*4!=5*24=120
位数2
数组内容为0 0 2*5 4*5
即0 0 10 20
因为data[0]大于10,需要进位
data[1]=data[1]+data[0]/10=10+2=12
data[0]=data[1]%10=0
此时数组内容为0 0 12 0
data[2]=data[2]+data[1]/10=0+1=1
data[1]=data[1]%10=2
位数加1
数组内容为0 1 2 0
一次类推,可以计算大数的阶乘,代码如下:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define MAX 100 void factorial(int n,char output[]) { int i = 0, j = 0; int cin = 0, tmp = 0; int result[MAX] = {0}; result[0] = 1; for(i = 2; i <= n; i++) { cin = 0; for(j = 0; j < MAX; j++) { /*120x7 = 0x7 + 2x7x10 + 1x7x100 */ /* 7 cin=0 4 cin=1 0 cin=7 */ tmp = result[j]*i + cin; result[j] = tmp % 10; cin = tmp / 10; } } for(i = MAX - 1; i >= 0; i--) { if(result[i] != 0) { break; } } for(j = i; j >= 0; j--) { sprintf(output++, "%d", result[j]); } } int main() { int i = 0; long long result = 1; char out[MAX]={0}; factorial(20,out); printf("result:%s ", out); return 0; }