AI 的早期萌芽？用 Swift 演绎约翰·康威的「生命游戏」
文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
你有没有想过，能不能通过简单的规则模拟出生与死亡？「生命游戏」正是这样一种充满魅力的数学模拟系统。这篇文章我们来聊聊它的规则到底有多神奇，并用 Swift 实现一个原地更新的算法，完全不需要额外内存空间，还能用得很优雅。如果你是算法练习者或者对模型仿真感兴趣，这篇你一定不能错过。
描述
生命游戏最早由数学家 John Conway 提出，是一种“零玩家游戏”。什么意思？就是说，一旦设置好初始状态，系统会自动演化，不再需要人为干预。
我们把一个二维网格当作世界，每个格子就是一个细胞。每个细胞的状态可能是“活”或“死”，状态变化完全依赖它周围八个邻居的状态。核心的规则有这几条：
- 活细胞周围活邻居少于 2 个 → 死（孤独）
- 活细胞周围 2 或 3 个活邻居 → 继续活着
- 活细胞周围超过 3 个活邻居 → 死（过度拥挤）
- 死细胞周围恰好有 3 个活邻居 → 复活！
所以我们要做的就是根据这四条规则，在原数组上进行原地更新，生成下一轮的世界。
题解答案
我们使用一个小技巧来原地记录状态的变化：
- 活→死 用
-1表示 - 死→活 用
2表示
这样我们在遍历的时候可以保留旧状态（通过 abs(board[i][j]) 取得），等所有状态都计算完之后再统一转换回 0 或 1。
题解代码分析
func gameOfLife(_ board: inout [[Int]]) {let m = board.countlet n = board[0].countlet directions = [(-1,-1), (-1,0), (-1,1),( 0,-1), ( 0,1),( 1,-1), ( 1,0), ( 1,1)]for i in 0..<m {for j in 0..<n {var liveNeighbors = 0// 统计活邻居数量for dir in directions {let x = i + dir.0let y = j + dir.1if x >= 0 && x < m && y >= 0 && y < n {if abs(board[x][y]) == 1 {liveNeighbors += 1}}}// 应用规则if board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {board[i][j] = -1 // 活→死}if board[i][j] == 0 && liveNeighbors == 3 {board[i][j] = 2 // 死→活}}}// 最终状态统一替换for i in 0..<m {for j in 0..<n {board[i][j] = board[i][j] > 0 ? 1 : 0}}
}
示例测试及结果
我们用几个例子跑一下看看效果。
var board1 = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]gameOfLife(&board1)
print(board1)
// 输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]var board2 = [[1,1],[1,0]]gameOfLife(&board2)
print(board2)
// 输出：[[1,1],[1,1]]
你可以把这段代码直接贴到 Xcode Playground 或命令行 Swift 项目里跑一跑，观察每轮世界的变化，非常直观。
时间复杂度
我们遍历了整个二维数组一次，并对每个元素最多再遍历 8 个邻居，所以：
时间复杂度：O(m * n)
其中 m 和 n 是二维数组的行数和列数。
空间复杂度
我们没有使用额外的数组，只是在原数组中用 -1 和 2 来标记变化。
空间复杂度：O(1)（原地算法）
总结
“生命游戏”听起来像是一种编程游戏，但其实它也是模拟系统、分布式模型、甚至人工生命研究中的一个缩影。通过这种原地算法优化，我们不仅节省空间，还能更贴近“状态转移”的本质。
这道题的亮点在于如何处理状态切换时的数据保存问题，如果直接改掉原始数据，我们就没法知道旧值是否活着。而用 -1 和 2 的技巧正好帮我们保留了历史信息，最终只需一轮替换就能搞定。