C語言解決猴子吃桃問題：逆向推導經典遞迴

問題描述

猴子第一天摘若干桃子，當天吃掉一半又多吃一個；之後每天同樣吃法。到第 10 天早上只剩 1 個。求第一天共摘多少？

逆向思維

設第 n 天早上剩 x 個，則第 n-1 天早上有 2*(x+1) 個。從第 10 天倒推至第 1 天。

完整程式碼

#include 

int main() {
    int sum = 1;          // 第 10 天早上剩 1 個
    for (int i = 0; i < 9; i++) {   // 往前推 9 天
        sum = 2 * sum + 2;
    }
    printf("%d\n", sum);
    return 0;
}

逐日推導表

執行結果

1534

第一天共摘 1534 個桃子。