欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

博弈论 ----- Nim游戏

程序员文章站 2022-04-01 10:29:40
题目:结论:假设有三堆石子{3, 4, 5}, 每堆石子分别有3、4、5个石子把3、4、5分别转为二进制:011、100、101对011、100、101取异或(对位相同取0,相异取1),011^100^101 = 010若异或结果为0,那么只要改变任意一堆石子的任意数量则异或结果必定会变为非0最优策略:只要每堆石子数量的二进制数求异或结果不为0,则到自己回合的时候改变其中一堆石子数量让异或结果为0因为只要在我回合结束后把异或结果变为0,那么对手回合则无论他怎么操作,异或结果必定不...
题目:

博弈论 ----- Nim游戏

结论:
  1. 假设有三堆石子{3, 4, 5}, 每堆石子分别有3、4、5个石子
  2. 把3、4、5分别转为二进制:011、100、101
  3. 对011、100、101取异或(对位相同取0,相异取1),011^100^101 = 010
  4. 若异或结果为0,那么只要改变任意一堆石子的任意数量则异或结果必定会变为非0
最优策略:
  • 只要每堆石子数量的二进制数求异或结果不为0,则到自己回合的时候改变其中一堆石子数量让异或结果为0

因为只要在我回合结束后把异或结果变为0,那么对手回合则无论他怎么操作,异或结果必定不为0 —> 在他当前回合一定无法取完所有石子,最后一个回合我赢的局面一定是取完石子后每堆石子数量都为0 —> 异或结果为0。

解决本问题思路:
  • 如果双方都采取上面的最优策略
  • 根据上面的推导可知:只要先手的那个人最开始面对的那几堆石子二进制数异或为0,那么他一定输,反之他一定赢
  • 即只需要判断初始的石堆二进制异或是否为0 <=> 初始的石堆的几堆石子数量异或是否为0(因为一个数的十进制数异或为0 当且仅当 其二进制数异或为0)
   public static boolean solve(int[] A) {
        int res = 0;
        for (int value : A) {
            res ^= value;
        }
        return res != 0;//不为0就会赢
    }

本文地址:https://blog.csdn.net/k909397116/article/details/107898288

相关标签: 算法