AcWing 791. 高精度加法


观察题目

第一眼看题:这不就是大淼题 /(/text {A + B}/) 吗?

再一看,看到数据范围 /(1 /leq 整数长度 /leq 100000/),很显然,/(C++/) 中自带的数据类型肯定不行。

怎么办?

算法思路

观察到题目给出的整数长度数组存的下,因此我们可以先读入两个字符串,然后转成数组。

还记得小学一年级老师教的“列竖式”吗?

回想一下,列竖式有这样几个步骤:

  1. 从最低位开始算起;
  2. 首先把这一位对应的两个数字相加,如果相加的和 $ /geq 10$,则需要进位,让下一位 $ + 1$(这里注意如果有进位,在进行下一次操作时还要加上之前进位的值);
  3. 重复 /(2/) 操作。

同理,我们可以用代码模拟这个过程。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

vector<int> add(vector<int> a, vector<int> b)
{
    int t = 0; //t存进位
    vector<int> c; //c存答案
    for (int i = 0; i < a.size() || i < b.size(); i ++ )
    {
        if (i < a.size())
        {
            t += a[i]; //这里要+=,加上上次的进位
        }
        if (i < b.size())
        {
            t += b[i]; //同上
        }
        c.push_back(t % 10);
        t /= 10;
    }
    if (t)
    {
        c.push_back(1);
    }
    return c;
}

int main()
{
    string x, y;
    cin >> x >> y;
    vector<int> a, b;
    //转数组
    for (int i = x.length() - 1; i >= 0; i -- )
    {
        a.push_back(x[i] - '0');
    }
    for (int i = y.length() - 1; i >= 0; i -- )
    {
        b.push_back(y[i] - '0');
    }
    auto z = add(a, b);
    for (int i = z.size() - 1; i >= 0; i -- )
    {
        printf("%d", z[i]);
    }
    return 0;
}

/(/text {Python}~yyds!/)

print(input() + input())

原创文章,作者:,如若转载,请注明出处:https://blog.ytso.com/277550.html

(0)
上一篇 2022年7月28日
下一篇 2022年7月28日

相关推荐

发表回复

登录后才能评论