2019-05-23尼姆博弈

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);
    }
}