Nim游戏的定义:
有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。
假设俩人 双方且都采取最优策略
谁会获胜
对数据异或
结果为0 无论 怎么动 都会变不为0
如果不为0 总有办法 动一个 变为0
先手遇到
1.非0 的时候 赢
( 因为可以把它变成0)
2.0 的时候 必输
设三堆 每堆分别是: 3 4 5
三堆异或:011^100^101=010
所以 上述先手 必胜
设三堆 每堆分别是:5 10 15
0101^1010^1111=0000
所以 上述先手 必胜
数组对每个元素 连续累计异或
public static void main(String[] args) {
int[] data={3,4,5};
boolean ans =solve(data);
System.out.println(ans);
}
private static boolean solve(int[] data) {
int res = 0;
for (int i = 0; i < data.length; i++) {
res ^= data[i];
}
return res!=0;//不是0 win
}
而在竞赛中 不会想上述(nim游戏裸题)那么直白 所以看下面
Staircase Nim问题识别
阶梯Nim博弈
阶梯:像一个梯子 往一个方向移动 不能反向
Georgia and Bob

POJ1704
高森斗法
此坑待填
巴什问题(巴什博弈)
本文地址:https://dxoca.cn/Algorithm/179.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。