算法分析实践环节习题集-2016.docx

1、信息工程学院算法分析实践环节习题集 -2016 年 序号 项目名称 任务描述 设计要求 指导教师 人数 1 搜索图中 最小控制顶点集合 给定一个无向连通子图 G=(V, E)，其中 V 表示图中顶点集合， E 表示边的集合。 G 的最小控制顶点集合为 V 的一个子集， S；假设集合 R 表示 V 排除集合 S 后剩余顶点集合，即 ,= V； 则最小控制顶点集合 S 满足约束条件 : R 中任意一个顶点至少与 S 的一个顶点直接相连。 例如下图中红色顶点集合 MDset 表示一个最小控制顶点集合，任意一个绿色的顶点至少与一个红色顶点直接相连。 读取文件 (网络 )，设计算法求解最小控制顶点集合。

2、文件中数据格式如下： A B B C C D B D 每一行表示图的两个顶点，且两个顶点之间有一条边。算法： Input：图文件 Output:最小控制顶点集合 刘全中 1 2 求解最大的双边聚类的子矩阵 给定一个 n 行 m 列的矩阵 E， 单元格中数值 1 或者 0，例如下图 12 行 12 列的矩阵中，灰色单元格表示 1，白色单元格表示 0。矩阵中一个双边聚类子矩阵 (G, C), ,，满足以下条件： (1) 矩阵 (G, C)的每个单元格中值都为 1 (2) 不存在另一个子矩阵 (G, C), , 满足下面两个条件： (a) (G, C)中的每一个单元格值都为 1 (b) 例如：下图左

3、边的矩阵中其中 2 个双边聚类矩阵分别为 (1,3,1,3)， (1,8,2,3,4) 算法输入： 存放矩阵的文件，例如图所示的文件为： 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0

4、 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 输出所有的双边聚类矩阵 刘全中 1 3 图聚类的贪心算法实现 一 个子图 G = (v, E)的内聚性定义如下： ，其中表示子图 G 中边的权重之和， 表示子图 G 与周 围顶点连接边的权重之和。注：如果图是无权图，边的权重设置为 1. 例如：如下图中，假设子图 G 表示包含 A, B, D,E 四个顶点， G = (A, B, D, E)，则， = 5. 则 f(G) = 10/(10+5). 如果一个子图 G 满足内聚性最大时，即局部最优时，则这个子图 G 就是一个聚类。寻找内

5、聚行最大的子图，用贪心算法，分以下三个步骤： (1) 对于 G 的每一个直接邻居顶点 (外围的直接邻居 )，例如 G=A,B,D,E，则 G 的直接邻居顶点为 C, F, G. 找到具有最大值 的顶点 ,如果 ,则 . (2) 对于 G 的每一个内部顶点 ，找到具有最大值的 ,其中 表示集合 G 排除顶点 后的集合；，则 . 算法输入： 存放图的文件，例如图的文件格式如下： A B B C C D B D 每一行表示图的两个顶点，且两个顶点之间有一条边 . 算法： (3)重复步骤 1 和 2，直到集合 G 不发生变化，即收敛，算法结束。 Input:图文件 Output:图中所有的内聚性最大的

6、 cluster. 4 最大匹配率算法设计与实现 两个图 A 和 B 之间的匹配率计算公式： ，其中 |A|表示图 A 中顶点个数， 表示图 A 和图 B 共同顶点组成的子图。例如下图中 R1 和P1 的匹配率为： (4*4)/(4*5) = 0.8 . 给定两组子图 R, P, 例如，如下图 R = R1, R2， P=P1, P2, P3, 图中的边上的权值表示两个图之间的匹配率。 R 和 P 之间最大匹配率计算方法如下： 1. 找出一组边，使得 P 和 R 中的每一个顶点最多出现一条边上，而且边的权重累加和最大。 2. 最大匹配率为：第 1 步选择边的权重之和除以 R 中子图的个数 例如

7、 : 下图中最大匹配率为： (0.8+0.75)/2 Input： 两组图 Output：输出最大匹配率 两个图文件格式如下： A B C D E F G H I 每一行表示一个子图 5 图合并算法的设计与实现 给定若干个子图，如果两个子图的重复度大于 等于 0.8，需要合并这两个子图。两个子图 A和 B 重复度计算公式为： , 例如： X=A, B, C, D, E, Y = B, C, D,E,则 = (4*4)/(4*5) = 0.8，则子图 x 和 y 需要合并。 合并算法有两种方法 : 方法一、从文件逐行扫描每一个子图，如果后面的子图于前面的子图重复度超过 0.8，则把这两个子图合并

8、为一个新的子图。 方法二、把每一个子图抽象为一个顶点，如果两个子图的重复度超过 0.8,则把对应的两个顶点连一条边，这样构造一个新的图。然后从新的图中搜索连通子图，每一个连通子图中所有的顶 点进行合并。 Input: 子图文件，文件的格式如下： A B C D E F G H I 每一行表示一个子图 Output，合并后的子图，输出到一个新的文件中。 要求： 用两种方法分别实现，并比较两种方法的时间复杂度 6 简单数据集跳跃显露模式挖掘算法设计与实现 跳跃显露模式是指在样本的一个类别上发生次数为 0，在另外一个类别上发生次数大于等于一个支持度计数阈值 的模式。 例如下表中数据，假定 2 。那么

9、在类别为 1D 上的跳跃显露模式有： ,eb ， , edc 利用 Java 语言或者 C 语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。 刘全中 1 7 简单数据集频繁关闭模式挖掘算法设计与实现 频繁模式是指在数据集中，出现的次数大于等于给定阈值 的项集。如下表所示的数据集，假设 2 。频繁模式： a ， b ， c , ., , mfca 等 对于模式 p ，如果不存在模式 p , pp . 使得包含 p 的事物和包含 p 的事物相同。那么p 就是一个关闭频繁模式。 利用 Java 语言或者 C 语言实现给定数据集、给定支持度阈值的所有的频繁关闭 刘全中 1 例如，假设 2 ， ,

10、 mfca 就是一个关闭频繁模式。 8 工作分配问题 设有 n 件工作分配给 n 个人。将工作 i 分配给第 j 个人所需的费用为 cij 。试设计一个算法，为每一个人都分配 1 件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小 。 刘全中 1 9 无分隔符字典问题 设 )( ,.,2,1 k 是 n 个 互 不 相 同 的 符 号 组 成 的 符 号 集 。1,| , . . . ,2,1 kiL ikk 是 中字符组成的长度为 k 的字符串全体。 kLS 是 kL 的 1 个无分隔符字典是指对任意 Saaa k., 21 和 Sbb

11、 k.,b 21 ，则 设计一个算法，对于给定的正整数 n 和 k,编程计算 kL 的最大无分隔符字典 数据输入：有文件 input.txt 给出输入数据。文件第 1 行有 2 个正整数 n 和 k 结果输出： 刘全中 1 S.bbba, . . . ,b. . . baa,b. . . aaa 1-k21k21431k32 无分隔符字典问题要求对给定的 n 和 以及正整数 k,编程计算 kL 的最大无分隔符字典。 将计算出的 kL 的最大无分隔符字典的元素个数输出到文件output.txt. 输入文件示例： 2 2 输出： 2. 10 最少个数运算符求解算法的设计与实现 关于整数的二元运算

12、#定义为 (X # Y) = 十进制整数 X 的各位数字之和 * 十进制整数 Y 的最大数字 +Y 的最小数字 例如， (9 # 30)=9*3+0=27. 对于给定的十进制 X 和 K,由 X 和 #运算可以组成各种不同的表达式 .试设计一个算法，计算由 X 和 #运算组成的值为 k 的表达式最少需要用多少个 #预算。 利用 Java 实现所要求的算法，开发一个 GUI 界面，接受两个数据 X 和 K, 然后在界面上输出需要 #的个数。 刘全中 1 11 放行路线选择算法的设计与实现 设有 n 个城市 (或者景点 ),今从某市出发遍历各城市，使之旅费最少 (即找出一条旅费最小的路径 ) 输入

13、：各城市间的旅费表有输入文件提供 输出：旅费最少的一条路径及总费用。 利用 Java, C 实现所要求的算法。 时间充分，设计一个图形化界面，读入文件后把 N 个城市的带权 (花费 )显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上 刘全中 1 12 N 色方柱问题 设有 n 个立方体，每个立方体的每一面用红、黄、蓝、绿等 n 种颜色之一染色。要把这 n个立方体叠成一个方形柱体，使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。试设计一个回溯算法，计 算出 n 个立方体的一种满足要求的叠置方案。 编程任务： 对于给定的 n 个立方体以及每个立方体各面的颜色，计算出 n 个立方

14、体的一种叠置方案，使得柱体的 4 个侧面的每一侧均有 n 中不同的颜色。 数据输入： 由文件 input.txt 给出输入数据。第 1 行有 1 个正整数 n， 0n27,表示给定的立方体个数和颜色均为 n。第 2 行是 n 个大写英文字母组成的字符串。该字符串的第 k nk0 个字符代表第 k 种颜色。接下来的 n 行中，每行有 6 个数，表示立方体各面的颜色。立方体各面的编号如图 1 所示： T L F R B D 刘全中 1 5 0 2 1 3 4 图 1 图 1 中 F 表示前面， B 表示背面， L 表示左面， R 表示右面， T 表示顶面， D 表示底面。相应地， 2 表示前面，

15、3 表示背面， 0 表示侧面， 1 表示右面， 5 表示顶面， 4 表示底面。 例如，在示例输出文件中，第 3 行的 6 个数 0, 2 , 1, 3, 0, 0 分别表示第 1 个立方体的左面的颜色为 R，右面的颜色为，前面的颜色为，背面的颜色为，底面的颜色为，顶面的颜色为 结果输出：将计算的个立方体的一种可行的叠置方案输出到文件 output.txt。每行 6 个字符，表示立方体个面的颜色。如果不存在所要求的叠置方案，输出“ No Solution” 输入文件示例 输出文件示例 Input.txt output.txt 4 RBGYRR RGBY YRBGRG 0 2 1 3 0 0 BG

16、RBGY 3 0 2 1 0 1 GYYRBB 2 1 0 2 1 3 1 3 3 0 2 2 13 猜比赛名次问题的求解算法设计与实现 五个学生 A、 B、 C、 D、 E 参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为 A、 B、 C、 D、 E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如与，或者与等）。 乙猜的名次顺序为 D、 A、 E、 C、 B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？ 利用穷举法，设计算法对以上问题求解。 利用 Java或者 C 对所描述任务进行求解。 刘全中 1 14 计算合数问题的求解 一个整数 n（ n=100）可以有多种划分，使其分划得一列整数之和为 n.例如： 输入 :n=4 输出文件 result.out，格式内容为： 4 3 1 2 2 要求输入一个整数 n，把划分序列输出到文件中。 刘全中 1