高精度运算

我们都知道,每一种数据类型的出从空间都有限,比如整数类型,一般用的是int(-2147483648~2147483647),如果数据太长了就用long long,数据如果再长一点就要用到unsigned long long,有些要用到一些编译器提供的_int128。那么万一万一,数据更长怎么办?这就需要我们的算法来模拟高精度的运算。
(以下是个人的解法,不一定最优,仅供参考)

高精度加法

题目

高精度加法,相当于 a+b problem,不用考虑负数

输入格式

分两行输入。$ a,b\leq 10^{500} $

输出格式

输出只有一行,代表 a+b 的值。

思路

这题如果是单纯输入两个数a和b,然后相加的话,就太简单了,不需要动用算法;因此题目也说了,是高精度算法,数字将会是很大的,大于unsigned long long ,因此我们应该考虑其他方式。那么我们可以考虑一种特殊的加法算数方式——竖式加法。
先看一下思路:

下面是演示代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<string>
#include<algorithm>//包含max函数
using namespace std;
int A[500], B[500], C[500];//这个列表定义要放在外面的话可以自动设置等于0,如果放在里面要手动设置
int main()
{
string a,b;//以字符串的形式定于数字
cin>>a>>b;//输入数字
int lena=a.length(), lenb=b.length();//定义数字长度
int len=max(lena,lenb);//将最长数字长度定义为较长那个的长度
for (int i=0;i<lena;i++)//通过倒序一个一个将数字输入到列表中
{
A[i]=a[lena-i-1]-'0';//倒叙输入,-'0'是因为数字的ASCII码不是直接对应它本身,比如'1'的ASCII码是49,'0'的ASCII码是48,所以就等于是ASCII码与数值的转换
}
for (int i=0;i<lenb;i++)
{
B[i]=b[lenb-i-1]-'0';
}
for (int i=0;i<len;i++)//两组数相加
{
C[i] += A[i] + B[i];
C[i+1] += C[i] / 10;//进位
C[i] %= 10;//保留进位后的个位

}
if (C[len])//如果进位,将长度增加
{
len++;
}
for (int i = len-1 ; i >= 0; i--)//因为一开始是倒序输入,现在将顺序倒转回去输出
{
cout << C[i];
}
return 0;
}