寒光博客

[LanQiao]Nim 游戏
Nim游戏的定义: 有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,...
扫描右侧二维码阅读全文
21
2019/07

[LanQiao]Nim 游戏

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


Georgia and Bob AC
POJ1704

高森斗法

此坑待填

巴什问题(巴什博弈)

本文作者:Author:     文章标题:[LanQiao]Nim 游戏
本文地址:https://dxoca.cn/Algorithm/179.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 7th, 2019 at 10:41 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment