作业题目2013.doc

作业题目请大家认真阅读下面红色字体部分！要求与说明：l 作业成绩总分40分，起评分下列作业题目各自不同，见具体作业题目，自选作业需根据实际判定。l 鼓励创新。可自拟（或结合实际项目情况）题目，有创新、有价值的题目起评分在35分以上。l 所有作业要求使用Visual studio（各个版本）编程工具实现。l 所有题目都要求具有完整的图形用户界面、输入/出接口，功能要完备。l 题目涉及的算法实现方法不限（同一个问题可以使用不同的算法实现）。l 要求撰写设计报告（内容包括：问题分析、算法选择、方案设计、编程实现），设计报告以Word文档形式与作业程序源代码压缩到一起提交。l 任何上交的作业（包括：设计报告、程序源代码）仅作为作业看待，不承担任何版权问题，而且必须是独立完成。l 提交作业时，请将程序目录下的debug和release目录及其下所有内容删除，并统一用WinRAR压缩，压缩文件名的命名格式：学号西文字符，半角，短横线姓名-西文字符，半角，短横线所在院系名称例如：2013090143-姓名-学院命名不规范将在起评分基础上扣2分！l 作业的提交时间：2013年11月25日12月23日。l 作业的提交方式：统一提交到为提交作业的独立性（避免作业提交后被别人下载或被别人看到），从2013年12月1日起，邮箱将不再向大家开放，邮箱中的实例、文档请大家在此之前下载。作业提交日期不得晚于2013年12月23日！l 作业只允许提交1次。l 作业提交名单（最终）将在考试日公布。l 请大家根据自己的情况，在作业完成后及时提交，以免集中提交造成邮箱阻塞而影响提交。l 被判定为抄袭者，其成绩按如下计算：非抄袭所得成绩/抄袭次数，抄袭人次3次以上，所有抄袭、被抄袭者成绩为0；一、 作业题目1：（起评分30分）1、 编制一个图形化的列表程序，具体要求如下：a) 以双向链表为数据模型，分别将链表的结点和链表本身定义为两个C+类，类名分别为CNode、CList。b) 一般结点的图形显示结果如下：c) 头结点显示如下：d) 尾结点显示如下：e) 当前结点显示如下：f) 整个链表显示结构如下：g) 链表应完成下列操作：i. 插入、追加、删除结点ii. 选中某结点成为当前结点iii. 结点可以拖拽iv. 链表双向遍历v. 通过对话框修改某结点的数据域h) 程序结果要求：i. 采用MDI方式ii. 对链表的操作通过菜单完成iii. 结点和链表的串行化处理iv. 多视图更新二、 汉诺塔（Towers of Hanoi）问题（起评分28分）汉诺塔（Towers of Hanoi）问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔，其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔。从世界创始之日起，婆罗门的牧师们就一直在试图把塔1上的碟子移动到塔2上去，其间借助于塔3的帮助。由于碟子非常重，因此，每次只能移动一个碟子。另外，任何时候都不能把一个碟子放在比它小的碟子上面。按照这个传说，当牧师们完成他们的任务之后，世界末日也就到了。图1-1问题：1、已知有三个塔（1、2、3）和n个从大到小的金碟子，初始状态时n个碟子按从大到小的次序从塔1的底部堆放至顶部。2、要求把碟子都移动到塔2（按从大到小的次序从塔2的底部堆放至顶部）。3、每次移动一个碟子。4、任何时候、任何一个塔上都不能把大碟子放到小碟子的上面。5、可以借助塔3。作业要求：1、在窗口中画出初始时塔和碟子的状态。2、可以以自动或手动两种方式搬移碟子。3、自动搬移可以通过定时器或多线程的方法，每一次移动的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的移动过程如能实现动画最好。4、定义塔的描述类和碟子的描述类。5、在程序中，碟子的数目及每次移动的时间间隔可以通过对话框设置（也应该有默认值）。6、支持暂停功和继续的功能（在自动搬移过程中可以暂停，并继续）。7、暂停后，可以将当前的状态保存（碟子和塔的组合关系）。8、可以从7中保存的文件中读出某个状态，并继续移动。三、 聊天系统（起评分30分）创建一个聊天系统，该系统由服务器程序和客户端程序两部分构成。其简单的工作原理如下图所示。当服务器程序运行时，首先启动一个监听器，负责监听服务器的某个端口，当客户端要进行聊天时，首先要对服务器的特定端口进行连接请求，即客户端试图连接服务器被监听的端口时，服务器的监听器可以选择接受或拒绝连接请求。如果接受客户端的连接请求，则由监听器为客户端分配一个对应的“套接字”对象，这样在服务器和某个客户端之间就建立了一条数据管道，可以聊天了。本聊天室主要采用Socket（套接字）编写，套接字可以支持TCP和UDP协议。图1 聊天室工作原理图图2 聊天室服务器启动界面图3 聊天室服务器主界面聊天客户端状态信息待发送信息区聊天信息图4 聊天室客户端主界面图5 客户端连接服务器主界面除实现上述基本聊天功能外，还要求：（1） 在服务器端可以将客户登陆、退出及在线时间等情况记录并保存。（2） 服务器和客户端都可以将聊天记录保存。附加功能：可以在客户端和服务器端传送文件，支持视频功能。四、 开关盒布线问题（起评分32分）给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。我们的目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。图11a给出了一个布线的例子，其中有八个针脚和四个网组。四个网组分别是(1,4)，(2,3)，(5,6)和(7,8)。图11b给出的布线方案有交叉现象发生（(1,4)和(2,3)之间），而图11c则没有交叉现象发生。由于四个网组可以通过合理安排而不发生交叉，因此可称其为可布线开关盒（routable switch box）。（在具体实现时，还需要在两个相邻的电线间留出一定的间隔。我们要解决的问题是，给定一个开关盒布线实例，确定它是不是一个可布线的。图11 开关盒布线原理图作业要求：1、画出给定矩形布线区域（包括需要连同的线网组），针脚和线网组在数据库中存放，通过数据库接口读出。2、在自动布线的每一步，用图形标示其状态。3、自动布线的过程可以通过定时器或多线程的方法，每一次布线的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的布线过程如能实现动画最好。4、如需要，请定义相关的描述类。5、在程序中，请使用对话框设定需要的各种参数。6、布线完成后，请将结果存入数据库中。7、统计算法耗时。五、迷宫问题（起评分26分）迷宫（maze）是一个矩形区域，它有一个入口和一个出口。在迷宫的内部包含不能穿越的墙或障碍。在图2-1所示的迷宫中，障碍物沿着行和列放置，它们与迷宫的矩形边界平行。迷宫的入口在左上角，出口在右下角。假定用nm的矩阵来描述迷宫，位置(1,1)表示入口，(n,m)表示出口，n和m分别代表迷宫的行数和列数。迷宫中的每个位置都可用其行号和列号来指定。在矩阵中，当且仅当在位置(i,j)处有一个障碍时其值为1，否则其值为0。图2-2给出了图2-1中迷宫对应的矩阵描述。迷宫老鼠（ratinamaze）问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居（如图2-3所示）。图2-1 图2-2 图2-3作业要求：1、在窗口中画出初始时迷宫的状态，迷宫随机生成，并验证其合法性(可以通行的迷宫)。2、在自动寻找迷宫路径的每一步，用图形标示其状态。3、自动寻找迷宫路径可以通过定时器或多线程的方法，每一步的时间间隔可以自定，以人眼观察比较舒服为宜，每一步的过程如能实现动画最好。4、定义迷宫的描述类。5、在程序中，迷宫的大小及每步移动的时间间隔可以通过对话框设置（也应该有默认值）。6、支持暂停功和继续的功能（在自动寻径过程中可以暂停，并继续）。7、暂停后，可以将当前的状态保存。8、可以从7中保存的文件中读出某个状态，并继续。六、残缺棋盘问题（起评分30分）残缺棋盘（defective chessboard）是一个有2k2k个方格的棋盘，其中恰有一个方格残缺。图4-1给出k2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k=0时，仅存在一种可能的残缺棋盘（如图4-1a所示）。事实上，对于任意k，恰好存在22k种不同的残缺棋盘。残缺棋盘的问题是：要求用三格板（triominoes）覆盖残缺棋盘（如图4-2所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三格板总数为(22k-1)/3。可以验证(22k-1)/3是一个整数。k为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k=1时，正好存在3个非残缺的方格，并且这三个方格可用图4-2中的某一方向的三格板来覆盖。解决的思想：用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k2k残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k2k棋盘一个很自然的划分方法就是将它划分为如图4-3a所示的4个2k-12k-1棋盘。注意到当完成这种划分后，4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k2k棋盘仅仅有一个残缺方格）。首先覆盖其中包含残缺方格的2k-12k-1残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图4-3b所示，其中原2k2k棋盘中的残缺方格落入左上角的2k-12k-1棋盘。可以采用这种分割技术递归地覆盖2k2k残缺棋盘。当棋盘的大小减为11时，递归过程终止。此时11的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。图4-1图4-2图4-3作业要求：1、在窗口中画出初始时的残缺棋盘（棋盘的格数可以指定或在某个范围内随机生成，残缺格的位置随机生成）。2、自动进行残缺棋盘的覆盖，覆盖的过