鱼C论坛

 找回密码
 立即注册
查看: 2293|回复: 1

[技术交流] 一道有关猴子拿桃的问题

[复制链接]
发表于 2014-3-26 14:03:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
这是“第023讲、024讲递归:这帮小兔崽子、汉诺塔|课后测试题及答案”里面的最后一道题。

  题目是:海滩上有一堆桃子,五只猴子来分。第一只猴子把这堆桃子凭据分为五份,多了一个,这只猴子把多的一个扔入海中,拿走了一份。第二只猴子把剩下的桃子又平均分成五份,又多了一个,它同样把多的一个扔入海中,拿走了一份,第三、第四、第五只猴子都是这样做的,问海滩上原来最少有多少个桃子?
  
  小甲鱼给的答案是用递归算出来的,但是我觉得有点问题,下面我说说我的理解。

  最后一只猴子拿的桃子数是不一定的。分成五份后:如果每份1个,那么一开始应该有6个桃子,但是6个不能被4整除,所以不满足“留下的其余4份”;如果每份2个,那么一开始应该有11个桃子,也不满足;如果每份3个,那么一开始应该有16个桃子,可以被4整除,那么说明前一只猴子拿的时候每份4个桃子,即有4*5+1=21个桃子,但是21个桃子又不能被4整除,说明每份3个不行。。。以此类推。。。

  我的方法比较直接:
用到的方法有:
  1. def number(n):
  2.         if not((5 * n + 1) % 4):
  3.                 return int(5 * n + 1)
  4.         else:
  5.                 return 0

  6. def four(n):
  7.         if not(n % 4):
  8.                 return int(n * 5 / 4 + 1)
  9.         else:
  10.                 return 0
复制代码
number方法:参数n为最后一只猴子所拿的桃子数;return的值是满足最后一只猴子拿n个桃子时,桃子的总数
four方法:用于计算根据现有桃子数,倒推满足题目条件时,上一只猴子留下的桃子数

首先,建立数组
  1. monkey1 = []
  2. monkey2 = []
  3. monkey3 = []
  4. monkey4 = []
  5. monkey5 = []
复制代码
分别表示第几个猴子拿桃子前,桃子的个数
  1. for i in range(1,1000):
  2.         if number(i):
  3.                 monkey5.append(number(i))
复制代码
枚举出第五个猴子拿桃子之前,桃子的数,放到monkey5列表中
  1. for i in monkey5:
  2.         if four(i):
  3.                 monkey4.append(four(i))

  4. for i in monkey4:
  5.         if four(i):
  6.                 monkey3.append(four(i))

  7. for i in monkey3:
  8.         if four(i):
  9.                 monkey2.append(four(i))

  10. for i in monkey2:
  11.         if four(i):
  12.                 monkey1.append(four(i))
复制代码
或者
  1. for i in monkey5:
  2.         if four(four(four(four(i)))) > 1:
  3.          monkey1.append(four(four(four(four(i)))))
复制代码
倒推出第一个猴子拿桃子前,桃子的数量,得出monkey1列表值为[3121, 6246, 9371]。

  如果取3121,顺序可得出第五个猴子拿桃子前,有1276个桃子,分五份,每份255个,剩于1个。

  而且,答案不唯一,如果说最后一个猴子拿桃子数最小的前提下,即一开始有3121个桃子。

  以上是我对这道题的理解,但是没有用到递推~~~望高手给出更好的解答方法~~~

评分

参与人数 1鱼币 +5 收起 理由
剑无痕 + 5 楼主学习很用心,赞一个

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-6-22 10:59:29 | 显示全部楼层
支持小甲鱼~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 07:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表