100个python算法超详细讲解：猴子吃桃_猴子吃桃问题python

【100个python算法超详细讲解】@谷哥技术

1．问题描述
一个猴子摘了一些桃子，它第一天吃掉了其中的一半然后再多吃了
一个，第二天照此方法又吃掉了剩下桃子的一半加一个，以后每天如
此，直到第十天早上，猴子发现只剩下一个桃子了，问猴子第一天总共
摘了多少个桃子？
2．问题分析
假设Ai为第i天吃完后剩下的桃子的个数，A0表示第一天共摘下的
桃子，显然，本题要求的是A0。根据问题描述，前后相邻两天之间的桃
子数应存在如下关系：：
A(i+1)=Ai-(Ai/2+1)
此式可转换为：
Ai=2 A(i+1)+2=2(A(i+1)+1)
因此，有以下递推式子：
A0 = 2×(A1+1) A1：第1天吃完后剩下的桃子数
A1 = 2×(A2+1) A2：第2天吃完后剩下的桃子数
……
A8 = 2×(A9+1) A9：第9天吃完后剩下的桃子数
A9 = 1
由于第9天吃完后剩下的桃子数是已知的，因此根据上述递推式子
可以推出第8天的桃子总数；根据第8天吃完后剩下的桃子数又可以推出
第7天的桃子总数……重复进行下去，就可以推出第1天摘下的桃子总
数。推导过程如表9.1所示。
表9.1 推导过程表

3．算法设计
以上递推过程可分别用循环结构和递归函数实现。先使用递归函数
来实现。
将上述递推关系进行描述：假设第n天吃完后剩下的桃子数为
A(n)，第n+1天吃完后剩下的桃子数为A(n+1)，则存在递推关系A(n)=
(A(n+1)+1)*2。这种递推关系可以用递归函数实现。
4．确定程序框架
递归函数代码如下：

# 递推公式：A(n) = (A(n+1) + 1) * 2
def A(n):
if n >= 9:
return 1 # 递归出口
else:
return (2 * (A (n+1) + 1)) # 递推公式

 5．完整的程序
根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 猴子吃桃
# 递推公式：A(n) = (A(n+1) + 1) * 2
def A(n):
if n >= 9:
return 1 # 递归出口
else:
return (2 * (A(n+1) + 1)) # 递推公式
if __name__ == "__main__":
print("猴子第一天总共摘了 %d 个桃子" %A(0))

6．运行结果
在PyCharm下运行程序，结果如图9.1所示。

7．问题拓展
该问题还可以使用循环结构求解，代码如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 猴子吃桃
if __name__ == "__main__":
day = 9
x2 = 1
while day > 0:
x1 = (x2 + 1) * 2 # 第1天的桃子数是第2天桃子数加1后的2倍
x2 = x1
day -= 1
print("猴子第一天总共摘了 %d 个桃子" %x1)