算法超简单：趣味游戏带你轻松入门与实践

本书通过趣味游戏编程项目讲解算法，提升读者学习算法的兴趣，降低读者学习算法的难度，增强读者将算法应用于编程实践的能力。 本书共 14 章，通过猜数字、飞翔的小鸟、得分排行榜、汉诺塔、八皇后、消灭星星、贪吃蛇、走迷宫、连连看、吃豆人、滑动拼图、井字棋、垒积木、十步万度等游戏，讲解顺序查找算法、二分查找算法，图形库 EasyX，插入排序算法、冒泡排序算法、选择排序算法、快速排序算法，递归算法，暴力搜索算法、回溯算法，FloodFill 算法，常见的数据结构（数组、链表、队列、栈、图、树）、标准模板库（STL），十字分割算法、图的广度优先搜索算法和深度优先搜索算法，加权图上的迪杰斯特拉算法、贪婪优先搜索算法、A*算法，状态空间上的搜索算法，博弈树的极大极小值搜索算法、α-β剪枝搜索算法，动态规划算法，遗传算法。 本书适合想要学习基础算法或练习编程实践的读者阅读，也可作为高等院校数据结构与算法相关课程或编程实践课程的指导用书。读者在阅读本书之前需要具备基础的C语言编程知识。

童晶，浙江大学计算机专业博士，河海大学副教授、硕士生导师、人工智能系主任。 主要从事计算机图形学、虚拟现实、数字化艺术等方向的研究，发表学术论文超过 30 篇，曾获中国发明协会发明创业奖成果奖一等奖、浙江省自然科学奖二等奖。 积极投身于教学与学生创新工作，指导学生获得“英特尔杯”大学生电子设计竞赛嵌入式系统专题邀请赛全国一等奖、“挑战杯”全国大学生课外学术科技作品竞赛全国三等奖、“中国软件杯”大学生软件设计大赛全国一等奖、中国大学生服务外包创新创业大赛全国一等奖等多个奖项。 具有 18 年的一线教学经验，所开设的课程在校内广受好评，获评河海大学优秀主讲教师。在知乎、哔哩哗哩、中国大学 MOOC 等平台的教学课程已有千万次的阅读与学习记录。

第 1 章 猜数字..1 1.1 实现猜数字游戏 .. 1 1.2 顺序查找 .. 2 1.3 二分查找 .. 7 1.4 算法的效率 .. 12 1.5 小结 .. 13 第 2 章 飞翔的小鸟 ..14 2.1 EasyX 图形库 .. 14 2.2 小球的自由落体 .. 17 2.3 按空格键让小球向上飞 .. 18 2.4 游戏程序框架改进 .. 19 2.5 添加水管障碍物 .. 22 2.6 得分的计算与显示 .. 24 2.7 更多水管障碍物 .. 26 2.8 图片的使用 .. 27 2.9 小结 .. 33 第 3 章 得分排行榜 .. 34 3.1 插入排序及其可视化 .. 34 3.2 冒泡排序及其可视化 .. 39 3.3 选择排序及其可视化 .. 42 3.4 快速排序及其可视化 .. 45 3.5 拓展练习：查找算法和更多排序算法的可视化 .. 51 3.6 小结 .. 52 第 4 章 汉诺塔 .. 53 4.1 实现汉诺塔游戏 .. 53 4.1.1 定义柱子结构体与可视化 ..54 4.1.2 通过鼠标点击选中柱子 ..56 4.1.3 移动盘子 ..58 4.1.4 判断盘子是否可以移动 ..59 4.1.5 提示信息与胜负判断 ..60 4.2 递归求解汉诺塔问题 .. 61 4.3 汉诺塔自动求解过程的可视化 .. 65 4.4 拓展练习：绘制分形树 .. 68 4.5 小结 .. 69 第 5 章 八皇后 .. 70 5.1 实现八皇后游戏 .. 70 5.1.1 绘制棋盘和提示信息 ..70 5.1.2 通过鼠标交互绘制皇后棋子 ..72 5.1.3 游戏胜负判断 ..74 5.2 暴力搜索 .. 76 5.2.1 八重 for 循环输出八皇后的所有摆法 ..76 5.2.2 暴力搜索求出八皇后的所有摆法 ..77 5.3 回溯 .. 79 5.4 八皇后游戏自动求解过程的可视化 .. 82 5.5 拓展练习：一笔画游戏、数独游戏 .. 85 5.6 小结 .. 86 第 6 章 消灭星星 .. 87 6.1 消灭星星游戏基础版 .. 87 6.1.1 基础数据结构和画面显示 ..87 6.1.2 通过鼠标点击消除单个方块 ..90 6.2 基于 FloodFill 算法消除连通的方块 .. 91 6.3 方块位置的更新 .. 93 6.3.1 方块下落 ..93 6.3.2 方块左移 ..94 6.4 游戏完善 .. 95 6.5 拓展练习：扫雷游戏 .. 96 6.6 小结 .. 98 第 7 章 贪吃蛇 .. 99 7.1 常见数据结构 .. 99 7.1.1 数组 ..99 7.1.2 链表 ..100 7.1.3 队列 ..101 7.1.4 栈 ..102 7.1.5 图 ..103 7.1.6 树 ..103 7.2 标准模板库 .. 104 7.2.1 vector ..104 7.2.2 queue ..107 7.2.3 stack ..109 7.2.4 string ..110 7.2.5 map ..110 7.3 实现贪吃蛇游戏 ..111 7.3.1 数据结构和画面显示 ..111 7.3.2 蛇的自动移动 ..114 7.3.3 通过鼠标控制蛇的移动方向 ..114 7.3.4 添加食物和障碍物 ..116 7.3.5 蛇吃食物后的处理 ..117 7.3.6 为蛇添加眼睛 ..119 7.4 拓展练习：飞机大战 .. 120 7.5 小结 .. 120 第 8 章 走迷宫 .. 121 8.1 实现走迷宫游戏 .. 121 8.1.1 迷宫地图初始化与显示 ..121 8.1.2 添加小球 ..124 8.1.3 通过键盘控制小球移动 ..125 8.2 基于十字分割算法自动生成迷宫地图 .. 126 8.3 图的广度优先搜索算法 .. 135 8.4 图的深度优先搜索算法 .. 137 8.5 迷宫游戏自动求解 .. 139 8.6 小结 .. 144 第 9 章 连连看 ..145 9.1 连连看游戏基础版 .. 145 9.1.1 数据初始化与显示 ..145 9.1.2 记录和处理鼠标点击操作 ..149 9.2 基于广度优先搜索算法的消除判断 .. 150 9.2.1 基于广度优先搜索算法的方格连线和消除 ..150 9.2.2 基于广度优先搜索算法限制拐弯次数 ..152 9.2.3 游戏胜负的判断与显示 ..156 9.3 拓展练习：围住神经猫 .. 156 9.4 小结 .. 157 第 10 章 吃豆人..158 10.1 吃豆人游戏基础版 .. 158 10.1.1 地图的存储与显示 ..158 10.1.2 玩家对吃豆人的控制 ..161 10.1.3 图片切换与动画效果 ..163 10.1.4 幽灵随机移动 ..165 10.1.5 胜负判断 ..166 10.2 迪杰斯特拉算法 .. 167 10.3 贪婪最佳优先搜索算法与 A* 算法 .. 170 10.4 三种算法的实现与对比 .. 173 10.5 幽灵自动追踪 .. 181 10.6 小结 .. 182 第 11 章 滑动拼图 ..183 11.1 实现滑动拼图游戏 .. 183 11.1.1 数据结构和画面显示 ..183 11.1.2 生成随机初始状态 ..186 11.1.3 鼠标交互与胜利判断 ..187 11.2 状态空间上的搜索算法 .. 189 11.3 滑动拼图游戏的自动求解 .. 191 11.4 拓展练习：农夫过河游戏 .. 194 11.5 小结 .. 195 第 12 章 井字棋..196 12.1 双人对战井字棋 .. 196 12.1.1 数据结构和画面显示 ..196 12.1.2 通过鼠标交互下棋 ..198 12.1.3 胜负判断 ..199 12.2 棋局的估值函数 .. 201 12.3 基于博弈树的极大极小值搜索算法实现人机对战下棋 .. 205 12.4 基于 α-β 剪枝搜索算法实现人机对战下棋 .. 208 12.5 拓展练习：人机对战五子棋 .. 212 12.6 小结 .. 212 第 13 章 垒积木..213 13.1 实现垒积木游戏 .. 213 13.1.1 积木块的绘制 ..213 13.1.2 积木块的旋转 ..216 13.1.3 多个积木与画面显示 ..217 13.1.4 垒积木操作 ..219 13.1.5 高度统计与胜负判断 ..220 13.1.6 游戏完善 ..221 13.2 递归回溯求解垒积木问题 .. 222 13.3 动态规划求解垒积木问题 .. 226 13.4 小结 .. 231 第 14 章 十步万度..232 14.1 实现十步万度游戏 .. 232 14.1.1 数据结构与画面显示 ..232 14.1.2 鼠标交互与指针旋转 ..235 14.1.3 旋转传播与得分统计 ..236 14.1.4 显示旋转过程动画 ..238 14.2 遗传算法基础 .. 239 14.3 基于遗传算法自动求解十步万度游戏 .. 241 14.4 小结 .. 249