博弈论 ----- 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,那么对手回合则无论他怎么操作,异或结果必定不...
题目:
结论:
- 假设有三堆石子{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,那么对手回合则无论他怎么操作,异或结果必定不为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
下一篇: js统一全局变量