面向对象作业要求.docx

1、面向对象作业要求面向对象编程技术作业题要求与说明： 作业成绩总分40分，各题目如无特别声明，起评分均为30分，在此基础上根据实际完成情况、设计文档情况、特色等方面浮动，满分40分；自选题目起评分根据题目难易具体确定； 所有作业要求使用Visual studio（各个版本）编程工具实现； 所有题目都要求具有完整的图形用户界面、输入/出接口，功能要完备； 题目涉及的算法实现方法不限（同一个问题可以使用不同的算法实现）； 要求撰写设计报告（内容包括：问题分析、算法选择、方案设计、编程实现），设计报告以Word文档形式与作业程序源代码压缩到一起提交； 任何上交的作业（包括：设计报告、程序源代码）仅作为

2、作业看待，不承担任何版权问题，而且必须是独立完成； 提交作业时，请将程序目录下的debug和release目录及其下所有内容删除，并统一用WinRAR压缩，压缩文件名的命名格式：学号姓名-所在院系名称例如：2090001-姓名-学院命名不规范将在起评分基础上扣2分！ 作业要求在本课程结束一周内上交，即在2011年12月9日前必须提交作业，提交地址如下：h_lionstar或hlionstar一、开关盒布线问题（35分起）开关盒布线问题是这样的：给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发

3、生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。我们的目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。图1-1a给出了一个布线的例子，其中有八个针脚和四个网组。四个网组分别是(1,4)，(2,3)，(5,6)和(7,8)。图1-1b给出的布线方案有交叉现象发生（(1,4)和(2,3)之间），而图1-1c则没有交叉现象发生。由于四个网组可以通过合理安排而不发生交叉，因此可称其为可布线开关盒（routable switch box）。（在具体实现时，还需要在两个相邻的电线间留出一定的间隔。我们要解决的问题是，给定一个开关盒布线实例，确定它是不是一个可布线的。图11图

4、1-1b和1-1c中的电线都是由平行于x轴和y轴的垂直线段构成的，当然也可以使用不与x轴和y轴平行的线段。解决的思想：为了解决开关盒布线问题，我们注意到，当两个针脚互连时，其电线把布线区分成两个分区。例如，当(1,4)互连时，就得到了两个分区，一个分区包含针脚2和3，另一个分区包含针脚5-8。现在如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之中（即不会

5、出现两个针脚分别位于两个子分区的情形），那么这个分区就是可布线的。为了实现上述策略，可以按顺时针或反时针方向沿着开关盒的外围进行遍历，可从任意一个针脚开始。例如，如果按顺时针方向从针脚1开始遍历图3-1a中的针脚，那么将依次检查针脚1, 2, .,8。针脚1和4属于同一个网组，那么在针脚1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚4至针脚1之间出现的所有针脚构成了第二个分区。把针脚1放入堆栈，然后继续处理，直至遇到针脚4。这个过程使我们仅在处理完一个分区之后才能进入下一个分区。下一个针脚是针脚2，它与针脚3同属一个网组，它们又把当前分区分成两个子分区。与前面的做法一样，把针脚2放入堆

6、栈，然后继续处理直至遇到针脚3。由于针脚3与针脚2属同一个网组，而针脚2正处在栈顶，这表明已经处理完一个子分区，因此可将针脚2从栈顶删除。接下来将遇到针脚4，由于与之互连的针脚1正处在栈顶，因此当前的分区已经处理完毕，可从栈顶删除针脚1。按照这种方法继续进行下去，直至检查完八个针脚，堆栈变空，所创建的分区都已处理完毕为止。那么，对于不可布线的开关盒将会出现什么样的情况呢？假定图3-1a中的网组是：(1,5)，(2,3)，(4,7)和(6,8)。初始时，针脚1和2被放入堆栈。在检查针脚3时，将针脚2从栈顶删除。接下来针脚4被放入堆栈，因为针脚4与栈顶的针脚不能构成一个网组。在检查针脚5时，它也被

7、放入堆栈。尽管已经遇到了针脚1和针脚5，但还不能结束由这两个针脚所定义的第一个分区的处理过程，因为针脚4的布线将不得不跨越这个分区的边界。因此，当完成对所有针脚的检查时，堆栈不会变空。作业要求：1、画出给定矩形布线区域（包括需要连同的线网组），针脚和线网组在数据库中存放，通过数据库接口读出。2、在自动布线的每一步，用图形标示其状态。3、自动布线的过程可以通过定时器或多线程的方法，每一次布线的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的布线过程如能实现动画最好。4、如需要，请定义相关的描述类。5、在程序中，请使用对话框设定需要的各种参数。6、布线完成后，请将结果存入数据库中。7、统计算法耗

8、时。二、数据阿伦方差计算显示问题在科学研究实验中，经常遇到对大量的实验数据的处理问题。其处理方法有很多种，但其基本的处理一般包括：求均值、方差等。今假设有一检测量，其实验测量值服从正态概率密度分布，分布范围：，分布概率100%，其中是其数学期望，是该测量样本的方差，样本基本采样频率为10ms。作业要求：1、 根据概率分布函数生成一个不少于20000个采样值的样本，其均值和方差通过程序界面指定。如有类似的实际检测数据样本，也可以使用实际样本。2、 对该采样样本，根据给定的时间间隔t0，对样本数据分段，总共（Tt0）n段，T为整个样本对应的采样时间。每一段内的数据求平均，得到n个平均值avg（n）

9、，然后将这n个平均值组成的数组求，即该样本的t0间隔平滑方差。3、 t0的取值为：10ms，20ms，50ms，100ms，200ms，500ms，1s，2s，5s，10s，20s，50s，100s，等等，就得到一系列的t0间隔平滑方差。4、 以t0为横坐标，为纵坐标，画双对数坐标的函数曲线5、 所绘制的曲线应采用逻辑坐标系，保证双对数曲线的所见即所得。6、 支持打印、打印预览。三、旅行商（TSP）问题1、设计TSP问题的算法模型。2、建立VC+程序框架。3、根据指定的城市规模（数量），自动生成城市模型，并图形化显示，城市之间的距离可以采用正态随机分布。4、动态显示求解过程。5、支持暂停功和继

10、续的功能（在求解过程中中可以暂停，并继续）。6、停止后，可以将当前的状态保存（城市模型、求解状态）。7、可以从7中保存的文件中读出某个状态，并继续求解。四、残缺棋盘问题残缺棋盘（defective chessboard）是一个有2k2k个方格的棋盘，其中恰有一个方格残缺。图4-1给出k2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k=0时，仅存在一种可能的残缺棋盘（如图4-1a所示）。事实上，对于任意k，恰好存在22k种不同的残缺棋盘。残缺棋盘的问题是：要求用三格板（triominoes）覆盖残缺棋盘（如图4-2所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆

11、盖其他所有的方格。在这种限制条件下，所需要的三格板总数为(22k-1)/3。可以验证(22k-1)/3是一个整数。k为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k=1时，正好存在3个非残缺的方格，并且这三个方格可用图4-2中的某一方向的三格板来覆盖。解决的思想：用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k2k残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k2k棋盘一个很自然的划分方法就是将它划分为如图4-3a所示的4个2k-12k-1棋盘。注意到当完成这种划分后，4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k2k棋盘仅仅有一个残缺

12、方格）。首先覆盖其中包含残缺方格的2k-12k-1残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图4-3b所示，其中原2k2k棋盘中的残缺方格落入左上角的2k-12k-1棋盘。可以采用这种分割技术递归地覆盖2k2k残缺棋盘。当棋盘的大小减为11时，递归过程终止。此时11的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。图4-1图4-2图4-3作业要求：1、在窗口中画出初始时的残缺棋盘（棋盘的格数可以指定或在某个范围内随机生成，残缺格的位置随机生成）。2、自动进行残缺棋盘的覆盖，覆盖的过程可以通过定时器或多线程的方法，每一次移动的时间间隔

13、可以自定，以人眼观察比较舒服为宜。3、请定义棋盘描述类和三格板描述类。4、支持暂停功和继续的功能（在自动覆盖过程中可以暂停，并继续）。5、暂停后，可以将当前的状态保存。6、可以从5中保存的文件中读出某个状态，并继续覆盖。五、图片浏览器作业要求：1、 程序界面自定义。2、 能够显示Bmp、JPeg、Gif图片3、 支持图片文件的重命名、拷贝、粘贴功能。4、 支持删除功能，删除时有提示。附加要求：支持打印、打印预览功能，并保持图片所见即所得。六、资源浏览器具体要求：其所有功能要求参见Windows下的资源管理器功能。七、画笔程序作业要求：1、 程序界面参考Microsoft画图程序。2、 能够支持

14、画直线、自由连线（随鼠标移动连线）、实体圆形、实体矩形、实体椭圆3、 支持区域选中（通过鼠标拖拽方框选中），并删除选中区域内所画的形状。4、 支持各种笔形画图时的前景和背景色。5、 支持图擦功能，选中图擦时，随着图擦的移动，根据图擦的大小，将图擦经过的区域中的形状相关部分清除。6、 支持打印、打印预览功能，并保持图片所见即所得。支持将所画的内容保存为文件，格式为BMP格式。八、 聊天系统创建一个聊天系统，该系统由服务器程序和客户端程序两部分构成。其简单的工作原理如下图所示。当服务器程序运行时，首先启动一个监听器，负责监听服务器的某个端口，当客户端要进行聊天时，首先要对服务器的特定端口进行连接请

15、求，即客户端试图连接服务器被监听的端口时，服务器的监听器可以选择接受或拒绝连接请求。如果接受客户端的连接请求，则由监听器为客户端分配一个对应的“套接字”对象，这样在服务器和某个客户端之间就建立了一条数据管道，可以聊天了。本聊天室主要采用Socket（套接字）编写，套接字可以支持TCP和UDP协议。图1 聊天室工作原理图图2 聊天室服务器启动界面图3 聊天室服务器主界面聊天客户端状态信息待发送信息区聊天信息图4 聊天室客户端主界面图5 客户端连接服务器主界面除实现上述基本聊天功能外，还要求：（1） 在服务器端可以将客户登陆、退出及在线时间等情况记录并保存。（2） 服务器和客户端都可以将聊天记录保

16、存。（3） 附加功能：可以在客户端和服务器端传送文件。九、 图形化列表编制一个图形化的列表程序，具体要求如下：（1） 以双向链表为数据模型，分别将链表的结点和链表本身定义为两个C+类，类名分别为CNode、CList。（2） 一般结点的图形显示结果如下：（3） 头结点显示如下：（4） 尾结点显示如下：（5） 当前结点显示如下：（6） 整个链表显示结构如下：（7） 链表应完成下列操作：i. 插入、追加、删除结点ii. 选中某结点成为当前结点iii. 结点可以拖拽iv. 链表双向遍历v. 通过对话框修改某结点的数据域（8） 程序结果要求：i. 采用MDI方式ii. 对链表的操作通过菜单完成iii. 结点和链表的串行化处理iv. 多视图更新十、其他自选题目作业题目也可以自选，但必须符合作业总体要求中的所有要求，而且：a) 必须结合具体的专业内容（小游戏、播放器等不能作为作业内容）。b) 难度与工作量必须达到或超过上述给定题目。c) 必须独立完成。