N的阶乘
问题描述
输入一个正整数n,输出n!的值。
其中n!=1*2*3*…*n。
算法描述
n!可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数a,A[0]表示a的个位,A[1]表示a的十位,依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k,请注意处理相应的进位。
首先将a设为1,然后乘2,乘3,当乘到n时,即得到了n!的值。
输入格式
输入包含一个正整数n,n<=1000。
输出格式
输出n!的准确值。
样例输入
10
样例输出
3628800
代码如下:
1 #include <stdio.h> 2 #include <string.h> 3 #define MAX 4000 4 int main() 5 { 6 int n,a[MAX],i,g,s,t=0; 7 scanf("%d",&n); 8 memset(a,0,sizeof(a)); 9 a[0]=1; 10 for(i=2;i<=n;i++) 11 { 12 for(g=0;g<MAX;g++) 13 { 14 s=a[g]*i+t; 15 t=s/10;//进位 16 a[g]=s%10; 17 } 18 } 19 for(i=MAX-1;i>=0;i--)//计算位数 20 { 21 if(a[i]) 22 break; 23 } 24 for(g=i;g>=0;g--)//倒序输出 25 printf("%d",a[g]); 26 return 0; 27 }
BASIC-29 高精度加法
问题描述
输入两个整数a和b,输出这两个整数的和。a和b都不超过100位。
算法描述
由于a和b都比较大,所以不能直接使用语言中的标准数据类型来存储。对于这种问题,一般使用数组来处理。
定义一个数组A,A[0]用于存储a的个位,A[1]用于存储a的十位,依此类推。同样可以用一个数组B来存储b。
计算c = a + b的时候,首先将A[0]与B[0]相加,如果有进位产生,则把进位(即和的十位数)存入r,把和的个位数存入C[0],即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加,这时还应将低位进上来的值r也加起来,即C[1]应该是A[1]、B[1]和r三个数的和.如果又有进位产生,则仍可将新的进位存入到r中,和的个位存到C[1]中。依此类推,即可求出C的所有位。
最后将C输出即可。
输入格式
输入包括两行,第一行为一个非负整数a,第二行为一个非负整数b。两个整数都不超过100位,两数的最高位都不是0。
输出格式
输出一行,表示a + b的值。
样例输入
20100122201001221234567890
2010012220100122
样例输出
20100122203011233454668012
代码如下:
1 #include <stdio.h> 2 #include <string.h> 3 4 int main() 5 { 6 char a[100]; 7 char b[100]; 8 int c[100]; 9 gets(a); 10 gets(b); 11 memset(c,0,sizeof(c)); 12 int len1=strlen(a)-1; 13 int len2=strlen(b)-1; 14 int i=0; 15 while(i<=len1||i<=len2) 16 { 17 if(i<=len1) 18 { 19 c[i]=c[i]+a[len1-i]-'0'; 20 } 21 if(i<=len2) 22 { 23 c[i]=c[i]+b[len2-i]-'0'; 24 } 25 if(c[i]>=10) 26 { 27 c[i+1]=c[i]/10; 28 c[i]%=10; 29 } 30 i++; 31 if(i>len1&&i>len2&&c[i]) 32 { 33 i++; 34 } 35 } 36 int g; 37 for(g=i-1;g>=0;g--) 38 { 39 printf("%d",c[g]); 40 } 41 printf(" "); 42 return 0; 43 }
阶乘之和
链接:https://ac.nowcoder.com/acm/contest/1069/C
题目描述
输入描述:
输入正整数N
输出描述:
输出计算结果S
输入
3
输出
9
代码
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <queue> 8 #include <set> 9 const int INF=0x3f3f3f3f; 10 using namespace std; 11 int S[1010]; 12 int cnt_s; 13 int T[1010]; 14 int cnt_t; 15 16 void f1(int x) 17 { 18 int jw=0; 19 for(int i=0;i<cnt_t;i++) 20 { 21 jw+=T[i]*x; 22 T[i]=jw%10; 23 jw/=10; 24 } 25 while(jw) 26 { 27 T[cnt_t++]=jw%10; 28 jw/=10; 29 } 30 } 31 32 void f2() 33 { 34 for(int i=0;i<cnt_t;i++) 35 { 36 S[i]+=T[i]; 37 if(S[i]>9) 38 { 39 S[i+1]+=S[i]/10; 40 S[i]%=10; 41 } 42 } 43 cnt_s=cnt_t;//阶乘n位数一定大于阶乘1到n-1的和,小位数加大位数,偷懒了 44 } 45 46 int main() 47 { 48 int n; 49 scanf("%d",&n); 50 cnt_t=1; 51 T[0]=1; 52 for(int i=1;i<=n;i++) 53 { 54 f1(i); 55 f2(); 56 } 57 for(int i=cnt_s-1;i>=0;i--) 58 { 59 printf("%d",S[i]); 60 } 61 printf(" "); 62 return 0; 63 }