【算法】经典博弈论问题②——尼姆博弈与反尼姆博弈 python

前置知识

经典博弈论问题——巴什博弈
异或运算的概念
还不了解的小伙伴可以点击进去详细讲解

尼姆博弈(Nim Game)

【模板】Nim 游戏

题目描述

甲，乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

输入格式

本题有多组测试数据。

第一行一个整数 $T$ （$T\le 10$），表示有 $T$ 组数据

接下来每两行是一组数据，第一行一个整数 $n$，表示有 $n$ 堆石子，$n\le 10^4$。

第二行有 $n$ 个数，表示每一堆石子的数量.

输出格式

共 $T$ 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。

样例输入

2
2
1 1
2
1 0

样例输出

No
Yes

思路分析：

对于尼姆博弈来说，关键在于计算所有堆中石子数目的二进制异或和（XOR）。
如果所有堆的石子数目异或和不为0，则先手玩家处于N态；
如果异或和为0，则先手玩家处于P态。
即当 n 堆石子的数量异或和等于 0 时，先手必败，否则先手必胜

为什么呢？用实际数字模拟来举个例子

通过这两个例子，我们可以直观地理解尼姆博弈中异或和的作用以及它对结果的影响。

附上题解code：

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    xor = 0
    for i in range(n):
        xor ^= a[i]
    if xor == 0:
        print("No")
    else:
        print("Yes")

反尼姆博弈（Anti - Nim）

[SHOI2008] 小约翰的游戏

题目描述

小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有 $n$ 堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。

小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。

输入格式

本题的输入由多组数据组成，第一行包括一个整数 $T$（$1\le T\le 500$），表示输入总共有 $T$ 组数据。

每组数据的第一行包括一个整数 $N$（$1\le N\le 50$），表示共有 $N$ 堆石子，接下来有 $N$ 个不超过 $5000$ 的整数，分别表示每堆石子的数目。

输出格式

对于每组数据，如果约翰能赢得比赛，则输出 John，否则输出 Brother，请注意单词的大小写。

样例输入

2
3
3 5 1
1
1

样例输出

John
Brother

提示

• 对于 $40\%$ 的数据，$T\le 250$；
• 对于 $100\%$ 的数据，$T\le 500$。

和尼姆博弈的题面几乎一样，唯一的区别在于胜利条件：
在反尼姆博弈中，取走最后一个石子的玩家输掉比赛。
让我们从简单的情形入手：只有一堆且为1，无需多言，后手胜利
扩大堆数：但确保每一堆都是1，那么只需要判断奇偶性，奇数则先手败，偶数则后手败
扩大每堆的数量：
只有一堆不是1，其余堆都是1，那么先手可以选择拿完或留一个（给后手奇数个1的局面）
从而后手必败,先手必胜。
一般情况：任意堆石子>1，任意堆石子小于1
有点无从下手了，但我们可以发现：
随着石子数在减少,一定会有人面临只有一堆石子大于1的情况,那么他就必胜。
这就回到了Nim博弈的感觉了

请看code：

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if sum(a) == n:
        print("John") if n % 2 == 0 else print("Brother")
    else:
        xor = 0
        for i in range(n):
            xor ^= a[i]
        if xor == 0:
            print("Brother")
        else:
            print("John")

END

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢