看你的策略是什么？你能赢吗？

wwd_meng

原帖由 superacid 于 2009-10-7 13:25 发表


如何保持？

呵呵
计算错误，因为不能拿3个
所以这个问题很麻烦，所以我是解不了了

铯_猪哥恐鸣

1、很容易证明7个以下的情况是：
a[0]=true
a[1]=false
a[2]=true
a[3]=true
a[4]=false
a[5]=true
a[6]=true
a[7]=false
（true表示待拿者胜利。例：a[0]=true，就是说还有0个球的时候下一位取球的胜利，，这是根据规则显然的）

对于7个以上的情况，若A取1则B取2（共取3），A取2则B取4，若A取4则B取2（共取6），总之每轮取完之后结果仍然为3N+1的数字。然后容易发现，a[7]=false,a[4]=false,a[1]=false。所以先取的人必败

lulijie

楼上完全正确，A取2时，B可取4，也可取1。
对于这类题目，用倒推的方法基本上都能解出。
－－－－－－－－－－－－－－－－－－－
若把题目推广到几堆球，难度就大了一些。
－－－－－－－－－
n堆球，每堆的球数都是100个，每次只能从一堆中拿球，每次拿球的个数是1、2、4个球，谁拿走最后一个球，算谁输。
那么先行方是赢还是输？
－－－－－－－－－－－－－－

123wyx

原帖由 lulijie 于 2009-10-7 19:26 发表
若把题目推广到几堆球，难度就大了一些。
－－－－－－－－－
n堆球，每堆的球数都是100个，每次只能从一堆中拿球，每次拿球的个数是1、2、4个球，谁拿走最后一个球，算谁输。
那么先行方是赢还是输？

这问题就复杂了，感觉跟二进制有点关系。

phileas

首先，计算nim函数，nim(x)= x mod 3。
如果拿到最后一个算赢，那么n堆球就是把上述函数用异或一下即可，结果为0则先行必输，否则先行必胜。
如果拿到最后一个算输，基本上仍然是上述结论。但是需要另外计算一个状态集：
0. 这个状态集是一层一层计算的，每层是0状态和非0状态交替；
1. 这个状态集的起始状态是(1)；
2. 附加一条显然的规则：任何一个状态，加上(1,1)是等价状态。
计算方法大概是这样的：
从非0状态层计算0状态层：把每个非0状态的前驱状态计算一下，如果其值是0，则放入0状态层。
从0状态层计算非0状态层：把每个0状态的前驱状态计算一下，这个状态要满足两个要求：
a. 能得到的0状态必须已经在状态集中。
b. 不能得到状态集中的任何一个非0状态。

对于拿到最后一个算输的问题，结论是：如果某状态在以上状态集中，那么为0则先行必胜，否则先行必输；如果某状态不在以上状态集中，那么为0则先行必输，否则先行必胜。
==========================================================
时间关系，写得不是很清楚，抱歉。

[ 本帖最后由 phileas 于 2009-10-7 21:43 编辑 ]

flwb

先手必输,B的原则是:A取1,B取2,A取2 B取1或4,A取4,B取2,保证以3或3的倍数递减至1。

[ 本帖最后由 flwb 于 2009-10-8 23:54 编辑 ]