编程之美:NIM(1)一排石头的游戏

  • Post author:
  • Post category:其他



题目大意:

N块石头排成一行,两个玩家依次取石头,每个玩家可以取其中任意一块或者相邻的两块,最后能将剩下的石头一次取光的玩家获胜。


分析:

1、N=1、N=2,必胜

2、N=3,先取者取中间1块石头,左右还剩下各1块石头,无论第二个人怎么取,己方必胜

3、N=4,先取者取中间2块石头,还是左右各剩一块,己方必胜

4、N>4时,先取者只要取中间的元素,N为奇数取中间一个,偶数取中间两个,将石头分为两部分,然后无论第二个人怎么取,先取者只要在另一部分的同样位置取走同样多的石头,则最后先取者必胜

所以对任意N,先取者必胜。


拓展:

1、判定最后取光石头的人输


分析:

1、N=1,必输

2、N=2,只要取走一块就转化成了1,必胜

3、N=3,只要取走任意相邻的两个就转化成了1,必胜

4、N=4,无论怎么取都是必输

5、N=5,因为只要取走最左边的1个或者最右边的1个就转化成了4,为必胜态

6、N=6,因为只要取走前面2块石头就转化成了4,为必胜态

。。。。。。

归纳总结如下:对于任意的N,若取走某1个或2个石头后,石头可能被分为两部分也可能还是一部分,若剩下一部分若为必输态,则此状态N必胜;

若剩下两部分:

1)若剩下的两部门一部分是必胜态,一部分是必输态,如果第二个人先从必输态中取,则无论怎么取最后的石头总会落到他的手中,然后己方还剩下必胜态,先取必胜;

如果第二个人先从必胜态中取,己方和对方都是想让对方先取必输态的石头,即都想在必胜态中败,所以无法考虑此类情况

若两部分都是必胜态,第二个人总会有必胜态的优先权,所以总能保证己方败

若两部分都是必败态,己方和对方都想要在必败态下败下阵来,所以无法考虑此类情况

可以看出,找寻必胜态是行不通的,换换找寻必败态试试:

要想保证己方必败,需要满足以下条件:

1、无论己方怎么取,剩下的石头(1或两部分)都构成必胜态

这个是不可能的,因为我可以直接取第二块石头,将第一块石头空下来,第一块石头为必败态,所以也无法考虑这种情况

所以,综上所述,当N>6时,胜负难定



版权声明:本文为starcuan原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。