[C++] Cộng hai số có giá trị lớn

Tính tổng của hai số cách nhau bởi dấu cách, một bài toán rất đơn giản nhưng điều đặc biệt ở đây nằm ở điều kiện của Input: a, b <= 10^18.

Với các kiểu dữ liệu mặc định thì miền giá trị chỉ nằm trong khoảng 8 bytes ~ 10 chữ số, vậy chúng ta cần phải tìm cách khác để xử lý input.

Ý tưởng ở đây là sử dụng hai chuỗi kí tự để nhập a và b, sau đó cộng từng phần từ với nhau. Chúng ta sẽ cần tới hai vòng lặp. Giả thiết độ dài của a luôn >= b, vòng lặp thứ nhất duyệt hết độ dài của chuỗi dài hơn và vòng lặp thứ hai theo chuỗi còn lại. Trong vòng lặp với b kết quả sẽ là tổng phần tử của a và phần tử tương ứng của b. Kết thúc vòng lặp với b thì tổng chỉ còn bằng phần tử của a.

Để đảm bảo chuỗi a luôn là chuỗi có độ dài lớn hơn, ta sẽ sử dụng hàm swap để đổi chỗ nếu a < b.

if(a.length() < b.length()) {
        swap(a, b);
    }

Theo quy tắc của phép cộng thì thứ tự cộng các chữ số là từ phải qua trái trong khi ta duyệt các phần tử của mảng từ trái qua phải, vậy để đảm bảo đúng quy tắc, chúng ta cần phải đảo ngược lại thứ tự của a và b.

void rev(string &x) {
    char temp;
    for(int i = 0; (int)(i < x.length() / 2); i++) {
        temp = x[i];
        x[i] = x[x.length() - i - 1];
        x[x.length() - i - 1] = temp;
    }
}

Công việc còn lại chỉ là cộng từng phần tử của a với phần tử tương ứng của b, sử dụng hai vòng lặp lồng nhau

for(int i = 0; i < (int)a.length(); i++) {
        if(i < (int)b.length()) {
        }
}

Một lưu ý là các phần tử của a và b sẽ có kiểu char lên muốn cộng theo quy tắc của số thập phân thông thường ta phải lấy giá trị cuẩ phần tử trừ đi 48(Xem bảng mã ASCII)

Code:

#include <iostream>
#include <string>

using namespace std;


void rev(string &x) {
    char temp;
    for(int i = 0; (int)(i < x.length() / 2); i++) {
        temp = x[i];
        x[i] = x[x.length() - i - 1];
        x[x.length() - i - 1] = temp;
    }
}

void sumBigInt(string a, string b) {
    if(a.length() < b.length()) {
        swap(a, b);
    }
    rev(a);
    rev(b);
    string result = "";
    int sum;
    int temp = 0;
    for(int i = 0; i < (int)a.length(); i++) {
        if(i < (int)b.length()) {
            if(temp) {
                sum = a[i] + b[i] - 95;
            } else {
                sum = a[i] + b[i] - 96;
            }
            if(sum < 10) {
                temp = 0;
                result += sum + 48;
            } else {
                temp = 1;
                result += sum % 10 + 48;
            }
        } else if(i != (int)a.length() - 1){
            if(temp) {
                sum = a[i] - 47;
            } else {
                sum = a[i] - 48;
            }
            if(sum < 10) {
                temp = 0;
                result += sum + 48;
            } else {
                temp = 1;
                result += sum % 10 + 48;
            }
        } else if(i == (int)a.length() - 1) {
            if(temp) {
                sum = a[i] - 47;
            } else {
                sum = a[i] - 48;
            }
            if(sum < 10) {
                result += sum + 48;
            } else {
                result += sum % 10 + 48;
                result += 49;
            }
        }
    }
    rev(result);
    cout<<result;
}

int main()
{
    string a, b;
    cin>>a>>b;
    sumBigInt(a, b);
    return 0;
}