C 語言解決猴子吃桃問題：逆向遞推計算初始桃子數

C 語言解決猴子吃桃問題：逆向遞推計算初始桃子數

問題重述

猴子第一天摘若干桃子，吃掉一半再多吃一個。之後每天同樣操作。第 10 天早上只剩 1 個。求第一天共摘多少？

逆向遞推公式

設第 n 天早上剩 x_n 個，則第 n-1 天早上有 x_{n-1} = 2 * (x_n + 1) 個。

程式碼實作

#include <stdio.h>

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

執行結果

第一天共摘了 1534 個桃子

遞迴版本

int peaches_recursive(int day) {
    if (day == 10) return 1;
    return 2 * (peaches_recursive(day + 1) + 1);
}
// 呼叫 peaches_recursive(1) 同樣得到 1534

驗證正向模擬

int verify(int start) {
    for (int d = 1; d <= 9; ++d) {
        if (start % 2 != 0) return 0; // 必須為偶數才能吃一半
        start = start / 2 - 1;
    }
    return start == 1;
}
// verify(1534) 返回 1 (真)

逆向思維將複雜的正向模擬轉化為簡單的迴圈，是解決此類問題的關鍵技巧。