算法題：統計 1 到 n 整數中數字 1 出現的次數（C語言遞歸解法）

編輯：關於C語言

問題描述

輸入整數 n，求 1 到 n 的十進制表示中數字 1 總共出現多少次。例如 n=12，數字 1 出現在 1、10、11(兩個)、12 共 5 次。

遞歸分解思路

將數字按最高位拆分：

最高位為 1 的計數：若最高位 >1，則滿計數 10^(k-1)；若 =1，則計數 低位數值 + 1。
其餘位數 1 的計數：最高位數字 × (位數-1) × 10^(k-2)。
遞歸處理低位部分：去掉最高位後的子問題。

核心代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int PowerBase10(size_t n) {
    int r = 1;
    for (size_t i = 0; i < n; ++i) r *= 10;
    return r;
}

int NumberOf1(const char* strN) {
    if (!strN || *strN < '0' || *strN > '9') return 0;
    int first = *strN - '0';
    size_t len = strlen(strN);
    if (len == 1) return first == 0 ? 0 : 1;

    // 最高位 1 的個數
    int numFirst = (first > 1) ? PowerBase10(len - 1)
                 : (first == 1) ? atoi(strN + 1) + 1 : 0;

    // 其餘位 1 的個數
    int numOther = first * (len - 1) * PowerBase10(len - 2);

    // 遞歸低位
    int numRecursive = NumberOf1(strN + 1);

    return numFirst + numOther + numRecursive;
}

int NumberOf1Between1AndN(int n) {
    if (n <= 0) return 0;
    char buf[50];
    sprintf(buf, "%d", n);
    return NumberOf1(buf);
}

int main(void) {
    printf("result = %d\n", NumberOf1Between1AndN(12)); // 輸出 5
    return 0;
}