博客

题目：有3堆硬币，分别是3,4,5

二人轮流取硬币。

每人每次只能从某一堆上取任意数量。

不能弃权。

取到最后一枚硬币的为赢家。

求先取硬币一方有无必胜的招法。

思路：

使用尼姆堆的模2加(异或)解法

意思是：设先手的人是a，后手的人是b。将a准备抓所以堆的数量进行异或，结果为0的话，那么a必输（既无论如何抓，b都有办法让a输）；如果不为0，那就a抓堆后让b的所有堆的数量异或为0，a便无论如何都有办法赢b

举例来说：一共有4个堆：2，5，12，14

对应的二进制数为：

0010

0101

1100

1110

————

0101

现在对每个堆的数目进行异或后结果不为0，那么该怎么抓让对方剩下的堆的数目异或为0呢？

由异或运算性质, 0异或任何数,其结果=任何数, 1异或任何数,其结果=把该数取反。可知，0101去异或其中任何一堆得到这一堆应该剩下的数，那其余的推全部异或起来为0（数学性质问题，自行验证）。

public class Nim {
	static void f(int[] a) {
		int sum = 0;
		for(int i=0; i<a.length; i++) {
			sum ^= a[i];
		}
		if(sum==0) {
			System.out.println("必输");
			return;
		}
		for(int i=0;i<a.length; i++) {
			int x = sum ^ a[i]; //x为i堆应剩下的数量
			if(x<a[i]) {
				System.out.println("让" + a[i] +"剩下"+ x + "可以赢"); //让3剩下1可以赢
			}
		}
	}
	
	public static void main(String[] args) {
		int [] a = {3,4,5};
		f(a);
	}
}