高分征集MFC例程

总体要求：
 使用Visual C++ 6.0编程工具实现。
 题目必须包含模型设计（数据结构设计、算法设计）等内容。
 所有问题要求图形化显示。
 算法的实现方法不限（同一个问题可以使用不同的算法实现）。
 要求撰写设计报告（问题分析、算法选择、方案设计、编程实现）。
以下任何题目都行一、开关盒布线问题
开关盒布线问题是这样的：给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。我们的目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。图1-1a给出了一个布线的例子，其中有八个针脚和四个网组。四个网组分别是(1,4)，(2,3)，(5,6)和(7,8)。图1-1b给出的布线方案有交叉现象发生（(1,4)和(2,3)之间），而图1-1c则没有交叉现象发生。由于四个网组可以通过合理安排而不发生交叉，因此可称其为可布线开关盒（routable switch box）。（在具体实现时，还需要在两个相邻的电线间留出一定的间隔。我们要解决的问题是，给定一个开关盒布线实例，确定它是不是一个可布线的。
 
图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中保存的文件中读出某个状态，并继续求解。
四、残缺棋盘问题（30分起）
残缺棋盘（defective chessboard）是一个有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中保存的文件中读出某个状态，并继续覆盖。
五、汉诺塔（Towers of Hanoi）问题（30分起）
汉诺塔（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中保存的文件中读出某个状态，并继续移动。
六、图片浏览器（）
要求：
1、 程序界面自定义。
2、 能够显示Bmp、JPeg、Gif图片
3、 支持图片文件的重命名、拷贝、粘贴功能。
4、 支持删除功能，删除时有提示。
附加要求：支持打印、打印预览功能，并保持图片所见即所得。
七、画笔程序（）
要求：
1、 程序界面参考Microsoft画图程序。
2、 能够支持画直线、自由连线（随鼠标移动连线）、实体圆形、实体矩形、实体椭圆
3、 支持区域选中（通过鼠标拖拽方框选中），并删除选中区域内所画的形状。
4、 支持各种笔形画图时的前景和背景色。
5、 支持图擦功能，选中图擦时，随着图擦的移动，根据图擦的大小，将图擦经过的区域中的形状相关部分清除。
6、 支持打印、打印预览功能，并保持图片所见即所得。
7、 支持将所画的内容保存为文件，格式为BMP格式。
八、八数码（九宫）问题
在一个３×３的方格中有１－８这８个数及一个空格随机的摆放在其中的格子里，如下图左边所示。现在要求实现这个问题：将该九宫格调整为如图4－1右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列。
 
图4－1
程序界面自行设计，要求：
1、 初始状态自动产生，但不能是已经排好的状态。
2、 程序支持自动求解和手动拖拽求解。
3、 自动寻解过程显示。
可以将中间结果保存为自定义格式的文件，并再次打开，继续操作。