阶乘和

阶乘和
    总时间限制:1000ms   内存限制:65536kB
描述
    用高精度计算出S=1!+2!+3!+…+n!（n≤50）
    其中“!”表示阶乘，例如：5!=5*4*3*2*1。
    输入正整数N，输出计算结果S。
输入
    一个正整数N。
输出
    计算结果S。
样例输入
    5
样例输出
    153
来源    NOIP1998复赛普及组第二题

分析：

这个题目涉及大整数的加法、大整数的阶乘。这个地方，大整数阶乘其实是累乘，就是一个大整数乘以一个小整数。

这里大整数可以考虑使用一个int数组模拟，各位数字按低位到高位从数组的第0号元素开始存储。另外使用一个int变量记录该大整数的位数。

这样一来，大整数相加，只要按位相加并处理好进位即可。（为了方便，大整数数组后面没有使用的部分可以都设为0.）

一个大整数temp[ ]和一个int变量t相乘，可以用t变量的每一位依次乘以大整数的各个位，把结果放在另外一个临时数组ansT[ ]中，乘完后再复制到temp[]即可。注意处理好进位即可。

这里要注意：

ansT[j+k]=temp[j]*t+ansT[j+k];
ansT[j+k+1]=ansT[j+k+1]+ansT[j+k]/10;
ansT[j+k]=ansT[j+k]%10;
其中k是指当前参与乘法计算的是t的第k位。（个位是第0位，十位是第1位，其他以此类推。）ansT[]在t*temp[ ]之前要清0.
在此过程要注意更新temp[]的长度。

 1 #include <stdio.h>
 2 #define maxLen 2000
 3 int main(int argc, char *argv[])
 4 {
 5     int n,i;
 6     int ans[maxLen]={0},temp[maxLen]={0},ansT[maxLen]={0};//低位在前，高位在后 
 7     int lenA,lenT;
 8     
 9     int j,tempI,t,k,flag,c;
10     
11     scanf("%d",&n);
12     if(n==0||n==1)
13     {
14         printf("1
");
15         return 0;
16     }
17     else if(n<0) return 0;
18     
19     ans[0]=1; // 1的阶乘 
20     lenA=1;
21     temp[0]=1; //1的阶乘 
22     lenT=1;
23     for(i=2;i<=n;i++)//每轮循环计算出i的阶乘并累加到ans 
24     {
25         //计算i的阶乘:  temp[]*i -> ansT[] -> temp[].
26         
27         //先实现：temp[]*i -> ansT[].这个需要用i的每一位依次去乘temp[] 
28         tempI=i;
29         for(j=0;j<maxLen;j++) ansT[j]=0;
30         k=0; //k表示当前准备用i的第k位去乘temp[] 
31         while(tempI>0)//枚举tempI的每一个位的数字
32         {
33             t=tempI%10;//temp[]*t -> ansT[]
34             tempI=tempI/10;
35             for(j=0;j<lenT;j++)//用t去乘以temp[]的每一位 
36             {
37                 ansT[j+k]=temp[j]*t+ansT[j+k];
38                 ansT[j+k+1]=ansT[j+k+1]+ansT[j+k]/10;
39                 ansT[j+k]=ansT[j+k]%10;
40             }
41             k++;//k表示当前t是i的第几位 
42         }
43         //这个for的功能：ansT[] -> temp[]
44         flag=0;
45         for(j=maxLen-1;j>=0;j--) 
46         {
47             temp[j]=ansT[j];
48             if(flag==0&&ansT[j]!=0)//寻找temp[]的长度 
49             {
50                 lenT=j+1;
51                 flag=1;
52             }
53         }
54         
55         //测试性质的代码：输出temp[]
56         /*for(j=lenT-1;j>=0;j--)
57         {
58             printf("%d",temp[j]);
59         }
60         printf("----------");*/
61         
62         //计算累加和：ans[]+temp[]  ->  ans[] 
63         c=0;//两个位相加时的进位 
64         lenA=(lenA>lenT?lenA:lenT);
65         for(j=0;j<lenA;j++)
66         {
67             ans[j]=ans[j]+temp[j]+c;
68             c=ans[j]/10;
69             ans[j]=ans[j]%10;
70         }
71         if(c!=0)
72         {
73             ans[j]=c;
74             lenA++;
75         }
76         //测试性质的代码：输出ans[]
77         /*for(j=lenA-1;j>=0;j--)
78         {
79             printf("%d",ans[j]);
80         }
81         printf("
");*/
82     }
83     for(j=lenA-1;j>=0;j--)
84     {
85         printf("%d",ans[j]);
86     }
87     printf("
");/**/
88     return 0;
89 }

另一段优秀的代码：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int a[100000],n,i,y,xy[100000],s[100000];
 5 
 6 void add()//s[]=s[]+a[]，计算过程用xy[]做临时存储空间
 7 {
 8     int i;
 9     memset(xy,0,sizeof(xy));
10     xy[0]=max(s[0],a[0]);
11     for (i=1;i<=xy[0];i++)
12     {
13         xy[i]+=s[i]+a[i];
14         xy[i+1]=xy[i]/10;
15         xy[i]%=10;
16         }
17     while (xy[xy[0]+1]>0) 
18         {
19             xy[xy[0]+2]=xy[xy[0]+1]/10;
20             xy[xy[0]+1]%=10;
21             xy[0]++;
22         }
23     s[0]=xy[0];
24     for (i=1;i<=xy[0];i++) s[i]=xy[i];
25 }
26 int main()
27 {
28     cin>>n;
29     a[0]=1;a[1]=1;//a[]现在表示1的阶乘
30     s[0]=1;s[1]=0;//s[]现在表示数字0    
31     for (y=1;y<=n;y++) //计算1！+2!+3!+……+n！
32     {
33         //第一步：计算y的阶乘y！=（y-1）！*y，其中y-1的阶乘就是a[]。计算结果存储在xy[]
34         memset(xy,0,sizeof(xy));
35         xy[0]=a[0];
36         for (i=1;i<=a[0];i++)
37         {
38           xy[i]+=a[i]*y;
39           xy[i+1]=xy[i]/10;
40           xy[i]%=10;
41         }
42         while (xy[xy[0]+1]>0) 
43         {
44             xy[xy[0]+2]=xy[xy[0]+1]/10;
45             xy[xy[0]+1]%=10;
46             xy[0]++;
47         }
48         //第二步：将计算结果复制到a[]
49         for (i=1;i<=xy[0];i++) a[i]=xy[i];
50         a[0]=xy[0];
51         //第三步：阶乘累加
52         add();
53     }
54     for (i=s[0];i>=1;i--) cout<<s[i];
55     cout<<endl;
56     return 0;
57 }

View Code

http://noi.openjudge.cn/ch0106/10/