HDU 1003 蟠桃記：逆向推導解決猴子分桃經典遞迴問題

HDU 1003 蟠桃記：逆向推導解決猴子分桃經典遞迴問題

《西遊記》中孫悟空偷吃蟠桃的故事廣為人知，但鮮少有人注意到其中隱藏著一個經典的數學遞迴問題：已知第 n 天早上只剩 1 個桃子，且每天猴子吃掉「剩餘桃子的一半再加 1 個」，求第一天原本有多少桃子？這正是 HDU 1003 / ZOJ 1003 「蟠桃記」的核心邏輯。

問題數學模型

設第 k 天早上剩餘桃子數為 a_k，則遞迴關係為：

a_k = (a_k+1 + 1) × 2

邊界條件：a_n = 1（第 n 天早上剩 1 個）。要求 a₁。

這是一個典型的「逆向遞迴」：從已知的終態反推初態。由於 n < 30，結果在 32 位整數範圍內（最大 n=29 時約 1.6×10⁹），int 或 long 足夠。

演算法實作

#include <stdio.h>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int peaches = 1;           // 第 n 天早上剩 1 個
        for (int day = 1; day < n; day++) {
            peaches = (peaches + 1) * 2;  // 逆向推導前一天數量
        }
        printf("%d\n", peaches);
    }
    return 0;
}

關鍵點解析

• 循環次數：只需迴圈 n-1 次（從第 n 天倒推到第 1 天）
• 公式推導：若第 k+1 天剩 x，則第 k 天原有 (x+1)×2。驗證：吃掉一半加一即 (x+1)×2 / 2 + 1 = x+2，剩下 (x+1)×2 - (x+2) = x ✓
• 多測試案例：使用 while(scanf(...)!=EOF) 處理輸入

範例驗證

延伸思考

此問題本質是線性遞迴數列 a_k = 2a_k+1 + 2，通項公式為 a₁ = 2ⁿ - 2。若 n 較大（如 10⁹），需用矩陣快速冪或模算術優化；但本題 n<30 直接迴圈即可。同類經典問題還有「猴子分椰子」（UVa 10078），涉及模逆元與中國剩餘定理，更具挑戰性。