C语言程序设计100例之（68）：大整数乘法
例68 大整数乘法
问题描述
求两个不超过200位的非负整数的积。
输入
有两行，每行是一个不超过200位的非负整数，没有多余的前导0。
输出
一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
输入样例
12345678900
98765432100
输出样例
1219326311126352690000
（1）编程思路。
将大整数用字符串保存，编写函数void mul(char *a,char *b,char *c)实现大整数c=a*b。
在函数中用int x[201]和int y[201]分别存放两个乘数，用int z[401]来存放积。计算的中间结果也都存在数组z中。数组z长度取401 是因为两个200 位的数相乘，积最多会有400 位。x[0], y[0], z[0]都表示个位。
计算的过程基本上和小学生列竖式做乘法相同。为编程方便，不急于处理进位，而将进位问题留待最后统一处理。
在乘法过程中，数组x的第i 位和y的第j 位相乘所得的数，一定是要累加到z的第i+j 位上。这里下标i, j 都是从右往左，从0 开始数。
（2）源程序。
#include
#include
void mul(char *a,char *b,char *c)
{
int len1=strlen(a),len2=strlen(b);
int x[201],y[201],z[401];
int len=len1+len2;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(z,0,sizeof(z));
int i,j;
for (i=len1-1;i>=0;i--)
x[len1-1-i]=a[i]-'0';
for (i=len2-1;i>=0;i--)
y[len2-1-i]=b[i]-'0';
for (i=0;i { for (j=0;j { z[i+j]+=x[i]*y[j]; } } for (i=0;i { if (z[i]>=10) { z[i+1]+=z[i]/10; z[i]=z[i]%10; } } while (len>0 && z[len-1]==0) // 去前置0 len--; if (len==0) // a*b=0时特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i c[i]=z[len-1-i]+'0'; c[len]='\0'; } int main() { char s1[201],s2[201],ans[401]; scanf("%s%s",s1,s2); mul(s1,s2,ans); printf("%s\n",ans); return 0; } 问题描述 求两个大的正整数相除的商。 输入 第1行是被除数，第2行是除数。每个数均不超过100位。 输出 一行，相应的商的整数部分 输入样例 2376 24 输出样例 99 （1）编程思路。 将大整数用字符串保存，编写函数void div(char *a,char *b,char *q)实现q=a/b。 实现大整数除法的基本的思想是反复做减法，从被除数里最多能减去多少个除数，商就是多少。但是不能一个一个地减除数，这样既慢又不好处理。 实际处理方法应该这样，将除数扩大10倍、100倍、…或10k倍，使得除数和被除数等长，之后再进行减法操作，依次减除数的10k倍、…、除数的100倍、除数的10倍、除数本身。每次记下够减的次数，所得结果就是商。 下面以231568除以328为例进行说明。 先将除数328扩大1000倍，即后面加上3个0，使得除数328000与被除数231568等长，231568减去328000，不够减，因此记下减的次数为0；之后，去掉除数后面的1个0，得到32800（即除数扩大100倍），231568减去32800，够减7次，余下 1968，同样记下减的次数为7；再去掉除数后面的1个0，得到3280（即除数扩大10倍），1968减3280，不够减，同样记下减的次数为0；再去掉除数后面的1个0，此时就是除数本身328，1968减328，够减6次，余下0，同样记下减的次数为6，结束运算。依次记下的减的次数为0706，去掉前导的0，商就是706。 （2）源程序。 #include #include void sub(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[111],y[111],z[111]; int len=len1; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(z,0,sizeof(z)); int i,j; for (i=len1-1,j=0;i>=0;i--,j++) x[j]=a[i]-'0'; for (i=len2-1,j=0;i>=0;i--,j++) y[j]=b[i]-'0'; int cf=0; for (i=0;i { z[i]=x[i]-y[i]+cf; if (z[i]<0) { z[i]+=10; cf=-1; } else cf=0; } while (len>0 && z[len-1]==0) // 去前置0 len--; if (len==0) // a-b=0时特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i c[i]=z[len-1-i]+'0'; c[len]='\0'; } int bigger(char *a,char *b) { if (strlen(a)>strlen(b)) return 1; if (strlen(a) if (strcmp(a,b)>=0) return 1; else return 0; } void div(char *a,char *b,char *q) { if (bigger(a,b)==0) // 被除数a小于除数b，商为0 { q[0]='0'; q[1]='\0'; return ; } int len1=strlen(a); int len2=strlen(b); int i; for (i=len2;i b[i]='0'; b[i]='\0'; for (i=0;i<=len1-len2;i++) { int times=0; while (bigger(a,b)) { times++; sub(a,b,a); } q[i]=times+'0'; b[strlen(b)-1]='\0'; } q[i]='\0'; for (i=0;q[i]=='0';i++); strcpy(q,&q[i]); } int main() { char a[115],b[115],q[115]; scanf("%s", a); scanf("%s", b); div(a,b,q); printf("%s\n",q); return 0; } 问题描述 用高精度计算出 S = 1!+2!+3!+?+n!（n≤50）。 其中“!”表示阶乘，例如：5! = 5×4×3×2×1。 输入格式 一个正整数n。 输出格式 一个正整数 S，表示计算结果。 输入样例 输出样例 （1）编程思路。 编写函数void bigNumMul(char a[],int b,char c[])实现一个大整数a乘以一个int型整数，得到乘积为大整数c。 编写函数void bigNumAdd(char a[],char b[],char c[])实现大整数c=a+b。 （2）源程序。 #include #include #define MAX_LEN 201 void bigNumAdd(char a[],char b[],char c[]) { int len1=strlen(a),len2=strlen(b); int x[MAX_LEN],y[MAX_LEN],z[MAX_LEN]; int len=len1>len2?len1:len2; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(z,0,sizeof(z)); int i; for (i=len1-1;i>=0;i--) x[len1-1-i]=a[i]-'0'; for (i=len2-1;i>=0;i--) y[len2-1-i]=b[i]-'0'; int cf=0; for (i=0;i { z[i]=(x[i]+y[i]+cf)%10; cf=(x[i]+y[i]+cf)/10; } z[len++]=cf; while (len>0 && z[len-1]==0) // 去前置0 len--; if (len==0) // a+b=0时特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i c[i]=z[len-1-i]+'0'; c[len]='\0'; } void bigNumMul(char a[],int b,char c[]) // C=a*b { int num[MAX_LEN]={0},result[MAX_LEN+10]={0}; // 将a中存储的字符串形式的整数转换到num中去， // num[0]对应于个位、num[1]对应于十位、…… int len1 = strlen(a); int i,j; for (i=len1-1,j=0;i>=0; i--) num[j++] = a[i] - '0'; int len2 =0; int t=b; do { len2++; t=t/10; } while (t!=0); for (i=0;i < len1; i++) result[i] = num[i]*b; // 统一处理进位问题 int len=len1+len2; for (i = 0; i < len; i++) { if (result[i] >= 10) { result[i+1] += result[i] / 10; result[i] %= 10; } } while (len>0 && result[len-1]==0) // 去前置0 len--; if (len==0) // a*b=0时特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i c[i]=result[len-1-i]+'0'; c[len]='\0'; } int main() { char a[MAX_LEN],s[MAX_LEN]; int n,i; scanf("%d",&n); a[0]='1', a[1]='\0'; s[0]='1'; s[1]='\0'; for (i=2;i<=n;i++) { bigNumMul(a,i,a); bigNumAdd(s,a,s); } printf("%s\n",s); return 0; } 问题描述 Hillwer编码的转换规则如下：对于每一条原码S，保证仅由26个大写字母组成。将每个字母后移R位，得到中转码S1（当S=‘XYZ’，R=2时，S1=‘ZAB’。即变成当前字母后R个字母，超过‘Z’则从‘A’开始）。接着，将中转码进行“符转数”操作，将S1每一位的ACS码（即ASCLL码）相乘，得到数串Q。转换后的编码即为Q。 输入 第1行，读入n，R。第2~n+1行，每行一条编码S。 输出 共n*2行，奇数行，每行一条中转码S1； 偶数行，每行一条转换后的编码Q。 输入样例 2 6 HELLOWORLD LETUSGO 输出样例 NKRRUCUXRJ 10167740864629920000 RKZAYMU 20957073637500 （1）编程思路1。 将S1中每一个字符的ASCLL码相乘得到的数串Q超出了长整数的表示范围，因此需要进行高精度乘法运算。 编写函数void bigNumMul(char a[],int b,char c[])实现一个大整数a乘以一个int型整数，得到乘积为大整数c。 （2）源程序1。 #include #include void bigNumMul(char a[],int b,char c[]) // C=a*b { int num[1300]={0},result[1300+10]={0}; // 将a中存储的字符串形式的整数转换到num中去， // num[0]对应于个位、num[1]对应于十位、…… int len1 = strlen(a); int i,j; for (i=len1-1,j=0;i>=0; i--) num[j++] = a[i] - '0'; int len2 =0; int t=b; do { len2++; t=t/10; } while (t!=0); for (i=0;i < len1; i++) result[i] = num[i]*b; // 统一处理进位问题 int len=len1+len2; for (i = 0; i < len; i++) { if (result[i] >= 10) { result[i+1] += result[i] / 10; result[i] %= 10; } } while (len>0 && result[len-1]==0) // 去前置0 len--; if (len==0) // a*b=0时特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i c[i]=result[len-1-i]+'0'; c[len]='\0'; } int main() { int n,r; scanf("%d%d",&n,&r); r=r%26; char s[600],q[1300]; while(n--) { scanf("%s",s); q[0]='1'; q[1]='\0'; int i; for (i=0;s[i]!='\0';i++) { if (s[i]+r<='Z') s[i]=s[i]+r; else s[i]=s[i]+r-'Z'+'A'-1; bigNumMul(q,(int)s[i],q); } printf("%s\n",s); printf("%s\n",q); } return 0; } （3）编程思路2。 在上面的源程序1中，实现大整数乘法时，保存大整数的数组num中，每个数组元素保存1位数字，这样既浪费存储空间，又耗费计算时间。实际上，一个数组元素中可以保存大整数的6位数字，因为它与一个ASCII码（最多为3位整数）相乘，不会超过int型整数的表数范围。下面的源程序2就是按这个想法编写的。 （4）源程序2。 #include #include #define MOD 1000000 void work(char s[]) { int q[205]; memset(q,0,sizeof(q)); int len=1; q[1]=1; int i,j; for (i=0;s[i]!='\0';i++) { int t=(char)s[i]; for (j=1;j<=len;j++) q[j]=q[j]*t; int cf; for (j=1;j<=len;j++) { cf=q[j]/MOD; q[j]=q[j]%MOD; q[j+1]+=cf; } if (q[len+1]!=0) { len++; } } printf("%d",q[len]); for (i=len-1;i>=1;i--) printf("%06d",q[i]); printf("\n"); } int main() { int n,r; scanf("%d%d",&n,&r); while (n--) { char s[605]; scanf("%s",s); int i; for (i=0;s[i]!='\0';i++) { s[i]=(s[i]-'A'+r)%26+'A'; } printf("%s\n",s); work(s); } return 0; }习题68
68-1 大整数除法
68-2 阶乘之和
68-3 Hillwer编码