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