阿里云如何添加新网站,长沙做网站团队,如何去建设一个企业网站,网页设计学到了什么本节通过学习解决一个有趣的问题来加深对递归的理解. 问题描述:
有一个猴子摘了桃子吃,第一天吃一半多一个,第二天吃第一天剩余的一半多一个,第三天吃第二天剩余的一半多一个..以此类推,当第n天时,恰好只剩下一个桃子.求猴子一共摘了多少桃子. 思路解析:
解读题目,第n天的桃子…本节通过学习解决一个有趣的问题来加深对递归的理解. 问题描述:
有一个猴子摘了桃子吃,第一天吃一半多一个,第二天吃第一天剩余的一半多一个,第三天吃第二天剩余的一半多一个..以此类推,当第n天时,恰好只剩下一个桃子.求猴子一共摘了多少桃子. 思路解析:
解读题目,第n天的桃子数量与第n-1天的数量关系如下:peach(n-1)[peach(n)1]*2
因此,想知道第一天的桃子数量必然需要知道第二天的桃子数量,就必然要知道第三天的桃子数量,以此类推,第n天的桃子数量就为1,递推关系十分清晰.那么接下来确定递归终止条件,当n等于1时,相当于达到了第n天的情况,即只剩下一个桃子,返回1给上层主调函数. 代码如下:
class Solution(object):def monkey(self, n):# 基本情况如果只剩下1个桃子则返回1if n 1:return 1else:# 递归情况计算前一天的桃子数量然后加1因为猴子多吃了一个再乘以2因为猴子吃掉了剩下桃子的一半return (self.monkey(n-1) 1) * 2
