數字根問題：HDU 1013 Digital Roots 遞歸求解

題目大意

輸入一個超長整數（以字符串形式給出），反覆計算各位數字之和，直到結果為個位數（0-9）為止。輸入 "0" 結束程序。

例如：1000 個 9 → 和為 9000 → 9+0+0+0=9 → 輸出 9。

算法設計

1. 大數存儲：字符數組逐位轉為整型數組
2. 首輪求和：遍歷數組累加得總和
3. 遞歸縮減：若總和 ≥ 10，拆分各位再求和，遞歸直到 < 10

代碼實現

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

char num[10000];
int a[10000];

int digitalRoot(int n) {
    if (n < 10) return n;
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return digitalRoot(sum);
}

void solve(char *s) {
    int len = strlen(s);
    for (int i = 0; i < len; i++) a[i] = s[i] - '0';
    int total = 0;
    for (int i = 0; i < len; i++) total += a[i];
    cout << digitalRoot(total) << endl;
}

int main() {
    while (cin >> num) {
        if (num[0] == '0') break;
        solve(num);
    }
    return 0;
}

優化提示

數字根存在數學公式：dr(n) = 1 + (n - 1) % 9（n>0 時），可直接 O(1) 計算。但本題數據規模較小，遞歸模擬足夠通過，且更直觀易懂。