最新消息:点击查看大S的省钱秘笈

二道数学题阐释递归思想

编程相关 Slyar 76浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

有同学问什么是递归,我懒得说,拿两道数学题来阐释好了。。。

1、两个人从1开始,轮流报数,每个人都只能报接下来的一个数或两个数。比如第一个人可以报1,也可以报1、2;如果第一个人报1、2,第二个人就可以报3或者3、4;然后第一个人又报......这样报下去,最先报到30的人获胜,求必胜策略。

解答:最先报到30的人获胜,那么先报到27的人就一定可以获胜,同理先报到24的人就一定能获胜……递归下去。21,18,15……,最终得到的结论就是先报到3的人必胜。也就是说,后报者必胜。不管先报者报多少,后报者始终能报到3的倍数,必胜。

如果先报到30的人输,同理,先报到29的人就赢了,然后同样递归,26,23,20……

2、有10枚硬币,每人轮流取硬币,可以拿一枚、两枚或四枚,取到最后一枚硬币者胜。求必胜策略。

利用递归思想解答:

硬币总数是一枚,先取者赢;
硬币总数是两枚,先取者赢;
硬币总数是三枚,先取者输;
硬币总数是四枚,先取者赢;
硬币总数是五枚,先取者赢(自己取两枚,对方面临三枚的情形,必输);
硬币总数是六枚,先取者输(不管取多少,对方面临的情形都是必胜的);
硬币总数是七枚,先取者赢(自己取一枚,对方面临六枚的情形,必输);
硬币总数是八枚,先取者赢(自己取两枚,对方面临六枚的情形,必输);
硬币总数是九枚,先取者输(不管取多少,对方面临的情形都是必胜的);
硬币总数是十枚,先取者赢(自己取一枚,对方面临九枚的情形,必输)。

转载请注明:Slyar Home » 二道数学题阐释递归思想

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (4)

  1. 经典
    卍俟-征封4年前 (2013-04-14)回复
  2. 硬币总数是九枚,先取者---输---
    码农4年前 (2012-12-28)回复
  3. 题目好绕人啊。
    打工皇帝8年前 (2008-11-13)回复
  4. 不错不错
    Mr.crazy8年前 (2008-11-13)回复