【算法基础】高精度加法（C++描述）

2021 年 03 月 20 日

1449 次浏览

444字数

【算法分析】

输入两个数到变量中，然后用赋值语句求它们的和后输出。但是，我们知道，在C/C++语言中任何数据类型都有一定的表示范围。当两个被加数很大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图。这样我们方便写出两个整数相加的算法。

![](https://blog.fivk.cn/usr/uploads/2021/03/2254028990.png)

如果我们用数组a、b分别储存加数和被加数，用数组c存储结果。则上例有a[1]=6, a[2]=5, a[3]=8, b[2]=5, c[4]=1, c[3]=1, c[2]=1, c[1]=1。

* 因此，算法描述如下：

```C
int c[100];
void add(int a[],int b[])			//a、b、c都是数组，分别存储被加数、加数、结果
{
	int i=1,x=0;				//x是进位
	while((i<=a数组长度)||(i<=b数组长度))
	{
		c[i]=a[i]+b[i]+x;		//第i位相加并加上次的进位
		x=c[i]%10;			//向高位进位
		c[i]%=10;			//存储第i位的值
		i++;				//位置下标变量
	}
}
```

通常，读入的两个整数可以用字符串来存储，程序设计如下：

```C
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int main(void)
{
	char a1[100], b1[100];
	int a[100] = { 0 }, b[100] = { 0 }, c[100] = { 0 }, lena, lenb, lenc, i, x;
	gets_s(a1);
	gets_s(b1);			//输入加数与被加数
	lena = strlen(a1);
	lenb = strlen(b1);

for (i = 0; i <= lena - 1; i++) a[lena - i] = a1[i] - 48;	//被加数放入a数组
	for (i = 0; i <= lenb - 1; i++) b[lenb - i] = b1[i] - 48;	//加数放入b数组
	lenc = 1;
	x = 0;

while (lenc <= lena || lenc <= lenb)
	{
		c[lenc] = a[lenc] + b[lenc] + x;	//两数相加
		x = c[lenc] / 10;
		c[lenc] %= 10;
		lenc++;
	}

c[lenc] = x;
	if (c[lenc] == 0) lenc--;		//处理最高进位

for (i = lenc; i >= 1; i--)
		cout << c[i];				//输出结果

cout << endl;
	return 0;
}

```

最后修改：2021 年 09 月 12 日