求取火柴一类问题的解的算法例1：2.取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取

Question

求【取火柴】一类问题的解的算法
例1：2. 取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1 根或
2 根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，
先取者没有必胜策略记为0。当N 分别为100，200，300，400，500 时，先取者有无必
胜策略的标记顺序为（回答应为一个由0 和/或1 组成的字符串）。
例2：2.(取石子游戏)现有5堆石子,石子数依次为3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自一堆,不能不取),取最后一颗石子的一方获胜.甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误,都能获胜) 如果有,甲第一步应该在哪一堆里取多少 请写出你的结果
{不是求解 是求算法}

Answer 1

第一题比较简单，可以推广到有n根火柴每人可取1到m根
若n % ( m + 1 ) == 1则先取必败，否则必胜，这个比较好证明
很简单可以证明当火柴数为1时先取必败，然后火柴数为m + 1时，无论先取的人怎样取，假定取x个，那么第二个人取m - x个，即可只剩一个留给对方。这样一直下来，如果用D( x ) = 1表示当留有x个火柴时先取必败，那么
D( 1 ) = 1
D( m + 2 ) = 1
D( 2m + 3 ) = 1
........
在这道题的情况就是
D( 1 ) = 1
D( 4 ) = 1
D( 7 ) = 1
.........
所以刚开始这些情况是必败的，换言之，如果刚开始不是这种情况，则先取的人可以取n % ( m + 1 ) - 1个（注意n % ( m + 1 ) == 0的情况，这是应该是取m个），就可以转化成上述令对手必败的情况。
第二题比较麻烦
我这里正好有一个别人写的
只有一堆时，无论有多少，先取者都可以一次性全部取走，所以必胜。
(1,1)时，显然先取者必败。
(1,2)时，先取者必胜，他可以在2那一堆中取1个，于是变成(1,1)，但这成为上一种情况了，于是接下来取的人必败，亦即先取者必胜。
(1,3)时，先取者必胜。他可以在3那一堆中取2个，于是变成(1,1)。
(2,2)时，先取者必败。他在任何一堆中取1个，对方随即在另一堆中取1个，即变成(1,1)；如果他取走一堆中的全部石子，对方即取走另一堆中的全部石子。
(2,3)时，先取者必胜。他可以在3那一堆中取1个，于是变成(2,2)。
(3,3)时，先取者必败。他取走任一堆中的1,2或3个，就变成了以上讨论过的情形。
(1,1,1)时，先取者必胜。他取走任一堆，就变成了(1,1)。
(1,1,2)时，先取者必胜。他取走2那一堆，就变成了(1,1)。
(1,1,3)时，先取者必胜。他取走3那一堆，就变成了(1,1)。
(1,2,2)时，先取者必胜。他取走1那一堆，就变成了(2,2)。
(1,2,3)时，先取者必败。分析如下：
他先取1那一堆，则变为(2,3)，由上面的分析，对手必胜。
他从2那一堆中取1个，就变成了(1,1,3)，对手可以将3那一堆全部取走，变成了(1,1)，于是必胜。
他将2那一堆全部取走，就变成了(1,3)，对手必胜。
他从3那一堆中取1个，就变成了(1,2,2)，对手必胜。
他从3那一堆中取2个，就变成了(1,2,1)，对手必胜。
他将3那一堆全部取走，就变成了(1,2)，对手必胜。
这些胜负有什么规律呢？我们可以将每堆的数转换成二进制，然后看每一位上所有堆里的1的个数总和：
必胜情况：(n) (1,2)(1,3)(2,3) (1,1,1)(1,1,2)(1,2,2)
必败情况： (1,1)(2,2)(3,3) (1,2,3)
化为二进制：
必胜情况：
(n)：……（反正每位只要有1肯定只有1个）
(1,2)：1,10
列成竖式：
01
10
个位上只有1个1，“十位”（因为是二进制所以叫十位不妥，这里为了方便说明暂且使用，下同）上也只有1个1。
(1,3)：1,11
列成竖式：
01
11
个位上有2个1（1的1个，3的1个），十位上有1个1。
(2,3)：10,11
个位上有1个1，十位上有2个1。
(1,1,1)：1,1,1
个位上有3个1。
(1,1,2)：1,1,10
个位上有2个1，十位上有1个1。
(1,1,3)：1,1,11
个位上有3个1，十位上有1个1。
(1,2,2)：1,10,10
个位上有1个1，十位上有2个1。
必败情况：
(1,1)：1,1
个位上有2个1。
(2,2)：10,10
十位上有2个1。
(3,3)：11,11
个位上有2个1，十位上也有2个1。
(1,2,3)：1,10,11
个位上有2个1，十位上也有2个1。
下面分析一下这些情况。
先看必败情形。容易发现，所有的必败情形，都是所有的数位上都有偶数个1。
下看必胜情形。我们发现，出现了两种情况：
1.只有1位上有奇数个1，如(1,3)(2,3)(1,1,1)(1,1,2)(1,2,2)。而先取者取走该位上的1，所有的位上就都变成了偶数个1，而这时后取者变成了先取者。
2.有若干位上都是奇数个1，如(n)(1,2)(1,1,3)。先取者取（不一定取走哪位）后，所有的位上也都变成了偶数个1。后取者变成了先取者。
以上两种情况，都是将后取者逼至必败情况从而取胜。
由以上分析我们可以得到结论：将所有的堆的石子数化为二进制后，如果所有数位上的1的个数都是偶数，那么先取者必败；如果有些位上的1的个数是奇数，先取者能够将所有数位上的1的个数都变为偶数的话，那么先取者必胜。
好，下面来分析我们的题目。
3,5,7,19,50化为二进制是：
000011
000101
000111
010011
110010
可见，只有最高位的1是奇数个，其他位上都是偶数个。
所以只需要将最高位的1取走即可必胜。
二进制的100000就是10进制的32，所以要将50个石子的那堆取32个，取掉就变成偶数个数目。于是先取者必胜。以后无论对方怎么取，始终保证每一位上的1的个数是偶数即可（一种简单的方法是，他在一堆中取几个，你在另一堆中也取几个就可以）。