-- 作者： 彦清风 -- 发布时间： 2003/10/05 11:03am 乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下： 每一步应取走至少一枚石子； 每一步只能从某一堆中取走部分或全部石子； 如果谁无法按规则取子，谁就是输家。 解答 对于游戏A来说，任意的一个初始局面S=(a1, a2, …, an)，我们把这里的ai都看成是二进制数。令#S=a1异或   a2异或    …   异或 an。若#S≠0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。 这个异或运算我一直没有弄很明白，这里为什么要用这种逻辑运算? -- 作者： jqjiang -- 发布时间： 2003/10/06 09:28am 设 #S = a1 XOR a2  XOR … XOR an 若 #S=0, 则改变an中的任一个数，#S≠0; 若 #S≠0, 则可通过改变 an 中最大的数，使得 #S=0. 持续游戏过程，则 n 个数会减少到两个数的情况， 若两个数相等（即 #S=0），先取者必输（后取者采用与先取者一样的方法）； 若两个数不相等（即 #S≠0），先取者可取较大一堆的部分石子，使得两堆相等。 -- 作者： 彦清风 -- 发布时间： 2003/10/06 10:34am 异或运算怎么进行？1，1或者0，0，异或结果是0，那多个1，或者0，1相间怎么运算？比如1，0，1，1，0，0，1异或结果是什么？ -- 作者： jqjiang -- 发布时间： 2003/10/06 11:44am 两个算完后的结果再与第三个运算，依此类推。 按照从左到右的顺序运算。 -- 作者： jqjiang -- 发布时间： 2003/10/06 00:46pm 而且它还满足交换律、结合律什么的。 -- 作者： 彦清风 -- 发布时间： 2003/10/06 04:38pm [quote][b]下面引用由[u]jqjiang[/u]在 [i]2003/10/06 09:28am[/i] 发表的内容：[/b] 若 #S=0, 则改变an中的任一个数，#S≠0; 若 #S≠0, 则可通过改变 an 中最大的数，使得 #S=0. [/quote] 没明白，举个例子好么？ -- 作者： jqjiang -- 发布时间： 2003/10/06 04:49pm a1,a2,...,an 中，ai 是其中一个数，其他数通过异或运算后结果设为 aj， 若 ai XOR aj = 0，例如 111110 XOR 111110 = 0，ai 改变了，那肯定不是 111110了，所以异或结果就不为零了，也就是说，若两个数相等，则异或结果为零。 若两个数不相等，则这两个数异或结果不为零，例如 111 XOR 11 = 100， 那么我把其中比较大的数 111 改为 11（这一定能做到），这是两个数就相等了，异或结果就等于零了。 -- 作者： 彦清风 -- 发布时间： 2003/10/06 05:10pm 大概明白了，也就是说，先手必胜的前提是：N堆石头异或值为0以外任意数； 先手必胜的方法是：每拿走自己的石子后，使后手面对的石子异或值为0； 或者可以说，如果谁第一次面对异或值为0的石子数，那么后手就可以按照唯一的方法有必胜方案 对么？ -- 作者： jqjiang -- 发布时间： 2003/10/06 05:19pm 嗯，没错  ：） 后面就是如何使异或值为零了，一般是改变较大的数，如果最大的数成对出现，那就不用改变它们了，因为它们的异或结果就是零了。 如本例，先手只能取第三堆石子。 -- 作者： 彦清风 -- 发布时间： 2003/10/06 05:29pm 呵呵，谢谢江老师 -- 作者： 彦清风 -- 发布时间： 2003/10/06 06:40pm 对了，可是为什么要使用异或运算呢？ -- 作者： jqjiang -- 发布时间： 2003/10/07 07:40am 这种问题，估计很多都是后来才发现的，发现正好与某个运算性质相吻合  ：） 好像，国际上有一个专门研究非波那契数列的小组，就是研究哪些问题可以用非波那契数列来解释。