|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
这是“第023讲、024讲递归:这帮小兔崽子、汉诺塔|课后测试题及答案”里面的最后一道题。
题目是:海滩上有一堆桃子,五只猴子来分。第一只猴子把这堆桃子凭据分为五份,多了一个,这只猴子把多的一个扔入海中,拿走了一份。第二只猴子把剩下的桃子又平均分成五份,又多了一个,它同样把多的一个扔入海中,拿走了一份,第三、第四、第五只猴子都是这样做的,问海滩上原来最少有多少个桃子?
小甲鱼给的答案是用递归算出来的,但是我觉得有点问题,下面我说说我的理解。
最后一只猴子拿的桃子数是不一定的。分成五份后:如果每份1个,那么一开始应该有6个桃子,但是6个不能被4整除,所以不满足“留下的其余4份”;如果每份2个,那么一开始应该有11个桃子,也不满足;如果每份3个,那么一开始应该有16个桃子,可以被4整除,那么说明前一只猴子拿的时候每份4个桃子,即有4*5+1=21个桃子,但是21个桃子又不能被4整除,说明每份3个不行。。。以此类推。。。
我的方法比较直接:
用到的方法有:
- def number(n):
- if not((5 * n + 1) % 4):
- return int(5 * n + 1)
- else:
- return 0
- def four(n):
- if not(n % 4):
- return int(n * 5 / 4 + 1)
- else:
- return 0
复制代码 number方法:参数n为最后一只猴子所拿的桃子数;return的值是满足最后一只猴子拿n个桃子时,桃子的总数
four方法:用于计算根据现有桃子数,倒推满足题目条件时,上一只猴子留下的桃子数
首先,建立数组
- monkey1 = []
- monkey2 = []
- monkey3 = []
- monkey4 = []
- monkey5 = []
复制代码 分别表示第几个猴子拿桃子前,桃子的个数
- for i in range(1,1000):
- if number(i):
- monkey5.append(number(i))
复制代码 枚举出第五个猴子拿桃子之前,桃子的数,放到monkey5列表中
- for i in monkey5:
- if four(i):
- monkey4.append(four(i))
- for i in monkey4:
- if four(i):
- monkey3.append(four(i))
- for i in monkey3:
- if four(i):
- monkey2.append(four(i))
- for i in monkey2:
- if four(i):
- monkey1.append(four(i))
复制代码 或者
- for i in monkey5:
- if four(four(four(four(i)))) > 1:
- monkey1.append(four(four(four(four(i)))))
复制代码 倒推出第一个猴子拿桃子前,桃子的数量,得出monkey1列表值为[3121, 6246, 9371]。
如果取3121,顺序可得出第五个猴子拿桃子前,有1276个桃子,分五份,每份255个,剩于1个。
而且,答案不唯一,如果说最后一个猴子拿桃子数最小的前提下,即一开始有3121个桃子。
以上是我对这道题的理解,但是没有用到递推~~~望高手给出更好的解答方法~~~
|
评分
-
查看全部评分
|