C语言程序设计100例之（67）：大整数加法

本文主要是介绍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 <stdio.h>

#include <string.h>

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<len;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<len;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;

}

习题67

67-1 二进制加法

问题描述

给出两个二进制数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 <stdio.h>

#include <string.h>

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<len;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<len;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;

}

67-2 大整数减法

问题描述

求两个大的正整数相减的差。

输入

共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 <stdio.h>

#include <string.h>

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<len;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<len;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;

}

67-3 求和

问题描述

已知两个整数a和b，求a+b的值

输入

第一行包含一个整数T，即测试用例的数量。

以下T行，每行分别包含2个整数A、B（-10^50000<A、B<32768）。

输出

输出应该包含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 <stdio.h>

#include <string.h>

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<len;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<len;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<len;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<len;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)<strlen(b)) return 0;

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<a,b-a=-(a-b)

{

sub(&a[1],b,ans);

sign=1;

}

if (sign==1 && ans[0]!='0') printf("-");

printf("%s\n",ans);

}

return 0;

}

这篇关于C语言程序设计100例之（67）：大整数加法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程