综合程序练习题jc_chap(编辑修改稿)

综合程序练习题jc_chap(编辑修改稿)内容摘要：

第 5章 综合程序练习题 —— 贪吃蛇 主要算法提示 碰撞检测模块： 蛇移动模块：在程序中定义循环链表来表示蛇，并记录蛇头指针以及蛇尾指针、当前移动方向。 若有方向按键信息： a1. 按键方向跟当前方向相同或是相反，则不做处理； a2. 否则将当前方向设置为新的方向；按当前方向得到蛇头的下一位置；对该位置进行碰撞检测，判断该位置是什么状态 c1. 若是蛇身和墙壁，跳到步骤 e； c2. 若是空白，则将蛇尾设为蛇头，将倒数第二节设为蛇尾，更新蛇头的位置为当前的新位置。 界面上就把当前最新位置用蛇的颜色画上，并把原蛇尾用背景色擦除。 c3. 若是食物，则新增加当前位置做为蛇头，蛇尾不变。 利用记分模块更新分数。 并再重新随机产生食物。 返回 a做循环；游戏结束 第 5章 综合程序练习题 —— 五子棋 1：问题描述  五子棋基本规则：棋盘上形成横向、竖向、斜向的连续的相同颜色的五个棋子称为 “五连 ”。 黑白双方先在棋盘上形成五连的一方为胜。 若对局双方均认为不可能形成五连或是剩余棋盘空间已不足以形成五连则为和棋。 下棋过程中不考虑各种禁手规则。 2：基本功能  提供图形界面 、 键盘操作 、 人人对战 、 支持某方先下 、 棋盘 15*15，显示网格线 ， 黑白棋子 、 当前光标所在；显示当前执棋方 3：高级功能  支持人机对战，显示人机对子情况和胜负判别  悔棋功能  音效功能 第 5章 综合程序练习题 —— 五子棋 难点分析 1）胜负判别 2）悔棋功能 3）人机对战的人工智能部分 五子棋的人机对战是一个典型的博弈问题。 博弈问题一般可用极大 极小法和 αβ法求解（读者可找相关资料，一般人工智能或博弈论教材中会涉及这些内容）。 而即便是用 αβ法，五子棋的搜索空间还是相当庞大。 第 5章 综合程序练习题 —— 五子棋 设计及实现要点 游戏初始化模块 主循环控制模块 键盘处理模块 胜负判别模块 人工智能模块 游戏结束清理模块 五子棋程序的总体结构 第 5章 综合程序练习题 —— 五子棋 主要数据结构提示 （ 一 ） 1）棋盘用 15*15的二维数组表示，数组的每一个元素对应棋盘上的一个交叉点，用‘ 0’表示空位、‘ 1’代表玩家 1的子、‘ 2’代表玩家 2的子 ： char ChessBoard[15][15]。 第 5章 综合程序练习题 —— 五子棋 主要数据结构提示 （ 二 ） 2)用于搜索过程的结构体： typedef struct five_chess* point。 struct five_chess{ int x。 int y。 int layer。 int value。 int score。 int chess[LENGTH][LENGTH]。 int record[LENGTH][LENGTH]。 }。 其中， x,y表示在某个位置上扩展出来的新节点， layer是表示第几层扩展，用于控制扩展深度。 value表示该点上极大极小值， score表示叶子节点的得分，用于推算父辈节点的 value， chess这个二维数组表示扩展出来的棋盘信息， record记录在 x、 y点上扩展过的节点，如果没有扩展 record中对应某个值为 0。 如果record中没有可以扩展的节点，那么该层扩展结束，返回一个特定值。 第 5章 综合程序练习题 —— 五子棋 主要算法提示 （ 一 ） 对棋盘的评分算法。 评估一个棋盘的分数，主要通过扫描 整个棋盘，对每个点评分。 对某个点上评分从四个方向 ( 角度分别为 0、 4 90、 135的四个方向 )分别统计，进而 累积该点总分，最后得到整个棋盘的分数。 实际上对当前 的局面按照下面规则的顺序进行比较，如果满足某一条规 则的话，就给该局面打分并保存，然后退出规则的匹配。 注意这里的规则是根据一般的下棋规律的一个总结，在实 际运行的时候，可以添加规则和对评分机制加以修正。 第 5章 综合程序练习题 —— 五子棋 主要算法提示 （ 二 ） 人工智能部分的搜索算法流程如下（以扩展两层为例）：  根据棋盘信息 chessman[15][15]建立根结点 s0（数据结构：five_chesman） ,并把 s0压入堆栈中  扩展 s1=top()；判断 s1layer是否等于－ 1  s1layer等于－ 1， push(s1),扩展 s2=top(),查看 s2layer是否－ 1  s2layer!=1，计算此时棋盘得分 score，并判断是否要更改上一层的极小值  s2layer==1,pop()：判断是否更改极大值， max_chess指向得分最高的棋盘  如果 s1layer=1,表示搜索结束，返回最大棋盘信息 max_chess 第 5章 综合程序练习题 —— 搬运工 1：问题描述 在一个四周有围墙的仓库的中，堆放着若干箱子、阻挡箱子前进的障碍物，以及标识出了箱子需要被推到的目标位置。 游戏者通过观查分析，找到合适的策略，然后只能用推的方法把所有散落在场地中的箱子借助于空闲区间推到目标位置，即获得胜利；否则失败 2：基本功能  场地元素定义与设计 、 箱子的搬运动作 、 提供一定数量的按键功能实现游戏者对搬运工的多种操作 3：高级功能  提供多套场地  提供视听效果  智能识别游戏的终止  自动完成移动 第 5章 综合程序练习题 —— 搬运工 难点分析 墙壁 箱子 x y 死角判定： 这里举一个例子，如下图所示： 死角判定 第 5章 综合程序练习题 —— 搬运工 设计及实现要点 搬运工程序的总体结构 第 5章 综合程序练习题 —— 搬运工 主要数据结构提示 系统的组成元素主要包含外围墙壁、内部障碍物、箱子、搬运工。 我们先建立一个虚拟的元素（不妨称之为容器），它用来将整个图形界面网格化，并记录各种图形元素的位置等属性。 然后，再为各个图形元素建立相应的保存其特有信息的数据结构。 先定义两个基本结构，在后面也会用到： typedef struct tagRect /*矩形 */ { Point leftTop, rightButton。 /*矩形左上定点和右下定点 */ } Rect。 typedef struct tagPoint /*直角坐标系点 */ { int x, y。 } Point。 第 5章 综合程序练习题 —— 搬运工 主要数据结构提示 1）虚拟的容器结构体： typedef struct tagContainer { Rect cRect。 /*确定整个容器在屏幕上的坐标 */ int cBoard[N][M]。 /*N、 M是事先设定的网格行数和列数 */ } Container。 其中数组 cBoard其取值代表各网格是何种图形元素：箱子、空格、障碍、目标位置，其它必要属性，可自行酌情添加。 第 5章 综合程序练习题 —— 搬运工 主要数据结。