AcWing 791. 高精度加法

[toc]

第一讲 基础算法 - 04高精度 | Akari的小站

AcWing 791. 高精度加法【简单】

1 题目描述

给定两个正整数（不含前导 0），计算它们的和。

输入格式:
共两行，每行包含一个整数。

输出格式:
共一行，包含所求的和。

数据范围:
1 <= 整数长度 <= 100000

输入样例:

12
23

输出样例：

35

2 算法步骤

  1. 高精度数字利用字符串读入
  2. 把字符串翻转存入两个整型数组 A, B
  3. 从低位到高位, 累加, 进位, 存余 *
  4. 把数组 C 从高位到低位依次输出
$fileName

3 时间复杂度

时间复杂度: O(n)

4 AC代码

4.1 数组

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int A[N], B[N], C[N];
int la, lb, lc;

void add(int A[], int B[], int C[]);

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a >> b;
    la = a.size(), lb = b.size(), lc = max(la, lb);
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入
    for (int i = lb - 1; ~i; i -- ) B[lb - 1 - i] = b[i] - '0';     // 翻转存入
    add(A, B, C);
    for (int i = lc - 1; ~i; i -- ) printf("%d", C[i]);     // 逆序输出
    
    return 0;
}

void add(int A[], int B[], int C[]){
    for (int i = 0; i < lc; i ++ ){
        C[i] += A[i] + B[i];        // 累加
        C[i + 1] += C[i] / 10;      // 进位
        C[i] %= 10;                 // 存余
    }
    if (C[lc]) lc ++ ;              // 处理最高位
}

3.2 vector

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef vector<int> VI;
VI A, B, C;

void add(VI &A, VI &B, VI &C);

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');      // 翻转存入
    for (int i = b.size() - 1; ~i; i -- ) B.push_back(b[i] - '0');      // 翻转存入
    add(A, B, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];     // 逆序输出
    
    return 0;
}

void add(VI &A, VI &B, VI &C){
    int t = 0;
    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(t);      // 处理最高位
}