5 10
-1 -1
输出文件示例： output.txt 4 1 7 2 9 3 8 5 10
题14：最佳匹配问题：
问题描述：
羽毛球队有男女运动员各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 晴 晴 多云 雨 雨 雨 多云 晴 晴 雨 晴 多云 多云 温度 热 热 热 中 冷 冷 冷 中 冷 中 中 中 热 湿度 风况 大 大 大 大 正常 正常 正常 大 正常 正常 正常 大 正常 无 有 无 无 无 有 有 无 无 无 有 有 无 分类 N N Y Y Y N Y N Y Y Y Y Y 雨 中 大 有 14 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，认为购买网球拍和购买网球之间存在关联。
相关推荐：
loading