OJ 递归反推 桃子问题

题目：桃子问题（反推初始桃子数）

链接： https://oj.haizeix.com/problem/184##

路飞买了一堆桃子不知道个数。第 1 天吃了剩下的一半又多吃 1 个；以后每天都吃剩下的一半又多吃 1 个。到第 n 天只剩下 1 个桃子。求最开始有多少个桃子。

输入

• 一个整数 n（2 ≤ n ≤ 30）

输出

• 初始桃子数（正整数）

样例

• 输入：2 → 输出：4
• 输入：3 → 输出：10

思路（反推法）

设第 k 天开始时的桃子数为 a_k，题意是第 n 天开始时 a_n = 1。根据每天的吃法：

• 第 k 天吃掉一半并多吃 1 个，剩下的是下一天开始的数量 a_{k+1}，关系为： a_{k+1} = a_k - (a_k/2 + 1) = a_k/2 - 1

我们要从 a_n = 1 反推 a_{n-1}, a_{n-2}, ..., a_1。把等式变形：

• a_{k+1} = a_k/2 - 1 ⇒ a_k/2 = a_{k+1} + 1 ⇒ a_k = 2 * (a_{k+1} + 1)

因此，从后往前递推：

• 初始：a_n = 1
• 对 i 从 n-1 到 1：a_i = 2 * (a_{i+1} + 1)

最终输出 a_1。

推导例子

• n = 2：
  • a_2 = 1
  • a_1 = 2 * (1 + 1) = 4
• n = 3：
  • a_3 = 1
  • a_2 = 2 * (1 + 1) = 4
  • a_1 = 2 * (4 + 1) = 10

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

C++ 实现（示例代码）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    long long a = 1; // a_n = 1
    for (int i = n - 1; i >= 1; --i) {
        a = 2 * (a + 1);
    }
    cout << a << "\n";
    return 0;
}

Python 实现（示例代码）

n = int(input().strip())
a = 1  # a_n = 1
for _ in range(n - 1):
    a = 2 * (a + 1)
print(a)

你可以将上面的任意一段代码复制到对应语言的编译器/解释器中运行。若需要 Java、Pascal 或其他语言的实现，我可以继续补充。