C語言經典遞歸題：猴子吃桃問題數學建模與代碼實現

猴子吃桃問題：逆向思維與遞歸/迭代求解

問題重述

猴子第一天摘 N 個桃子，吃掉一半再多吃 1 個。第二天對剩餘桃子同樣操作。第 10 天早上只剩 1 個。求第一天摘了多少個？

數學建模（逆向推導）

設第 k 天早上剩 a_k 個。

• 第 10 天：a_10 = 1。
• 第 k 天吃掉：a_k / 2 + 1，剩 a_{k+1} = a_k - (a_k/2 + 1) = a_k/2 - 1。
• 逆向：a_k = 2 * (a_{k+1} + 1)。

遞歸實現

#include <stdio.h>

int peaches_recursive(int day) {  // day: 當前天數 (1-10)
    if (day == 10) return 1;      // 第10天剩1個
    return 2 * (peaches_recursive(day + 1) + 1);
}

int main() {
    printf("第一天摘了 %d 個桃子\n", peaches_recursive(1));  // 輸出 1534
    return 0;
}

迭代實現（推薦，無棧溢出風險）

int peaches_iterative(int days) {
    int remaining = 1;  // 第 days 天剩餘
    for (int d = days - 1; d >= 1; --d) {
        remaining = 2 * (remaining + 1);
    }
    return remaining;
}

通用化：第 n 天剩 m 個

int peaches_general(int n, int m) {  // n天，第n天剩m個
    int rem = m;
    for (int d = n - 1; d >= 1; --d) rem = 2 * (rem + 1);
    return rem;
}

數學驗證

遞推公式：a_k = 2*a_{k+1} + 2，特徵方程 x = 2x + 2 解得通項：

a_k = 3 * 2^{10-k} - 2。驗證：k=10 → 3*1-2=1；k=1 → 3*512-2=1534。

擴展思考

• 若「吃一半再吃 k 個」，逆向公式：a_k = 2*(a_{k+1} + k)。
• 大數問題：天數多時結果指數增長，需用大整數庫（GMP）或高精度模擬。
• 面試變體：「猴子分桃」（航海經典問題），引入同餘方程/中國剩餘定理。