面向对象作业要求.docx

面向对象作业要求.docx

《面向对象作业要求.docx》由会员分享，可在线阅读，更多相关《面向对象作业要求.docx（15页珍藏版）》请在冰点文库上搜索。

面向对象作业要求

面向对象编程技术作业题

要求与说明：

●作业成绩总分40分，各题目如无特别声明，起评分均为30分，在此基础上根据实际完成情况、设计文档情况、特色等方面浮动，满分40分；自选题目起评分根据题目难易具体确定；

●所有作业要求使用Visualstudio（各个版本）编程工具实现；

●所有题目都要求具有完整的图形用户界面、输入/出接口，功能要完备；

●题目涉及的算法实现方法不限（同一个问题可以使用不同的算法实现）；

●要求撰写设计报告（内容包括：

问题分析、算法选择、方案设计、编程实现），设计报告以Word文档形式与作业程序源代码压缩到一起提交；

●任何上交的作业（包括：

设计报告、程序源代码）仅作为作业看待，不承担任何版权问题，而且必须是独立完成；

●提交作业时，请将程序目录下的debug和release目录及其下所有内容删除，并统一用WinRAR压缩，压缩文件名的命名格式：

学号－姓名-所在院系名称

例如：

2090001-姓名-学院

命名不规范将在起评分基础上扣2分！

！

！

●作业要求在本课程结束一周内上交，即在2011年12月9日前必须提交作业，提交地址如下：

h_lionstar@或

hlionstar@

一、开关盒布线问题（35分起）

开关盒布线问题是这样的：

给定一个矩形布线区域，其外围有若干针脚。

两个针脚之间通过布设一条金属线路而实现互连。

这条线路被称为电线，被限制在矩形区域内。

如果两条电线发生交叉，则会发生电流短路。

所以，不允许电线间的交叉。

每对互连的针脚被称为网组。

我们的目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。

图1-1a给出了一个布线的例子，其中有八个针脚和四个网组。

四个网组分别是（1,4），（2,3），（5,6）和（7,8）。

图1-1b给出的布线方案有交叉现象发生（（1,4）和（2,3）之间），而图1-1c则没有交叉现象发生。

由于四个网组可以通过合理安排而不发生交叉，因此可称其为可布线开关盒（routableswitchbox）。

（在具体实现时，还需要在两个相邻的电线间留出一定的间隔。

我们要解决的问题是，给定一个开关盒布线实例，确定它是不是一个可布线的。

图1－1

图1-1b和1-1c中的电线都是由平行于x轴和y轴的垂直线段构成的，当然也可以使用不与x轴和y轴平行的线段。

解决的思想：

为了解决开关盒布线问题，我们注意到，当两个针脚互连时，其电线把布线区分成两个分区。

例如，当（1,4）互连时，就得到了两个分区，一个分区包含针脚2和3，另一个分区包含针脚5-8。

现在如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。

如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。

为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之中（即不会出现两个针脚分别

位于两个子分区的情形），那么这个分区就是可布线的。

为了实现上述策略，可以按顺时针或反时针方向沿着开关盒的外围进行遍历，可从任意一个针脚开始。

例如，如果按顺时针方向从针脚1开始遍历图3-1a中的针脚，那么将依次检查针脚1,2,...,8。

针脚1和4属于同一个网组，那么在针脚1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚4至针脚1之间出现的所有针脚构成了第二个分区。

把针脚1放入堆栈，然后继续处理，直至遇到针脚4。

这个过程使我们仅在处理完一个分区之后才能进入下一个分区。

下一个针脚是针脚2，它与针脚3同属一个网组，它们又把当前分区分成两个子分区。

与前面的做法一样，把针脚2放入堆栈，然后继续处理直至遇到针脚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时，它也被放入堆栈。

尽管已经遇到了针脚1和针脚5，但还不能结束由这两个针脚所定义的第一个分区的处理过程，因为针脚4的布线将不得不跨越这个分区的边界。

因此，当完成对所有针脚的检查时，堆栈不会变空。

作业要求：

1、画出给定矩形布线区域（包括需要连同的线网组），针脚和线网组在数据库中存放，通过数据库接口读出。

2、在自动布线的每一步，用图形标示其状态。

3、自动布线的过程可以通过定时器或多线程的方法，每一次布线的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的布线过程如能实现动画最好。

4、如需要，请定义相关的描述类。

5、在程序中，请使用对话框设定需要的各种参数。

6、布线完成后，请将结果存入数据库中。

7、统计算法耗时。

二、数据阿伦方差计算显示问题

在科学研究实验中，经常遇到对大量的实验数据的处理问题。

其处理方法有很多种，但其基本的处理一般包括：

求均值、方差等。

今假设有一检测量，其实验测量值服从正态概率密度分布，分布范围：

，分布概率100%，其中

是其数学期望，

是该测量样本的方差，样本基本采样频率为10ms。

作业要求：

1、根据概率分布函数生成一个不少于20000个采样值的样本，其均值和方差通过程序界面指定。

如有类似的实际检测数据样本，也可以使用实际样本。

2、对该采样样本，根据给定的时间间隔t0，对样本数据分段，总共（T÷t0）＝n段，T为整个样本对应的采样时间。

每一段内的数据求平均，得到n个平均值avg（n），然后将这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、支持暂停功和继续的功能（在求解过程中中可以暂停，并继续）。

6、停止后，可以将当前的状态保存（城市模型、求解状态）。

7、可以从7中保存的文件中读出某个状态，并继续求解。

四、残缺棋盘问题

残缺棋盘（defectivechessboard）是一个有2k×2k个方格的棋盘，其中恰有一个方格残缺。

图4-1给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

注意当k=0时，仅存在一种可能的残缺棋盘（如图4-1a所示）。

事实上，对于任意k，恰好存在22k种不同的残缺棋盘。

残缺棋盘的问题是：

要求用三格板（triominoes）覆盖残缺棋盘（如图4-2所示）。

在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。

在这种限制条件下，所需要的三格板总数为（22k-1）/3。

可以验证（22k-1）/3是一个整数。

k为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。

当k=1时，正好存在3个非残缺的方格，并且这三个方格可用图4-2中的某一方向的三格板来覆盖。

解决的思想：

用分而治之方法可以很好地解决残缺棋盘问题。

这一方法可将覆盖2k×2k残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。

2k×2k棋盘一个很自然的划分方法就是将它划分为如图4-3a所示的4个2k-1×2k-1棋盘。

注意到当完成这种划分后，4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k×2k棋盘仅仅有一个残缺方格）。

首先覆盖其中包含残缺方格的2k-1×2k-1残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图4-3b所示，其中原2k×2k棋盘中的残缺方格落入左上角的2k-1×2k-1棋盘。

可以采用这种分割技术递归地覆盖2k×2k残缺棋盘。

当棋盘的大小减为1×1时，递归过程终止。

此时1×1的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。

图4-1

图4-2

图4-3

作业要求：

1、在窗口中画出初始时的残缺棋盘（棋盘的格数可以指定或在某个范围内随机生成，残缺格的位置随机生成）。

2、自动进行残缺棋盘的覆盖，覆盖的过程可以通过定时器或多线程的方法，每一次移动的时间间隔可以自定，以人眼观察比较舒服为宜。

3、请定义棋盘描述类和三格板描述类。

4、支持暂停功和继续的功能（在自动覆盖过程中可以暂停，并继续）。

5、暂停后，可以将当前的状态保存。

6、可以从5中保存的文件中读出某个状态，并继续覆盖。

五、图片浏览器

作业要求：

1、程序界面自定义。

2、能够显示Bmp、JPeg、Gif图片

3、支持图片文件的重命名、拷贝、粘贴功能。

4、支持删除功能，删除时有提示。

附加要求：

支持打印、打印预览功能，并保持图片所见即所得。

六、资源浏览器

具体要求：

其所有功能要求参见Windows下的资源管理器功能。

七、画笔程序

作业要求：

1、程序界面参考Microsoft画图程序。

2、能够支持画直线、自由连线（随鼠标移动连线）、实体圆形、实体矩形、实体椭圆

3、支持区域选中（通过鼠标拖拽方框选中），并删除选中区域内所画的形状。

4、支持各种笔形画图时的前景和背景色。

5、支持图擦功能，选中图擦时，随着图擦的移动，根据图擦的大小，将图擦经过的区域中的形状相关部分清除。

6、支持打印、打印预览功能，并保持图片所见即所得。

支持将所画的内容保存为文件，格式为BMP格式。

八、聊天系统

创建一个聊天系统，该系统由服务器程序和客户端程序两部分构成。

其简单的工作原理如下图所示。

当服务器程序运行时，首先启动一个监听器，负责监听服务器的某个端口，当客户端要进行聊天时，首先要对服务器的特定端口进行连接请求，即客户端试图连接服务器被监听的端口时，服务器的监听器可以选择接受或拒绝连接请求。

如果接受客户端的连接请求，则由监听器为客户端分配一个对应的“套接字”对象，这样在服务器和某个客户端之间就建立了一条数据管道，可以聊天了。

本聊天室主要采用Socket（套接字）编写，套接字可以支持TCP和UDP协议。

图1聊天室工作原理图

图2聊天室服务器启动界面

图3聊天室服务器主界面

聊天客户端状态信息

待发送信息区

聊天信息

图4聊天室客户端主界面

图5客户端连接服务器主界面

除实现上述基本聊天功能外，还要求：

（1）在服务器端可以将客户登陆、退出及在线时间等情况记录并保存。

（2）服务器和客户端都可以将聊天记录保存。

（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）必须独立完成。