SG函数详解（C语言实现博弈论核心算法）

关键概念解释

• mex（Minimum Excludant）：最小非负整数不在集合中。例如 mex{0,1,3} = 2。
• SG(x) = mex{ SG(y) | y 是 x 的后继状态 }
• 多个独立子游戏的总SG值 = 各子游戏SG值的异或（XOR）

C语言实现SG函数

下面是一个经典的取石子游戏例子：有n堆石子，每次可以从任意一堆中取1~k个石子，最后无法操作的人输。我们来计算每堆石子数量对应的SG值。

#include <stdio.h>#include <string.h>// 计算mex值int mex(int *s, int n) {    for (int i = 0; i <= n; i++) {        if (!s[i]) return i;    }    return n + 1;}// 计算SG函数值void computeSG(int *sg, int n, int k) {    sg[0] = 0; // 终止状态SG值为0        for (int i = 1; i <= n; i++) {        int next[100] = {0}; // 标记后继SG值                // 遍历所有可能的操作（取1~k个石子）        for (int j = 1; j <= k && j <= i; j++) {            next[sg[i - j]] = 1;        }                sg[i] = mex(next, k);    }}int main() {    int n = 10; // 最大石子数    int k = 3; // 每次最多取3个    int sg[100];        computeSG(sg, n, k);        printf("石子数\tSG值\n");    for (int i = 0; i <= n; i++) {        printf("%d\t%d\n", i, sg[i]);    }        return 0;}

代码解析

上面的代码实现了SG函数的计算：

1. mex 函数找出集合中未出现的最小非负整数。
2. computeSG 函数从0开始递推计算每个状态的SG值。
3. 主函数输出0到n个石子对应的SG值，便于观察规律。

应用场景与总结

SG函数广泛应用于Nim游戏、取石子变种、棋盘游戏等博弈论问题中。掌握C语言实现SG函数不仅能提升你的算法能力，还能在ACM/ICPC等竞赛中快速解题。

记住：SG值为0 → 必败；SG值非0 → 必胜。多个子游戏时，总SG值为各子游戏SG值的异或结果。

通过本算法教程，相信你已经理解了SG函数的基本原理和实现方法。动手试试修改参数k或增加更复杂的游戏规则吧！