C語言經典遞歸問題：五猴分桃子求最少數量

問題重述

海灘上有一堆桃子，五只猴子依次分桃：每只猴子將當前桃子分成 5 份，多 1 個扔入海中，拿走 1 份。第五只猴子操作後結束。求最初桃子最少數量。

數學建模

設第 i 只猴子操作前桃子數為 x_i，操作後剩餘 x_{i+1}。則：

x_i = 5 * a_i + 1 （a_i 為每份數量）

x_{i+1} = 4 * a_i = 4 * (x_i - 1) / 5

要求所有 x_i 為整數，且 x_6 為最終剩餘（可為 0）。反向推導更簡單：

設第 5 只猴子操作前桃子為 x_5，操作後剩 x_6。則 x_5 = (5 * x_6) / 4 + 1，需 x_6 為 4 的倍數。從 x_6 = 0 開始反推：

• x_6 = 0 → x_5 = 1（非 5k+1）❌
• x_6 = 4 → x_5 = 6 ❌
• x_6 = 8 → x_5 = 11 ❌
• ...
• x_6 = 4^4 = 256 → 依次反推得 x_1 = 3121 ✅

通用公式

對於 m 只猴子，最少桃子數 = m^m - (m - 1)。此處 m=5，5^5 - 4 = 3125 - 4 = 3121。

C語言實現（暴力搜索與反向推導）

方法一：正向模擬暴力搜索

#include 
#include 

bool check(int n) {
    for (int i = 0; i < 5; i++) {
        if (n % 5 != 1) return false;
        n = 4 * (n - 1) / 5;
    }
    return true;
}

int main() {
    for (int n = 1; ; n++) {
        if (check(n)) {
            printf("最少桃子數: %d\n", n);
            break;
        }
    }
    return 0;
}

方法二：反向推導（高效）

#include 

int main() {
    int x = 0; // 第6只猴子前剩餘，從0開始嘗試4的倍數
    while (true) {
        int cur = x;
        bool ok = true;
        for (int i = 0; i < 5; i++) {
            // 反向：前一狀態 = (5 * 當前) / 4 + 1
            if (cur % 4 != 0) { ok = false; break; }
            cur = 5 * cur / 4 + 1;
        }
        if (ok) {
            printf("最少桃子數: %d\n", cur);
            break;
        }
        x += 4; // 每次增加4保證整除
    }
    return 0;
}

驗證過程

初始: 3121
猴1: (3121-1)/5=624 拿走624 剩2496
猴2: (2496-1)/5=499 拿走499 剩1996
猴3: (1996-1)/5=399 拿走399 剩1596
猴4: (1596-1)/5=319 拿走319 剩1276
猴5: (1276-1)/5=255 拿走255 剩1020
每步均滿足多1個條件。

結論

海灘上原來最少有 3121 個桃子。