**問題**：猴子第一天摘若干桃子，當天吃掉一半，又多吃一個；第二天吃掉剩餘的一半，又多吃一個；... 第 10 天早上只剩 1 個桃子。求第一天共摘多少桃子？
設第 k 天早上剩 xₖ 個桃子，則第 k-1 天早上有：
xₖ₋₁ = (xₖ + 1) × 2
從第 10 天早上 x₁₀ = 1 反推至第 1 天。
#include <stdio.h>
int main() {
int day = 9; // 需要反推 9 次 (第10天→第1天)
int next_day = 1; // 第 10 天早上剩 1 個
int prev_day;
while (day > 0) {
prev_day = (next_day + 1) * 2; // 逆向公式
next_day = prev_day;
day--;
}
printf("第一天共摘 %d 個桃子\n", prev_day); // 1534
return 0;
}
第一天共摘 1534 個桃子
| 天數 (早上) | 剩餘桃子 | 當天吃掉 | 當天剩餘 |
|---|---|---|---|
| 第 1 天 | 1534 | 1534/2+1=768 | 766 |
| 第 2 天 | 766 | 384 | 382 |
| 第 3 天 | 382 | 192 | 190 |
| 第 4 天 | 190 | 96 | 94 |
| 第 5 天 | 94 | 48 | 46 |
| 第 6 天 | 46 | 24 | 22 |
| 第 7 天 | 22 | 12 | 10 |
| 第 8 天 | 10 | 6 | 4 |
| 第 9 天 | 4 | 3 | 1 |
| 第 10 天 | 1 | — | — |
通用化：任意天數、任意剩餘、任意吃法
數學閉式解
遞推關係：
xₖ₋₁ = 2xₖ + 2，特徵方程求解得：x₁ = (xₙ + 2) × 2ⁿ⁻¹ - 2 = (1 + 2) × 2⁹ - 2 = 3 × 512 - 2 = 1534 ✓總結
猴子吃桃問題本質是**線性遞推逆向求解**。關鍵洞察：正向模擬需要知道初始值（未知），逆向推導從已知終值出發，邏輯鏈條完整閉合。迭代版 O(n) 時間 O(1) 空間最優；遞歸版易理解但有棧溢出風險；閉式解 O(1) 最快。答案：**1534 個桃子**。
