1.需求描述以及分析
需求描述:
猴子第一天摘了若干个桃子,第一天吃了若干个桃子中的一半,觉得不过瘾,又多吃了一个。
第二天早上又将第一天剩下的桃子吃了一半,并且也觉得不过瘾,又多吃了一个。
第三天早上有讲第二天剩下的桃子吃了一半,并且也觉得不过瘾,又多吃了一个。
以后每天早上都会吃前一天剩下的一半桃子,且会多吃一个。
到第10天的时候发现只剩下一个桃子了,求猴子第一天一共摘了多少桃子?
需求分析:
猴子每天都会吃掉前一天所剩桃子数的一半,可以得到这样一个推理过程:
- 第一天吃掉了一半的桃子,还剩下一半,又多吃了一个,第二天吃了第一天所剩桃子数的一半,并且也多吃了一个。
- 那么就得到:第1天的桃子个数是第2天所吃的桃子个数加1后的2倍,第2天的桃子个数是第3天所吃的桃子个数加1后的2倍,依次类推,直到只剩下1个桃子。第n天的桃子数就是第n+1天所吃的桃子个数加1后的2倍。
计算猴子每天吃的桃子个数时,需要从第10天开始计算,因为明确知道第10天只有1个桃子,然后再算第9天的桃子个数,第9天的桃子树等于第10天的桃子树加1乘2的个数,第9天的桃子树就是(1+1)*2=4个,第9天就是4个桃子,按照这个思路一直计算第8天、第7天,一直到第一天为止,将每天的桃子数累加起来,就是第一天摘了多少个桃子。
2.递推方式实该该程序
首先使用递推的方式来实现这个程序,设计思路如下:
-
已知第1天的桃子个数是第2天所吃的桃子个数加1后的2倍,第2天的桃子个数是第3天所吃的桃子个数加1后的2倍。
-
我们可以将每天的桃子数放在一个列表mp
里,在列表中填充11个None值,只有10天,填充11个元素的目的是,索引为0的元素不会被处理,因此要填充11个元素,已知第10天的桃子数为1,那么就将索引为10的元素,初始化成1:mp[10]=1
。
-
可以设n
天的桃子数为mp[n]
,递推表达式就是:mp[n]=(mp[n+1]+1)*2
,且mp[10]=1
。
-
确定好表达式之后,我们就可以写一个for循环,已知第10天为1个桃子了,那么就从第9天开始循环,已知递推循环到第1天,每循环一次,就根据递推表达式,计算出这天的桃子树,递推表达式会将后一天的桃子数加1并且乘以2,因此不用手动累加每天的桃子个数,到了第一天时,一定是准确的桃子个数。
例如第一次循环时第9天,根据递推表达式mp[9] = (mp[9+1] + 1) *2
= mp[9] = (mp[10] + 1) = 2 * 2 = 4
,第9天的桃子数就是4个,以此类推。
def monkey_peach():
mp = [None] * 11
mp[10] = 1
for n in range(9, 0, -1):
mp[n] = (mp[n + 1] + 1) * 2
return mp[1]
print('猴子第一天一共摘了{}个桃子'.format(monkey_peach()))
3.递归方式实现该程序
使用递推方式,每次都会用当前的天+1之后得到后一天的桃子树,然后加1乘2得到当天的桃子树,这个递推关系相当于在一个函数的内部又调用了一遍函数,所以我们可以使用递归函数来实现这个例子。
递归的结束条件就是当循环到第10天时,返回1。
代码如下:
def monkey_peach(day):
if day == 10:
return 1
else:
return (monkey_peach(day + 1) + 1) * 2
print('猴子第一天一共摘了{}个桃子'.format(monkey_peach(1)))
递归的循环过程是:将传递的参数带入到循环体内,开始进行递推,直到满足循环结束条件时,递推结束,然后开始回归,将最后一次递推执行的结果,向前面递推的进行运算,直到第一个递推结果处为止,最后返回对应的结果。
猴子吃桃的递归遍历过程:
1)首先开始递推
递归函数:monkey_peach(day + 1) + 1)
- 调用函数时传入day的实参为1,即day=1,视作为day1。
- 开始第一次递推:day+1=1+1=2,即day1+1,视作为day2。
- 开始第二次递推:day+1=2+1=3,即day2+1,视作为day3。
- 开始第三次递推:day+1=3+1=4,即day3+1,视作为day4。
- 开始第四次递推:day+1=4+1=5,即day4+1,视作为day5。
- 开始第五次递推:day+1=5+1=6,即day5+1,视作为day6。
- 开始第六次递推:day+1=6+1=7,即day6+1,视作为day7。
- 开始第七次递推:day+1=7+1=8,即day7+1,视作为day8。
- 开始第八次递推:day+1=8+1=9,即day8+1,视作为day9。
- 开始第九次递推:day+1=9+1=10,10满足递归结束条件:
if day == 10
,此时递推结束,第九次递推拿到return返回值1。
2)然后带着返回值开始回归遍历计算
-
带着第九次递推的返回值去回归。
-
回归到第八次递推,即day9,此时day9的结果就是((day9+1)+1)*2
,day9+1为day10,day10的值1,然后套入公式中,即day9=(1+1)*2=4
。
-
回归到第七次递推,即day8,此时day8的结果就是((day8+1)+1)*2
,day8+1为day9,day9的值为4,然后套入公式中,即day8=(4+1)*2=10
-
回归到第六次递归,即day7,此时day7的结果就是((day7+1)+1)*2
,day7+1为day8,day8的值为10,然后套入公式中,即day7=(10+1)*2=22
-
回归到第五次递推,即day6,此时day6的结果就是((day6+1)+1)*2
,day6+1为day7,day7的值22,然后套入公式中,即day6=(22+1)*2=46
。
-
回归到第四次递推,即day5,此时day5的结果就是((day5+1)+1)*2
,day5+1为day6,day6的值为46,然后套入公式中,即day5=(46+1)*2=94
-
回归到第三次递归,即day4,此时day4的结果就是((day4+1)+1)*2
,day4+1为day5,day5的值为94,然后套入公式中,即day4=(94+1)*2=190
-
回归到第二次递推,即day3,此时day3的结果就是((day3+1)+1)*2
,day3+1为day4,day4的值190,然后套入公式中,即day3=(190+1)*2=382
。
-
回归到第一次递推,即day2,此时day2的结果就是((day2+1)+1)*2
,day2+1为day3,day3的值为382,然后套入公式中,即day2=(382+1)*2=766
-
到此递推和回归就结束了,带着返回值766与调用函数传递的day1进行运算,day1的结果就是((day1+1)+1)*2
,day1+1位day2,也就是递归函数的运算结果766,套入公式中即day1=(766+1)*2=1534
1534就是函数的返回值。