猴子吃桃問題 C 語言實現：遞推逆向思維求首日桃數

題目重述

猴子第一天摘若干桃子，當即吃一半再多吃一個。第二天早上吃剩下的一半再多一個……每天早上同樣規則。到第 10 天早上想吃時，只剩 1 個桃子。求第一天共摘多少顆。

核心邏輯：逆向遞推

設第 n 天早上剩 x_n 個桃子。
第 n-1 天剩下多少？
根據規則：第 n 天早上吃了 (x_{n-1} / 2) + 1，剩下 x_n。
所以：x_{n-1} - (x_{n-1}/2 + 1) = x_n → x_{n-1}/2 - 1 = x_n → x_{n-1} = 2 * (x_n + 1)。

已知 x_10 = 1，逆推 9 次即得 x_1。

C 語言實現

#include 

int main() {
    int peaches = 1;  // 第10天早上剩1個
    for (int day = 9; day >= 1; day--) {
        peaches = 2 * (peaches + 1);
        printf("第 %d 天早上剩 %d 個\n", day, peaches);
    }
    printf("第一天共摘了 %d 個桃子\n", peaches);
    return 0;
}

執行結果

第 9 天早上剩 4 個
第 8 天早上剩 10 個
第 7 天早上剩 22 個
第 6 天早上剩 46 個
第 5 天早上剩 94 個
第 4 天早上剩 190 個
第 3 天早上剩 382 個
第 2 天早上剩 766 個
第 1 天早上剩 1534 個
第一天共摘了 1534 個桃子

驗證：正向模擬

int verify(int start) {
    int n = start;
    for (int day = 1; day <= 10; day++) {
        if (n % 2 != 0) return 0; // 必須能整除2
        n = n / 2 - 1; // 吃一半再多一個
        if (n < 0) return 0;
    }
    return n == 1;
}
// verify(1534) 回傳 1，驗證通過

變體擴展

• 若第 N 天剩 M 個，通用公式：x_1 = 2^N * (M + 1) - 2（可證明）。
• 若規則改為「吃一半再多 k 個」，遞推式：x_{n-1} = 2 * (x_n + k)。

結語

猴子吃桃問題本質是**線性遞推關係的逆向求解**。關鍵洞察：已知終態，利用逆運算逐步還原初態。C 語言只需一個迴圈、一個變數，幾行代碼即得解 1534。這類問題考驗的不是語法，而是**建立數學模型並轉化為迴圈不變量**的能力。