C语言程序设计100例之（67）：大整数加法
例67 大整数加法
问题描述
求两个不超过200位的非负整数的和。
输入
有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。
输出
一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
输入样例
22222222222222222222
33333333333333333333
输出样例
55555555555555555555
（1）编程思路。
可以用一个字符串来保存200位整数。
编写函数void add(char *a,char *b,char *c)实现大整数c=a+b。
在函数中可以用数组unsigned x[201]来保存一个200 位的整数a，让x[0]存放个位数，x[1]存放十位数，x[2]存放百位数……。
实现两个大整数相加的方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10 则进位。
（2）源程序。
#include
#include
void add(char *a,char *b,char *c)
{
int len1=strlen(a),len2=strlen(b);
int x[201],y[201],z[205];
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'; } int main() { char s1[201],s2[201],ans[205]; scanf("%s%s",s1,s2); add(s1,s2,ans); printf("%s\n",ans); return 0; } 问题描述 给出两个二进制数a和b的01串，按二进制加法计算a+b并输出。 输入 第1行为一个整数T，表示测试用例的组数，之后T行，每行包括两个01串，每个串长不超过80位。 输出 对于每组测试用例，输出两个01串相加的结果（最简形式）。 输入样例 1001101 10010 1001001 11001 1000111 1010110 输出样例 1 1011111 2 1100010 3 10011101 （1）编程思路。 二进制数高精度加法，注意前置0的处理。 （2）源程序。 #include #include void binAdd(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[91],y[91],z[91]; 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)%2; cf=(x[i]+y[i]+cf)/2; } 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'; } int main() { char s1[91],s2[91],ans[91]; int n,i; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%s%s",s1,s2); binAdd(s1,s2,ans); printf("%d %s\n",i,ans); } return 0; } 问题描述 求两个大的正整数相减的差。 输入 共2行，第1行是被减数a，第2行是减数b(a > b)。每个大整数不超过200位，不会有多余的前导零。 输出 一行，即所求的差。 输入样例 9999999999999999999999999999999999999 9999999999999 输出样例 9999999999999999999999990000000000000 （1）编程思路。 可以用一个字符串来保存200位整数。 编写函数voidsub(char *a,char *b,char *c)实现大整数c=a-b。 在函数中可以用数组unsigned x[201]来保存一个200 位的整数a，让x[0]存放个位数，x[1]存放十位数，x[2]存放百位数……。 实现两个大整数相减的方法很简单，就是模拟小学生列竖式做减法，从个位开始逐位相减，小于0则向前借位补10。 （2）源程序。 #include #include void sub(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[210],y[210],z[210]; 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 main() { char a[210],b[210],c[210]; scanf("%s", a); scanf("%s", b); sub(a,b,c); printf("%s\n",c); return 0; } 问题描述 已知两个整数a和b，求a+b的值 输入 第一行包含一个整数T，即测试用例的数量。 以下T行，每行分别包含2个整数A、B（-10^50000 输出 输出应该包含T行，每个行都有一个整数，代表相应的和。 输入样例 1 2 -1 +2 输出样例 （1）编程思路。 由于a和b可能小于0，因此a+b分为4种情况： 1）a>=0，b>=0，则进行a+b； 2）a<0，b<0，则进行(-a)+(-b)； 3）a>=0，b<0，则进行a-(-b)；此时还需对a和(-b)进行大小比较，按比较情况执行a-(-b)或(-b)-a； 4）3）a<0，b>=0，则进行b-(-a)；此时还需对-a和b进行大小比较，按比较情况执行b-(-a)或(-a)-b。 （2）源程序。 #include #include void add(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[51000],y[51000],z[51000]; 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 sub(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[51000],y[51000],z[51000]; int len=len1; 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; 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; } int main() { int t; scanf("%d",&t); while(t--) { char a[51000],b[51000],ans[51000]; scanf("%s%s",a,b); if (a[0]=='+') strcpy(a,&a[1]); if (b[0]=='+') strcpy(b,&b[1]); int sign; if (a[0]!='-' && b[0]!='-') // a+b { add(a,b,ans); sign=0; } else if (a[0]=='-' && b[0]=='-') // -a-b=-(a+b) { add(&a[1],&b[1],ans); sign=1; } else if (a[0]!='-' && b[0]=='-') // a-b { if (bigger(a,&b[1])) { sub(a,&b[1],ans); sign=0; } else // b>a,a-b=-(b-a) { sub(&b[1],a,ans); sign=1; } } else // b-a { if (bigger(b,&a[1])) // b>a { sub(b,&a[1],ans); sign=0; } else // b { sub(&a[1],b,ans); sign=1; } } if (sign==1 && ans[0]!='0') printf("-"); printf("%s\n",ans); } return 0; }习题67
67-1 二进制加法
67-2 大整数减法
67-3 求和