Rust语言实现SG函数算法详解（从零开始掌握博弈论中的SG定理）

mex 函数的实现

在计算 SG 值前，我们需要先实现 mex 函数。它的作用是找出一个非负整数集合中未出现的最小非负整数。

fn mex(values: &Vec<usize>) -> usize {    let mut seen = vec![false; values.len() + 1];    for &v in values {        if v <= values.len() {            seen[v] = true;        }    }    for (i, &not_seen) in seen.iter().enumerate() {        if !not_seen {            return i;        }    }    values.len() + 1}

SG 函数的递归实现

假设我们有一个取石子游戏：每次可以从一堆石子中取 1、3 或 4 个石子。我们来计算不同石子数量下的 SG 值。

use std::collections::HashMap;fn sg(n: usize, memo: &mut HashMap<usize, usize>) -> usize {    if let Some(&value) = memo.get(&n) {        return value;    }    let moves = vec![1, 3, 4];    let mut next_sgs = Vec::new();    for &take in &moves {        if take <= n {            next_sgs.push(sg(n - take, memo));        }    }    let result = mex(&next_sgs);    memo.insert(n, result);    result}fn main() {    let mut memo = HashMap::new();    for i in 0..=20 {        println!("SG({}) = {}", i, sg(i, &mut memo));    }}

运行上述代码，你会看到类似如下的输出：

SG(0) = 0SG(1) = 1SG(2) = 0SG(3) = 1SG(4) = 2SG(5) = 2...

如何判断胜负？

在多个独立子游戏组成的复合游戏中（例如多堆石子），总游戏的 SG 值等于各子游戏 SG 值的异或和（XOR）。

• 若异或和为 0 → 先手必败；
• 若异或和不为 0 → 先手必胜。

为什么用 Rust 实现 SG 函数？

Rust 以其内存安全、零成本抽象和高性能著称，非常适合编写算法核心逻辑。使用 HashMap 进行记忆化搜索，既能避免重复计算，又能保证类型安全，是实现 SG 函数的理想选择。

总结

通过本文，你已经掌握了：

• SG 函数的基本定义与 mex 运算；
• 如何用 Rust 递归+记忆化实现 SG 函数；
• 如何利用 SG 值判断组合游戏的胜负。

希望这篇 Rust SG函数 教程能帮助你在算法竞赛或项目开发中灵活运用 博弈论SG定理。继续练习更多变种题目（如“Nim 游戏”、“Chomp 游戏”等），你的 Rust算法教程 之路会越走越宽！

记住：理解 组合游戏SG值 的核心在于状态转移与 mex 运算。动手写代码，比死记硬背更有效！