1. Ý tưởng thuật toán

Khi thực hiện phép cộng thông thường, chúng ta căn chỉnh các chữ số theo hàng đơn vị, sau đó cộng từng cột từ phải sang trái. Nếu kết quả của một cột lớn hơn 9, chúng ta sẽ giữ lại chữ số hàng đơn vị và nhớ 1 sang cột tiếp theo bên trái. Thuật toán cộng số nguyên lớn cũng hoàn toàn tương tự như vậy, nhưng được thực hiện trên các chuỗi ký tự.

2. Phân tích chi tiết code

2.1. Code hoàn chỉnh

#include <iostream>
#include <cstring>
using namespace std;

void pad_numbers(char num1[], char num2[], int len1, int len2);

int main() {
    int carry = 0, digit_sum = 0, start_index = 0;
    static char str1[1001];
    static char str2[1001];

    cin.getline(str1, 1001);
    cin.getline(str2, 1001);

    int len1 = strlen(str1);
    int len2 = strlen(str2);
    pad_numbers(str1, str2, len1, len2);
    len1 = strlen(str1);
    len2 = strlen(str2);
    int result[len2];
    int pos = len2 - 1;

    for (int i = len1 - 1; i >= 0; i--) {
        digit_sum = (str1[i] - '0') + (str2[i] - '0') + carry;
        if (digit_sum >= 10) {
            digit_sum -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result[pos] = digit_sum;
        pos--;

        if (i == 1 && carry == 1){
            start_index = 0;
        }
        if (i == 1 && carry == 0){
            start_index = 1;
        }
    }

    int total_len = len2;
    for (int i = start_index; i < total_len; i++) {
        cout << result[i];
    }
    cout << endl;
    return 0;
}

void pad_numbers(char num1[], char num2[], int len1, int len2) {
    char temp;
    int diff = 0;

    if (len1 == len2) {
        for (int i = 1; i <= len1; i++) {
            temp = num1[len1 - i];
            num1[len1 - i + 1] = temp;
        }
        num1[0] = '0';
        for (int i = 1; i <= len2; i++) {
            temp = num2[len2 - i];
            num2[len2 - i + 1] = temp;
        }
        num2[0] = '0';
    }

    if (len1 > len2) {
        for (int i = 1; i <= len1; i++) {
            temp = num1[len1 - i];
            num1[len1 - i + 1] = temp;
        }
        num1[0] = '0';
        diff = len1 - len2;
        for (int i = 1; i <= len2; i++) {
            temp = num2[len2 - i];
            num2[len2 - i + diff + 1] = temp;
        }
        for (int i = 0; i <= diff; i++) {
            num2[i] = '0';
        }
    }

    if (len2 > len1) {
        for (int i = 1; i <= len2; i++) {
            temp = num2[len2 - i];
            num2[len2 - i + 1] = temp;
        }
        num2[0] = '0';
        diff = len2 - len1;
        for (int i = 1; i <= len1; i++) {
            temp = num1[len1 - i];
            num1[len1 - i + diff + 1] = temp;
        }
        for (int i = 0; i <= diff; i++) {
            num1[i] = '0';
        }
    }
}

2.2. Hàm pad_numbers

Hàm này có nhiệm vụ căn chỉnh độ dài của hai số bằng cách thêm các số 0 vào phía trước. Mục đích là để hai chuỗi số có cùng độ dài, giúp việc thực hiện phép cộng từng cột trở nên dễ dàng hơn.

Trường hợp 1: len1 == len2

Khi hai số có độ dài bằng nhau, ta chỉ cần thêm một ký tự '0' vào đầu mỗi số. Để làm điều này, ta phải dịch toàn bộ chuỗi sang phải một vị trí, sau đó gán phần tử đầu tiên (index 0) bằng '0'.

if (len1 == len2) {
    // Ví dụ: num1 = "143"
    // Ý tưởng: dịch phải -> "0143"
    for (int i = 1; i <= len1; i++) {
        temp = num1[len1 - i];
        num1[len1 - i + 1] = temp;
    }
    num1[0] = '0';
    // Làm tương tự với num2
}

Trường hợp 2: len1 > len2

Nếu số thứ nhất dài hơn số thứ hai, ta thực hiện hai việc:

• Số thứ nhất (dài hơn): thêm một '0' vào đầu (tương tự trên).
• Số thứ hai (ngắn hơn): dịch phải các chữ số của nó, nhưng số lượng vị trí cần dịch phải đủ để khi thêm các số 0 vào phía trước, tổng độ dài của nó bằng độ dài của số thứ nhất (sau khi đã thêm '0').

// Ví dụ: num1 = "5262", num2 = "153". len1=4, len2=3
// Sau khi xử lý, mong muốn: num1 = "05262", num2 = "00153"

// Bước 1: Thêm '0' vào đầu num1 -> num1 = "05262"
for (int i = 1; i <= len1; i++) { ... } // Mã dịch phải
num1[0] = '0';

// Bước 2: Xử lý num2
// diff = len1 - len2 = 1
// Dịch phải các chữ số của num2. Ví dụ:
// Bắt đầu từ cuối, lấy chữ số 3 (index 2), gán vào vị trí 2+1+1 = 4. Kết quả: "1533"
// Lấy chữ số 5 (index 1), gán vào vị trí 1+1+1 = 3. Kết quả: "15353"
// Lấy chữ số 1 (index 0), gán vào vị trí 0+1+1 = 2. Kết quả: "15153"
// Sau đó, thay thế các vị trí từ 0 đến diff (0..1) bằng '0' -> "00153"
for (int i = 1; i <= len2; i++) {
    temp = num2[len2 - i];
    num2[len2 - i + diff + 1] = temp;
}
for (int i = 0; i <= diff; i++) {
    num2[i] = '0';
}

Trường hợp 3: len2 > len1

Nguyên lý hoàn toàn tương tự như trường hợp 2, nhưng vai trò của hai số được đổi chỗ cho nhau.

2.3. Hàm main

Trong main, sau khi gọi pad_numbers, hai chuỗi đã có độ dài bằng nhau. Phép cộng được thực hiện như sau:

for (int i = len1 - 1; i >= 0; i--) {
    // Lấy từng chữ số từ cuối chuỗi, chuyển từ char sang int bằng cách trừ '0'
    digit_sum = (str1[i] - '0') + (str2[i] - '0') + carry;
    if (digit_sum >= 10) {
        digit_sum -= 10; // Giữ lại chữ số hàng đơn vị
        carry = 1;      // Nhớ 1 cho lần tính tiếp theo
    } else {
        carry = 0;
    }
    result[pos] = digit_sum; // Lưu kết quả vào mảng
    pos--;

    // Kiểm tra sau khi cộng xong cột thứ hai (từ phải sang), 
    // nếu vẫn còn nhớ (carry == 1) thì bắt đầu in từ vị trí đầu tiên của mảng result
    // nếu không còn nhớ thì bỏ qua vị trí đầu tiên (vì nó là số 0 do padding)
    if (i == 1 && carry == 1){
        start_index = 0;
    }
    if (i == 1 && carry == 0){
        start_index = 1;
    }
}

// In kết quả từ vị trí start_index
for (int i = start_index; i < total_len; i++) {
    cout << result[i];
}

Biến carry lưu giá trị cần nhớ. Biến start_index giúp xác định vị trí bắt đầu in kết quả. Nếu kết quả của phép cộng có số lượng chữ số nhiều hơn số ban đầu (do bị nhớ lên vị trí đầu tiên vốn là '0' do padding), ta in từ vị trí 0. Ngược lại, ta bỏ qua vị trí đầu tiên đó để kết quả hiển thị không có số 0 vô nghĩa ở đầu.