書頁數字統計問題：遞迴分解法計算 0-9 各數字出現次數

給定書籍總頁數 page，統計頁碼 1 到 page 中數字 0-9 各自出現的總次數。本文提供遞迴分解演算法，時間複雜度 O(log₁₀ page)，附完整 C 實作與邊界處理。

問題分析

逐頁轉字串統計雖直觀，但 page ≤ 10^9 時會超時。利用位權分解：

• 個位：每 10 頁循環 0-9 一次。
• 十位：每 100 頁循環 10 次 0-9。
• 以此類推，高位權重為 10^k。

遞迴函數 count(num) 處理單一數字 num 的各位統計，主迴圈累加 1 到 page。

C 程式碼實作

#include <stdio.h>

int digitCount[10] = {0};  // 全域累加器

// 遞迴分解單一數字的各位
void countDigits(int num) {
    if (num == 0) return;           // 0 不計入（頁碼從 1 開始）
    int d = num % 10;
    digitCount[d]++;
    countDigits(num / 10);
}

// 遍歷所有頁碼
void compute(int page) {
    for (int i = 1; i <= page; ++i) {
        countDigits(i);
    }
}

int main() {
    int page = 0;
    printf("請輸入總頁數：");
    scanf("%d", &page);

    if (page <= 0) {
        printf("輸入不合法！\n");
        return 1;
    }

    compute(page);

    for (int i = 0; i <= 9; ++i) {
        printf("數字 %d 出現 %d 次\n", i, digitCount[i]);
    }
    return 0;
}

範例驗證

輸入 page = 13：

頁碼：1 2 3 4 5 6 7 8 9 10 11 12 13
統計：
0: 1次 (10)
1: 6次 (1,10,11x2,12,13)
2: 2次 (2,12)
3: 2次 (3,13)
4-9: 各 1 次

優化方向（大數據量）

若 page > 10^7，O(page log page) 仍可能緩慢。可採用「按位權數學公式」直接計算，複雜度降為 O(log₁₀ page)；核心公式參考《程式設計珠玑》第 1 章或 LeetCode 233 題解法。

常見錯誤

• 忘記初始化 digitCount 陣列為 0。
• 遞迴基準情況處理 num == 0 時直接返回，避免統計前導零。
• 頁碼從 1 開始，不可包含 0。

總結

書頁數字統計是經典遞迴分解練習。理解「逐位累加」與「數學公式」兩種思路，可應對從教學級到競賽級的不同資料範圍需求。