《算法分析实践环节习题集.doc》由会员分享，可在线阅读，更多相关《算法分析实践环节习题集.doc（61页珍藏版）》请在金锄头文库上搜索。
1、信息工程学院算法分析实践环节习题集（2011年）序号项目名称任务描述设计要求指导教师人数112二进制位串的压缩树算法设计与实现第一步输入：二进制位串，例如：0000010000001111输出：如下图1所示的二进制压缩树第二步输入：二进制压缩树，如图1输出：二进制路径码数组 如图2第三步：输入两个路径码数组， 如图2，图3输出：相与后的路径码数组，如图4两个路径码数组相与就是求子码的过程，对于两个路径码x,y， 如果x是y的前缀，那么y是x的子码，比如：0是0101的前缀，因此0101是0的子码。所以图2和图3相与后的路径码数组是图4.图1图2图3图4用Java语言，或者C语言，推荐用Java
2、语言。要求：读文件，读取文件中所有的项，得到二进制串，然后构造每个项的二进制串的压缩树，并得到每个项的路径码。 刘全中134简单数据集跳跃显露模式挖掘算法设计与实现跳跃显露模式是指在样本的一个类别上发生次数为0，在另外一个类别上发生次数大于等于一个支持度计数阈值的模式。例如下表中数据，假定。那么在类别为上的跳跃显露模式有：，利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。刘全中15简单数据集频繁关闭模式挖掘算法设计与实现频繁模式是指在数据集中，出现的次数大于等于给定阈值的项集。如下表所示的数据集，假设。频繁模式：，, ., 等对于模式，如果不存在模式,. 使得包含的
3、事物和包含的事物相同。那么就是一个关闭频繁模式。例如，假设，就是一个关闭频繁模式。利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有的频繁关闭刘全中16利用分治思想设计循环赛日程表假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：(1). 每个选手必须与其他n-1个选手各赛一次(2). 每个选手一天只能赛一次(3). 循环赛一共进行n-1天利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。刘全中17工作分配问题设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算
4、法，为每一个人都分配1件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。刘全中18无分隔符字典问题设 是n个互不相同的符号组成的符号集。是中字符组成的长度为k的字符串全体。是的1个无分隔符字典是指对任意和，则无分隔符字典问题要求对给定的n和以及正整数k,编程计算的最大无分隔符字典。 设计一个算法，对于给定的正整数n和k,编程计算的最大无分隔符字典数据输入：有文件input.txt给出输入数据。文件第1行有2个正整数n和k结果输出：将计算出的的最大无分隔符字典的元素个数输出到文件output.txt.输入文件示例：2 2输出：2.刘全中1
5、910放行路线选择算法的设计与实现设有n个城市(或者景点),今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最小的路径)输入：各城市间的旅费表有输入文件提供输出：旅费最少的一条路径及总费用。利用Java, C实现所要求的算法。时间充分，设计一个图形化界面，读入文件后把N个城市的带权(花费)显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上刘全中111N色方柱问题设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染色。要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜色。试设计一个回溯算法，计算出n个立方体的一种满足要求的叠置方案。编程任务
6、：对于给定的n个立方体以及每个立方体各面的颜色，计算出n个立方体的一种叠置方案，使得柱体的4个侧面的每一侧均有n中不同的颜色。数据输入：由文件input.txt给出输入数据。第1行有1个正整数n，0n27,表示给定的立方体个数和颜色均为n。第2行是n个大写英文字母组成的字符串。该字符串的第k个字符代表第k种颜色。接下来的n行中，每行有6个数，表示立方体各面的颜色。立方体各面的编号如图1所示：TLFRB D 502134 图1图1中F表示前面，B表示背面，L表示左面，R表示右面，T表示顶面，D表示底面。相应地，2表示前面，3表示背面，0表示侧面，1表示右面，5表示顶面，4表示底面。例如，在示例输
7、出文件中，第3行的6个数0, 2 , 1, 3, 0, 0分别表示第1个立方体的左面的颜色为R，右面的颜色为，前面的颜色为，背面的颜色为，底面的颜色为，顶面的颜色为结果输出：将计算的个立方体的一种可行的叠置方案输出到文件output.txt。每行6个字符，表示立方体个面的颜色。如果不存在所要求的叠置方案，输出“No Solution”输入文件示例 输出文件示例Input.txt output.txt4 RBGYRRRGBY YRBGRG0 2 1 3 0 0 BGRBGY3 0 2 1 0 1 GYYRBB2 1 0 2 1 31 3 3 0 2 2刘全中112N个自然数中r个数组合求解设计与
8、实现找出n个自然数(1,2,3,n)中r个数的组合。输入n,和r,输出所有的组合数。n个数中r的组合，其中每r个数中，数不能相同。另外，任何两组组合的数，所包含的数也不应相同。例如：当n=5,r=3时，所有组合为：5 4 3 ； 5 4 2 ； 5 4 15 3 2 ； 4 3 2 ； 4 2 13 2 1； total=10；分别用穷举搜索法、递归法、回溯法实现所要求的功能，并比较三者的时间复杂度刘全中113猜比赛名次问题的求解算法设计与实现五个学生A、B、C、D、E 参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任
9、何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如与，或者与等）。乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？利用穷举法，设计算法对以上问题求解。 利用Java或者C 对所描述任务进行求解。刘全中114计算合数问题的求解一个整数n（n=100）可以有多种划分，使其分划得一列整数之和为n.例如：输入:n=4输出文件result.out，格式内容为：43 12 22 1 11 1 1 1要求输入一个整数n，把划分序列输出到文件中。刘全中115查找数字对问题求解算法的设计与实现输入N（2=N=100）个数字(在0到9之
10、间),然后统计出这组数中相邻两数字组成的链环数字对出现的次数。输入:N=200 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9输出：(7,8)=2 （8,7）=3指(7,8)、(8,7)数字对出现次数分别是2次、3次设计一个GUI界面，能够接受用户的输入，也能够从文件中读取数据。在界面上输出所要求的结果，并把结果存储到文件中刘全中116无向图最小代价生成树算法的实现（1） 掌握最小代价生成树算法思想。（kruskal算法），并利用贪心的思想改进该算法，降低其时间复杂性。（2） 设计一个有10个顶点的无向图，并用随机数产生其各边的代价。（3） 利用最小代价生成树算法思
11、想，对其所产生的无向图，找出其最小代价生成树。（1） 设计一个界面，显示产生的无向图。（2） 实现最小代价生成树算法。（3） 在输出界面，显示结果。王湘桃117分治法在一个划分成网络的操场上，n名士兵散乱地站在网格点上。网格点由整数坐标（x,y）表示。士兵们可以沿网格边上下左右移动一步，但在同一时刻任意网格点上只能有一名士兵。按照军官的命令，士兵们要整齐的列成一个纵队，及排列成（x,y）,(x+1，y)（x+n-1,y）。如何选择x和y的值才能使士兵们以最小的总移动步数排成一列。设计一个分治算法，输出方案。王湘桃118有向图单源最短路径分支限界算法实现（1）掌握单源最短路径分支限界算法思想。（
12、2）设计一个至少有10个顶点的有向图，并用随机数产生其各边的权值。（3）利用单源最短路径分支限界算法思想，对其所产生的有向图，找出从某源点出发，到其它各顶点的最短路。（1）设计一个界面，显示产生的有向图。（2）实现单源最短路径分支限界算法。（3）在输出界面，显示结果（在有向图中，标记出从源到各顶点的路径）。王湘桃119回溯算法实现部落卫队问题。原始部落中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌，部落酋长为了组织一只保卫部落的队伍，希望从部落的居民中选出最多居民入伍，并保证队伍中任何两个人都不是仇敌。给定该部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。（1）
13、实现回溯法的设计思想。王湘桃120装载问题的分支限界算法实现（1）有一批集装箱共n个，要装上两艘载重量分别为c1和c2的轮船，其中，集装箱i 的重量Wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）用文件导入集装箱的重量，和两艘船的载重量。（2）实现分支限界算法的设计思想。（3）设计一个输出界面，输出装载方案。王湘桃121最大团问题的回溯算法实现（1） 给定无向图G=(V,E)。如果，且对任意有，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含
14、顶点数最多的团。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）设计一个界面，显示产生的无向图。（至少有5个顶点）（2）实现回溯法的设计思想。（3）在输出界面，显示结果。王湘桃122最大团问题的分支限界算法实现（1）给定无向图G=(V,E)。如果，且对任意有，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）设计一个界面，显示产生的无向图。（至少有5个顶点）（2）实现分支限界算法的设计思想。（3）在输出界面，显示结果。王湘桃123最佳调度问题的回溯算法实现（1） 有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。找出完成这n个任务的最佳调度，使得完成
