14.高精度加法

阅读数: 次 2020-11-29

字数：842字 | 预计阅读时长：3分钟

作者：X3B0A1

1.0 问题
1.1 思路
1.2 完整代码
1.3 时间复杂度分析

1.0 问题

题目：P1601

在我们熟悉的数据类型中，能够储存的最大的数也只是longlong的范围。

虽然有些编译器也提供__int128类型，但是最多也只能表示40位左右的数，大小依然有限，而且适用范围也很受限。

那么，又没有办法来模拟非常长的整数呢？

~~所以用python他不香么，自带高精度还有各种库~~

~~手动 @€€￡（doge~~

1.1 思路

既然变量不能储存大数，我们可以尝试使用数组来储存一个数。

用数组的每一位来储存那个数字上的一位，也就是说，用一个长度为n的数组记录一个n位数字。

那么，问题又来了，我们如何进行加法运算呢

首先，回顾一下小学学习的竖式计算：

  1 9 1
+ 9 8 1
--------
1 1 7 2

可以看到，用竖式计算时，为了保证进位正确，是从低位向高位运算的

我们可以模拟这个运算方法：

首先为了方便读入，使用string直接读入大数

将string类型的数转换为数字，并为了进位方便，倒叙存储在数组内

len1 = str1.length();
len2 = str2.length();
//从 len - 1 开始到0遍历数组，减去1是因为数组下标从0开始，方便操作
for(int i = len1 - 1; i >= 0; i--){
    //转换为数字
    num1[len1 - i] = str1[i] - '0';
}
for(int i = len2 - 1; i >= 0; i--){
    num2[len2 - i] = str2[i] - '0';
}

遍历数组，对于每一组数，先两个数加起来：

1	sum[i] += num1[i] + num2[i];

然后把两数的和对10取整，即进位。

例如，两数的和为9，对10取整为0，即进位为0；两数的和为19，对10取整为1，即进1位。

1	sum[i + 1] = sum[i] / 10;

处理完进位后，把两数的和对10取余，留下个位。

例如，和为9，对10取余，留下个位为9；和为19，对10取余，留下个位为9。

1	sum[i] %= 10;

最后将数组倒叙输出即可。

1.2 完整代码

根据上面的描述，可以得到如下代码：

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
const int MAXn = 2333;
int num1[MAXn], num2[MAXn], sum[MAXn];
int len1, len2;

int main(){

    //读入
    string str1, str2;
    cin >> str1 >> str2;
    //转换
    len1 = str1.length();
    len2 = str2.length();
    //从 len - 1 开始到0遍历数组，减去1是因为数组下标从0开始，方便操作
    for(int i = len1 - 1; i >= 0; i--){
        //倒叙存储         把字符转换为数字
        num1[len1 - i] = str1[i] - '0';
    }
    for(int i = len2 - 1; i >= 0; i--){
        num2[len2 - i] = str2[i] - '0';
    }

    //进行加运算
    int len = max(len1, len2);
    for(int i = 0; i <= len; i++){
        //此处使用“+=” 是因为可能有进位
        sum[i] += num1[i] + num2[i];
        //处理进位  直接把进的为赋值给sum[i - 1]
        sum[i + 1] = sum[i] / 10;
        //保留个位
        sum[i] %= 10;
    }

    //输出
    //进位有可能导致位数增加1
    if(sum[len + 1]){
        len++;
    }
    //倒叙输出
    for(int i = len; i >0; i--){
        cout << sum[i];
    }

    return 0;
}

1.3 时间复杂度分析

该算法次数最多的循环为最大数的数位次，时间复杂度即为
$O(n)$

本文作者： 益题 Yitee
发布时间： 2020-11-29
最后更新： 2021-08-19
本文标题： 14.高精度加法
本文链接： https://yitee.top/posts/51142.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！