【深基7.习8】猴子吃桃

题意

猴子每天吃掉当前桃子的一半再多吃一个。第 n 天早上只剩 1 个桃子，求最开始有多少个桃子。

思路

正向吃桃不方便，因为不知道初始值。反过来想：如果某天早上剩 peaches 个，那么前一天早上吃之前应有：

text

1(peaches + 1) * 2

从第 n 天的 1 个桃子开始，倒推 n-1 次即可。

这题是倒推递推练习，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：单个整数输入用 int(input())。
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：Python 整数适合直接做递推乘法。
for _ in range(n - 1) 表示重复执行固定次数，不关心循环变量。

代码

python

1
2
3
4
5
6
7n = int(input())
peaches = 1

for _ in range(n - 1):
    peaches = (peaches + 1) * 2

print(peaches)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

int main() {
    int n;
    cin >> n;
    int peaches = 1; // 第 n 天早上剩 1 个
    // 倒推 n-1 次，回到第 1 天
    for (int i = 1; i < n; i++) {
        peaches = (peaches + 1) * 2;
    }
    cout << peaches;
    return 0;
}

复杂度

循环 n-1 次，时间复杂度是 $O(n)$ ，空间复杂度是 $O(1)$ 。

总结

遇到“最后剩多少，求最开始多少”的题，常常从末尾倒推更自然。

【深基7.习8】猴子吃桃

目录

题意

思路

Python 知识

代码

复杂度

总结