辅导大、辅导大学计算机基础编程

《大学计算机基础》常规班大作业题目

要求：从下列题目中，选择1道题目作为大作业，实现程序并撰写实验报告；文科学生可以选做任何题目，理科学生不可以选做“文科题目”。

作业一   信息录入与查找系统

设计一个信息录入与查找系统，使其具有基本身份信息的录入功能，并能在录入的数据中根据一个或多个查找关键字查询出所有符合条件的人。具体要求如下：

1、设计一个 GUI 界面，其中具有多个输入框，对应姓名、性别、年龄、血型、星座、身高、体重等数据；并有确定、查找、清除、Backspace 等按钮。当单击确定键时，可将输入框中的信息录入，形成一条记录，并清空当前输入框中的内容。要求输入记录的条数不少于 20 条。

2、若任何一个输入框中的内容为空，单击确定键时返回错误信息，不添加此记录。

3、可以通过在输入框中输入查询信息（可以是多个查找条件），单击查找键，找出全部符合要求的人的姓名信息，并显示在一个查找结果框中，若未找到则显示未找到。

4、功能扩展。事先将全部记录存入一个文件（如 txt 或 Excel 文件）；增加一个“文件读入”按钮，从文件中批量读取记录到系统中；增加一个“记录导出” 按钮，可以导出全部记录到一个文件中。你还可以增加其他你能想到的功能，如删除一条记录、修改一条记录等。

5、撰写大作业实验报告，包括作业完成功能、实现方案、设计思路（给出关键代码）和涉及的知识点、创新点或增加功能、程序运行结果截图等。

6、课程学习总结：课程收获、难点分析、教师授课评价、助教评价、课程进一步改进建议。

提示 1：可以用 Text 组件实现输入框。单击确定键时，首先判断是否所有的文本框中内容都不为空，若任何一个为空，则生成一个错误信息的小窗体；若均不为空，则将全部信息录入。

提示 2：查找时，可首先将全部查找关键字记录，然后逐个跟已存放的信息进行比对；对于关键字全部相等的记录，则在结果框中输出该记录的姓名信息。提示 3：记录的存放可以使用列表或字典，注意列表嵌套或字典嵌套的使用。

提示 4：文件读取和输出请学习教材和课件中文件读写操作相关内容。

 

作业二   汉诺塔游戏

有这样一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的 64 片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

现在请你编写一个程序，完成一个模仿汉诺塔的益智小游戏，具备图形界面和以下功能：

1、输入整数 n，生成对应层数的汉诺塔；

2、可以选中三根针之一最上面一片进行移动；

3、复选取消选择；

4、判断移动是否合法；

5、当全部金片由针 1 移至针 3 时，游戏结束；

6、制作可视化游戏界面；

撰写大作业实验报告，包括作业完成功能、实现方案、设计思路（给出关键代码）和涉及的知识点、创新点或增加功能、程序运行结果截图等。

课程学习总结：课程收获、难点分析、教师授课评价、助教评价、课程进一步改进建议。

GUI 参考样例：

：

作业三 最大团问题

使用回溯法或动态规划解决较小规模的最大团问题。

1、图：由点、边（点与点之间连线），组成的集合，如点集 V=[0,1,2,3,4]，边集 E=[[1,3,4],[2,3,4],[4],[4],[]]，则（V，E）就是一个图，其表达的意思如下：

 

该图中含有 5 个端点，分别为 0,1,2,3,4，这些点存在 V 中，如端点 1 对应 V[1]=1 端点之间会连着线，称为边，如 1 和 2 之间连的边，就对应 E 中 E[1]=[2,3,4] 的元素 2，如 0 和 4 之间连的边就对应 E[0]=[1,3,4]含有元素 4（E[4]=[]不含元素

0 是因为 0<4，只需在 E[0]中记录了 4 即可）

2、团：一个图可能会有多个团，团是 V 的子集，记为集合 G，且保证 G 中任意两点之间都有连线如 G=[1,3,4]，其中 1,3,4 三点两两相连，一个图的包含元素最多的团称为最大团

3、本次实验要求同学们用python实现用回溯法或者分支限界法（动态规划）找出一个图的最大团（如果有多个请全部找出）并打印出来。

4、回溯法说明

 

如上图所示，回溯法通过函数递归实现，在每一次可能存在不同解的时候（例如本题中，最大团是否含有元素 0），先尝试其中一种情况（例如本题中假定含有元素 0），然后在此基础之上继续求解（例如本题中，求含有元素 0 的最大团），当走至尽头时（例如迷宫中走入死角,例如本题中，已经求完含有元素 0 的最大团），就返回上一级尝试另一种情况（例如迷宫中返回上一个岔路口看是否还有别的路可走，本题中假定不含有元素 0 继续求解）

5、分支限界法说明

回溯法是深度优先算法，而分支限界法是广度优先算法。分支限界法类似于穷举法，但它会不断地将不可能的情况排除，还好比所有可能的解是一棵树，分支限界法会从下往上，不断地将走不通的树枝裁掉，再沿剩下的树枝走下去。其中会用到动态规划。

如本题中，可以将问题分为 5 段：求含有一个、两个、三个、四个、五个元素的团，其中含有 N 元素的团必包含含有 N-1 个元素的团，故只需在上一段问题的答案的基础上，尝试给团添加新的元素，这即为动态规划。实际上例如求解出两个元素的团，如本题中的[0,1]，[0,3]，[0,4]，[1,2]，[1,3]，[1,4]，[2,4]，[3,4]，就是一次裁枝，裁掉的是“含有[0,2]或[2,3]”的所有解，分支限界法由此可不断地缩小所有可能解的集合，因此会比盲目的穷举少很多计算。

6、实现要求

1）在文件开头便声明列表 V,E，并直接赋值，例如：

 

2）回溯法输出样例:

 

3）分支限界法输出样例：

 

 

作业四   凸包问题

使用 Graham 扫描法解决凸包问题，通过输入的点的坐标，计算出一个最小的凸包，输出在凸包边界上的点。

1、凸包：假设平面上有多个点，过某些点作一个多边形，使这个多边形能

把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。

（如图就是一个凸包）

2、凸多边形：如果把一个多边形的所有边中，任意一条边向两方无限延长

成为一直线时，其他各边都在此直线的同旁，那么这个多边形就叫做凸多边形。

3、Graham 扫描法：

1)首先，找到所有点中 y 坐标最小的某一个点。

2)以这个点为基准求所有点的辐角（0-180°）并按照辐角对这些点排序，前述基准点在最面，

3)设这些点为 P[0]..P[n-1]

4)注:这样预处理后,保证 p[0],p[1]和 p[n-1]都是凸包上的点.  

5)建立一个栈,初始时前三个点进栈,对于剩余的每个点，若栈顶的两个点与它不成"向左转的

6)关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈；  

7)所有点处理完之后栈中保存的点就是凸包了。

4、其它实验要求：

1)点的坐标由键盘输入；

2)从输入的点当中，输出凸包边界上的点的坐标；

3)有一定的 GUI 界面。

5、撰写大作业实验报告，包括作业完成功能、实现方案、设计思路（给出关键代码）和涉及的知识点、创新点或增加功能、程序运行结果截图等。

6、课程学习总结：课程收获、难点分析、教师授课评价、助教评价、课程进一步改进建议。

7、GUI 示例：

 

 

作业五   贪吃蛇

设计一个贪吃蛇小游戏，使其具有基本的游戏功能。具体要求如下：

1、方向键控制贪吃蛇的移动，且按下与贪吃蛇行进方向相反的方向键时无响应，即蛇不能直接调转行进方向。

2、随机生成食物的位置，生成的位置不能与贪吃蛇身体重合。

3、贪吃蛇初始长度大于一个单位长度，吃到食物后身体长度增加一个单位长度。

4、蛇头碰到身体或者边框即判定死亡，游戏结束，结束后显示分数。

5、撰写大作业实验报告，包括作业完成功能、实现方案、设计思路（给出关键代码）和设计的知识点、创新点或增加功能、程序运行结果截图等。

6、课程学习总结：课程收获、难点分析、教师授课评价、助教评价、课程进一步改进建议。

提示：可以定义类实现蛇、食物等。：