package 数论;
public class Code_3Nim1 { // 尼姆博弈问题
/*nim问题为ICG 问题ICG问题的特征是：
1.两个人参与，交替走棋；
2.可能的走法在一个有限的集合里选取；
3.游戏局面无后效性，未来与过去无关；
4.如果某选手无法走动，则判负；
我们现在写的这个问题是一个
1*M的棋盘上有N个棋子，初始位置一定，两人轮流操作，
* 每次移动一枚棋子，要求只能向左移且至少移动一格，而且不
* 能到达或经过以前有棋子的格子，谁无法移动棋子就算输。
* 假设这个数组(棋盘)是给定的这道题的原题是poj1704原题是要
* 处理多行数据的这里我们就直接简化操作了数组中的数据也都是有序的
* */
public static void nim(int[] arr) {
int res = 0;
if((arr.length & 1) == 1) { // 奇数的情况
for(int i = 0; i < arr.length; i+=2) {
res ^= i == 0 ? (arr[0] - 1) : (arr[i] - arr[i - 1] - 1);
// 第一个元素和0为一组也就是第一个元素距离0的长度然后其余的两两分组
// i+2是要一次直接跳过两个值但是是奇数的时候第一个元素用了两回
}
}else {
for(int i = 1; i < arr.length; i+=2) {
res ^= (arr[i] - arr[i - 1] - 1);
}
}
if(res == 0) { // 等于0的话后手就会赢
System.out.println("后手会赢");
}else {
System.out.println("先手会赢");
}
}
public static void main(String[] args) {
int[] arr = {4, 5, 9};
nim(arr);
}
}
2019-05-23尼姆博弈
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
