第十三章 综合实践

C++程序设计宋存利第十三章综合实践实践内容：1.旅行商问题（TSP）2.简易版贪吃蛇游戏3.学生信息管理系统的设计13.1旅行商问题（TSP）问题描述TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。13.1旅行商问题（TSP）2.设计思路求解旅行商问题的方法很多，可用遗传算法、禁忌搜索算法、粒子群算法、贪心法等等。

本案例首先采用简单的能求出问题的近似最优解的最近邻点策略来求解该问题，该算法思想是从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。即给定初始的城市a，寻找与其邻接的最短距离的城市b，记录二者之间的路径并增加总路径长度；下一次从城市b开始，寻找与b邻接的最短距离的城市,循环查找，直到找到n-1条路径（n为城市个数），最后加上终点回到起点的边即可。13.1旅行商问题（TSP）3.算法分析对TSP问题描述采用类实现，类名不妨定义为TSP，对该问题描述至少要由数据成员城市个数(int)城市间距离（数组）出发城市（int)旅行经过城市(int)路径长度(int)成员函数应包含：构造函数：该函数完成城市的个数、城市间的距离、出发城市等的初始化操作输出函数：完成城市距离矩阵的输出操作邻域贪心法函数：求旅行线路输出旅行线路函数：将贪心法求得的旅行线路输出。13.1旅行商问题（TSP）4.具体算法实现如下：TSP.txt13.2简易版贪吃蛇游戏游戏介绍：

贪吃蛇游戏是一款经典的小游戏，一条蛇在围墙内寻找随机出现的食物（一个时刻只能有一个食物），当蛇头碰到食物，则视为蛇吃到食物，玩家积分则增加10分，蛇身长长一节。当玩家按下方向键后，蛇的运动方向发生相同改变，当蛇碰触围墙或蛇头碰到自身身体，则游戏结束。游戏共有两个模式，其中普通模式，蛇的游走速度共8个等级，一旦初始设置游戏等级，则蛇的游走速度在游戏过程中不变，只是增加积分，蛇的长度。而冒险模式，则随着积分每增加60分，蛇的速度也提升一个等级，共5个等级。13.2简易版贪吃蛇游戏2.设计思路：（1）在游戏中，应能设置游戏模式，本游戏设置为普通模式和冒险两种模式，蛇的速度对应8个等级。（2）蛇的描述，本案例中，蛇头用@符号表示，蛇身和蛇尾用0来表示，初始蛇的长度尾3。每当蛇吃到食物，则蛇身增长1个0，需要在游戏过程中记录蛇头和蛇尾的位置，并需要记录蛇头移动方向和蛇尾前一个蛇身的移动方向，以便在更新蛇位置时，根据反向键的控制更改蛇头和蛇尾的位置。（3）食物同一时刻只能出现一个食物，用符号%表示。一旦食物被蛇吃掉，则此食物消失，在游戏框的其他位置随机出现一个食物。（4）游戏框、食物、蛇的相关信息均存储在一个二维数组中，随着蛇的游动速度进行更新。其中，游戏框每次不发生变更，变更的地方在游走的蛇，而蛇每游走一次，蛇的变化主要在舌头和蛇尾的位置，其他位置不变，每变化一次，则刷新输出二维数组。若一个游走时间单位中，没有按下方向键，则按照蛇的原方向继续游走，蛇长不变，刷新输出二维数组。13.2简易版贪吃蛇游戏3.算法分析蛇snake类，它描述蛇头，蛇尾的位置，因此其数据成员定义为横坐标x和纵坐标y。食物food类，它描述食物的位置，因此其数据成员由横坐标x和纵坐标y。13.2简易版贪吃蛇游戏非常重要的一个类：

map类，它来描述整个游戏的属性及动作，其中数据成员包括：

食物、蛇头、蛇尾（记录它们的位置）、当前的游戏模式（普通和冒险两种取值）、当前的游戏等级（1-8个等级）、当前取得的成绩（每吃掉一个食物成绩增加10）、蛇当前的游走方向队列（deque）、蛇当前的游走速度（由游戏的等级和模式确定的值）、游戏地图（记住当前时刻蛇的位置、游戏框、食物等等的位置信息）、蛇的可游走方向（五个常量值，上下左右及暂停），游戏可允许的速度（8个常量值）。13.2简易版贪吃蛇游戏Map类的成员函数包括：构造函数，完成上述数据成员的初始化操作，游戏的初始信息设置，用hello函数完成，在此函数中完成游戏模式、游戏等级的设计。游戏初始化算法initialize_Map：完成对游戏框，蛇头、蛇尾，食物的初始化。输出当前游戏窗口Show_Map：完成map数组信息的输出操作。跟新游戏信息模块Update_Map:对二维数组map的更新操作。本游戏的主要核心模块重置模块Reset：完成游戏信息的重新设置，开始新的一场游戏。13.2简易版贪吃蛇游戏4.STL库函数应用介绍:(1)_khbit()函数该函数的作用是检查控制台窗口的按键是否被按下。其格式为：int_kbhit(void);

如果在调用该函数时，有按键被按下，则返回一个非零值，否则该函数的返回值是0。需要注意的是，该函数是一个非阻塞函数，不管有没有按键被按下，该函数都会立即返回。_khbit()函数一般与_getch()函数与getche()函数组合使用获取按键信息。13.2简易版贪吃蛇游戏（2）_getch()函数

该函数的作用是从控制台中获取输入的字符，在获取输入的字符之后，并不会在控制台中显示该字符。该函数的格式为：int_getch(void);该函数的返回值是获取到的字符值。需要注意的是，_getch()函数是一个阻塞函数，直到有字符输入时才会返回，所以该函数不会返回错误值。注意：_khbit()函数和_getch()函数都是在conio.h头文件中定义。13.2简易版贪吃蛇游戏（3）clock()函数该函数返回该进程执行的该函数时刻的毫秒值。在头文件<ctime>中，注意事项：键盘的上下左右键分为两个字节，其中第一个字节ASCII码均为224，第二个字节分别为：72、80、75和77。空格键的ASCII码是32，回车的ASCII码是13，它们均为一个字节。5.具体实现13.3学生信息管理系统的设计1.问题描述

该系统完成学生信息的维护工作，也就是对学生信息的增删改查功能，学生信息存放在一个二进制文件中，通过该程序对之进行维护管理，学生信息包括学号、姓名、班级、年级、性别、联系电话等信息。要求设置有管理人员来完成学生信息的维护工作，也就是说不能随便什么人都可以对学生信息进行修改，以便保证学生信息的安全性。管理人员有多个，每个管理人员均可对学生信息进行维护操作，但只有主任管理员可对管理员信息进行维护。当首次使用本系统时，第一个注册的人员自动是主任管理人员，它拥有系统的所有操作权限，同时他可增加其他管理人员来对学生信息进行维护工作。13.3学生信息管理系统的设计2.设计思路根据面向对象程序设计思路，设计类如下。（1）账号类记录管理人员的用户名和密码信息，并可简单对账户信息进行设置和获取的相关函数。（2）学生类的数据成员包括学号、姓名、班级