猴子摘桃问题 #

1. 猴子摘桃问题介绍
2. 猴子摘桃问题分析
3. 猴子摘桃问题的实现

收获 #

学完本节内容，可以更深刻了解递推思想的使用。

猴子摘桃问题介绍 #

问题描述：
猴子第一天摘了若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃一个。
以后每天早上都吃前一天的一半零一个。到第十天的时候再想多吃，见只剩下一个桃子了。求第一天一共摘了多少桃子？

猴子摘桃问题分析 #

可以用逆推来解决这个问题。第10天时，猴子只剩下1个桃子，逆推可得，第9天桃子的数量为2（1+1）=4个，同理得第8天桃子的数量为2（4+1）=10个，…以此类推。
该过程可以简单用下图表示：

猴子摘桃问题的实现 #

python实现代码如下：

#逆推法
total=1 #最后一天剩余的桃子
for i in range(9):
    total+=1
    total*=2
print(total)

小结 #

结合猴子摘桃问题的应用，进一步理解递推算法的思想
掌握猴子摘桃问题的代码实现

习题 #

1. 习题1：画出猴子摘桃问题的流程图
2. 习题2：假设猴子在之前的问题中吸取了教训，痛改前非，决定每天吃掉比一半的桃子少一个的数量，在第10天的时候，只剩下3个桃子，求问这次猴子在第一天摘了多少桃子？

–>