Nim游戏:一共有N堆石子,编号从1到N,第i堆中有a[i]个石子。有A和B两个人。依次拿石子,每次可以从任意堆中拿任意数量的石子,至少拿一颗。至多拿着一堆剩下的所有石子。两个人轮流行动;取光所有石子的一方获胜(最后一次拿石子的那一人获胜)。假定A先手,且两人都会常用最优策略,A会不会获胜?
解题思路:
题目问的是会不会有一方稳赢的情况和策略。这是一个数学问题,有一个结论:就是将这N个数(剩余的数)转换为二进制然后进行异或操作得到一个结果S。S有为0和不为0两种情况;如果A下先手的时候S不为0,那么A就可以稳赢。
这是因为当S不为0时,可以通过拿一定的数量使得S为0;当S为0时,不管拿多少都会使得S不为0。所以只要一方掌握了S不为0的情况就可以使得S在0和非0之间不断变化,最终自己可以成为最后一次拿石子的人。
代码如下:
public class Nim游戏 {
public static void main(String[] args){
int[] arr = {3,4,5};
System.out.println(f(arr));
}
private static boolean f(int[] arr) {
int sum = 0;
for(int i=0; i<arr.length; i++){
sum = sum ^ arr[i];
}
if(sum!=0) return true;
return false;
}
}