程序与算法综合设计课程设计指导书-2013(4)

层次三：附加要求

能够图形显示求解过程。

题13：最大匹配问题：

问题描述：

写出求一个二分图的最大匹配的算法，并用于解决下面的问题。 第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出 的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

编程任务：

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案， 使皇家空军一次能派出最多的飞机。

数据输入：

由文件input.txt提供输入数据。文件第1 行有2 个正整数m和n。n是皇家空军的飞行员总数(n<100)；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n。 接下来每行有2 个正整数i和j，表示外籍飞行员i可以和英国飞行员j配合。文件最后以2 个-1 结束。

结果输出：

程序运行结束时，将最佳飞行员配对方案输出到文件output.txt 中。第1 行是最佳飞行员配对方案一次能派出的最多的飞机数M。接下来M 行是最佳飞行员配对方案。每行有2个正整数i和j，表示在最佳飞行员配对方案中，飞行员i和飞行员j 配对。

如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入文件示例： input.txt 5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8

5 10 -1 -1

输出文件示例： output.txt 4 1 7 2 9 3 8 5 10

题14：最佳匹配问题：(80)

问题描述：

羽毛球队有男女运动员各n人。给定2 个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

编程任务：

设计一个优先队列式分支限界法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

数据输入：

第一行有1 个正整数n (1≤n≤20)。接下来的2n行，每行n个数。前n行是p，后n行是q。

结果输出：

将计算出的男女双方竞赛优势的总和的最大值输出。

样例输入： 3 10 2 3 2 3 4 3 4 5 2 2 2 3 5 3 4 5 1

样例输出：52

课题15：（75分）设计程序以实现构造哈夫曼树的哈夫曼算法，要求如下： （1）可以使用实验工具的有关功能。 （2）要能演示构造过程。

（3）求解出所构造的哈夫曼树的带权路径长度。

课题16：（85分）采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。

要求：

（1）描述压缩基本符号的选择方法。

（2）运行时的压缩原文件的规模应不小于5K。 （3）提供恢复文件与原文件的相同性对比功能。

课题18：（75分）给出一组实验来比较下列排序算法的时间性能：

快速排序、堆排序、希尔排序、冒泡排序、归并排序（其它排序也可以作为比较的对象）

要求：

（1）时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 （2）实验数据应具有说服力，包括：

规模范围要大（如从100到10000）

数据的初始特性类型要多，因而需要具有随机性；

实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。 实验结果要能以清晰的形式给出，如图、表等。

（3）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 （4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 （5）要给出实验的方案及其分析。

课题19：（85分）设计一个模拟电梯工作过程的图形演示系统。要求所设计的电梯能符合市场上大多数系统的要求。

设计概要：几部电梯；相应优先级及规则确定；

课题20：（95分）决策树构造算法的实现

(1) 简介：决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得

到什么值的类似规则的方法。它是一个从上到下、分而治之的归纳过程，是决策树的一个经典的构造算法。应用于很多预测的领域，如通过对信用卡客户数据构建分类模型，可预测下一个客户他是否属于优质客户。

(2) 分类过程：分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。数据分类是

一个两步过程。第一步，使用已知类别标记的训练数据集建立一个分类模型。例如：图1是一个决策树模型。第二步，对未知标记的数据使用模型进行分类。例如，根据图1的决策树模型，运用自顶而下的属性测试过程，将表2中的样例1-6分别分类为“Y”、“Y”、“Y”、“Y”、“N”、“N”。

天况

晴 湿度

多云

Y

雨

风况

大 N

正常

Y

有 N

无

Y

图1. 一个决策树模型的例子

(3) 算法描述：

输入：训练样例集S，未标记的节点T，属性集A 输出：以T为根的决策树

① 如果S中所有样例都是正例，则标记节点T为“Y”，并结束； ② 如果S中所有样例都是反例，则标记节点T为“N”，并结束； ③ 否则，从A中选择一个属性X，(可随机选)标记节点T为X;

④ 设X的所有取值为V1, V2,?,Vn，依据这些取值将S划分为n个子集 S1, S2, ?, Sn，建T的n个孩子节点Ti，并分别以Vi作为从T到Ti的分支标号; ⑤ 对每对（Si，Ti，A-{X}），递归调用ID3算法建立一棵以Ti为根的子树； END

(4) 举例：对下表运用算法构建决策树

表1. 一个训练数据集 编号 天况 1 2 3 4 5 6 7 8 9 10 11 12 13 14 晴 晴 多云 雨 雨 雨 多云 晴 晴 雨 晴 多云 多云 雨 温度 热 热 热 中 冷 冷 冷 中 冷 中 中 中 热 中 湿度 风况 大 大 大 大 正常 正常 正常 大 正常 正常 正常 大 正常 大 无 有 无 无 无 有 有 无 无 无 有 有 无 有 分类 N N Y Y Y N Y N Y Y Y Y Y N 对下列样例输入使用构建的决策树模型预测其分类属性： 表2. 一个待分类的数据集 编号 天况 1 2 3 晴 晴 雨 温度 热 热 热 湿度 风况 正常 正常 正常 无 有 无 分类 ？ ？ ？ 4 5 6 晴 晴 晴 中 冷 冷 正常 大 大 无 有 无 ？ ？ ？ (5) 要求：①设计合理的数据结构，编程实现决策树构造算法；②给定训练数据集，运用构

建的决策树模型，设计合理的文件格式，保存于外存之中；③设计决策树分类算法，根据保存在外存的决策树模型，实现决策树的分类过程，完成对未知类别属性数据样例的分类。

课题21：（95分） 关联规则求解算法Apriori的实现

简介：关联分析是数据挖掘中的一个重要任务，Apriori算法是一种典型的关联分析算法。多用于超市的销售决策，如通过统计一段时间内，用户买商品A和B同时发生的概率，得出了顾客买A则很可能会买B的一条规则。

本课题要求对给定的训练数据，实现Apriori算法，构件关联规则集合。 Apriori算法描述如下：

输入：训练样例集S，属性集A，支持度阈值minsup，置信度阈值minconf 输出：关联规则集 （1）令 k=1

（2）生成长度为1的频繁项集

（3）重复以下操作直到不在生成新的频繁项集

（a）剪除一些候选项集，它们包含非频繁的长度为K子集 （b）从长度为k的频繁项集中生成长度为k+1的候选项集 （c）通过扫描数据库，计算每个候选项集的支持度

（d）除去那些非频繁的候选项集，只留下那些频繁的候选项集 END 示例：

基本概念表：关联规则的简单例子 TID 网球拍 网 球 运动鞋 羽毛球 1 2 3 4 5 6

1 1 1 1 0 1

1 1 0 0 1 1

1 0 0 1 1 0

0 0 0 0 1 0

用一个简单的例子说明。表1是顾客购买记录的数据库D，包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则（频繁二项集）：网球拍与网球，事务1,2,3,4,6包含网球拍，事务1,2,6同时包含网球拍和网球，支持度(X^Y)/D=0.5，置信度(X^Y)/X=0.6。若给定最小支持度α = 0.5，最小置信度β = 0.6，认为购买网球拍和购买网球之间存在关联。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库程序与算法综合设计课程设计指导书-2013(4)在线全文阅读。