HDU 1013 大整數加法：模擬算法 C++ 實現詳解

題目背景

HDU 1013 "A + B Problem II" 要求計算兩個超長整數之和，位數遠超內置類型範圍，必須採用數組模擬人工豎式加法。

核心思路

1. 字符串反轉存儲：將輸入字符串逐字符轉為數字，逆序存入數組（個位對應下標 0），便於按位運算。
2. 逐位相加帶進位：從低位向高位遍歷，對應位相加並處理進位。
3. 結果輸出：最高位可能產生新進位，需檢查並輸出；最後逆序打印結果數組。

關鍵代碼解析

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

int num1[1010], num2[1010], result[1010];
char str1[1010], str2[1010];

void add(int len1, int len2) {
    // 字符轉數字並反轉存儲
    for (int i = 0; i < len1; i++) num1[i] = str1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++) num2[i] = str2[len2 - 1 - i] - '0';

    int carry = 0, k = 0;
    for (int i = 0; i < len1 || i < len2; i++) {
        int sum = num1[i] + num2[i] + carry;
        result[k++] = sum % 10;
        carry = sum / 10;
    }
    if (carry) result[k++] = carry;  // 處理最高位進位

    // 輸出格式：原數字 + 原數字 = 結果
    cout << str1 << " + " << str2 << " = ";
    for (int i = k - 1; i >= 0; i--) cout << result[i];
    cout << endl;
}

int main() {
    int T; cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        memset(num1, 0, sizeof(num1));
        memset(num2, 0, sizeof(num2));
        memset(result, 0, sizeof(result));
        cin >> str1 >> str2;
        cout << "Case " << cas << ":" << endl;
        add(strlen(str1), strlen(str2));
        if (cas < T) cout << endl;  // 最後一組無空行
    }
    return 0;
}

易錯點提醒

• 每組測試數據必須完整清零所有數組，否則殘留數據導致 WA
• 輸出格式嚴格遵循 "Case n:" 換行、"a + b = result"、組間空行
• 數組大小預留充足（題目 1000 位，開 1010 保險）

複雜度分析

時間 O(max(len1, len2))，空間 O(max(len1, len2))，完美滿足題目要求。