题目
分析
我们先用最直接的倒推法来解题。
第n天的桃子数量\(a_n\)是这么得来的：\(a_n=\frac{a_{n-1}}{2}-1\)，所以\(a_{n-1}=(a_n+1)*2\)。简单列表如下：
| 天数 | 剩余桃子数 \(a_i\) | 计算步骤 | 上一天桃子数 \(a_{i-1}\) |
|---|---|---|---|
| 4 | \(1\) | — | \(a_3 = 2\times(1+1) = 4\) |
| 3 | \(4\) | \(a_3 = 2\times(a_4+1) = 2\times(1+1) = 4\) | \(a_2 = 2\times(4+1) = 10\) |
| 2 | \(10\) | \(a_2 = 2\times(a_3+1) = 2\times(4+1) = 10\) | \(a_1 = 2\times(10+1) = 22\) |
| 1 | \(22\) | \(a_1 = 2\times(a_2+1) = 2\times(10+1) = 22\) | — |
所以，在倒推法中，正确的递推公式为：\(a_{i-1} = 2\times\bigl(a_i + 1\bigr)\)
答案
思考
本题还可以用顺推的方式解决：
int calculatePeaches(int day, int n)
{
if (day == n)
{
return 1; // 第 n 天早上剩 1 个
}
// 第 day+1 天开始时的桃子数
int nextDay = calculatePeaches(day + 1, n);
// 第 day 天开始时的桃子数 = (第 day+1 天的数量 + 1) × 2
return (nextDay + 1) * 2;
}