算法分析解析实践环节习题集.doc

《算法分析解析实践环节习题集.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息工程学院算法分析实践环节习题集（2011年）序号项目名称任务描述设计要求指导教师人数1．11．二进制位串的压缩树算法设计与实现第一步输入：二进制位串，例如：0000010000001111输出：如下图1所示的二进制压缩树第二步输入：二进制压缩树，如图1输出：二进制路径码数组如图2第三步：输入两个路径码数组，如图2，图3输出：相与后的路径码数组，如图4两个路径码数组相与就是求子码的过程，对于两个路径码x,y，如果x是y的前缀，那么y是x的子码，比如：0是0101的前缀，因此0101是0的子码。所以图2和图3相与后的路径码数组是图4.用Java语言，或者C语言，推

2、荐用Java语言。要求：读文件，读取文件中所有的项，得到二进制串，然后构造每个项的二进制串的压缩树，并得到每个项的路径码。刘全中1图1图2图3图41．1．简单数据集跳跃显露模式挖掘算法设计与实现跳跃显露模式是指在样本的一个类别上发生次数为0，在另外一个类别上发生次数大于等于一个支持度计数阈值的模式。例如下表中数据，假定。那么在类别为上的跳跃显露模式有：，利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。刘全中12．简单数据集频繁关闭模式挖掘算法设计与实现频繁模式是指在数据集中，出现的次数大于等于给定阈值的项集。如下表所示的数据集，假设。频

3、繁模式：，，,……..,等对于模式，如果不存在模式,.使得包含的事物和包含利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有的频繁关闭刘全中1的事物相同。那么就是一个关闭频繁模式。例如，假设，就是一个关闭频繁模式。1．利用分治思想设计循环赛日程表假设有n=2k个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：(1).每个选手必须与其他n-1个选手各赛一次(2).每个选手一天只能赛一次(3).循环赛一共进行n-1天利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。刘全中11．工

4、作分配问题设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。刘全中12．无分隔符字典问题设是n个互不相同的符号组成的符号集。是中字符组成的长度为k的字符串全体。是的1个无分隔符字典是指对任意和，则无分隔符字典问题要求对给定的n和以及正整数k,编程计算的最大无分隔符字典。设计一个算法，对于给定的正整数n和k,编程计算的最大无分隔符字典数据输入：有文件input.txt给出输入数据。文件第1行有2个正整数n

5、和k结果输出：将计算出的的最大无分隔符字典的元素个数输出到文件output.txt.输入文件示例：22输出：2.刘全中11．2．放行路线选择算法的设计与实现设有n个城市(或者景点),今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最小的路径)输入：各城市间的旅费表有输入文件提供输出：旅费最少的一条路径及总费用。利用Java,C实现所要求的算法。时间充分，设计一个图形化界面，读入文件后把N个城市的带权(花费)显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上刘全中13．N色方柱问题设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染色。

6、要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜色。试设计一个回溯算法，计算出n个立方体的一种满足要求的叠置方案。编程任务：对于给定的n个立方体以及每个立方体各面的颜色，计算出n个立方体的一种叠置方案，使得柱体的4个侧面的每一侧均有n中不同的颜色。数据输入：刘全中1由文件input.txt给出输入数据。第1行有1个正整数n，0

7、02134图1图1中F表示前面，B表示背面，L表示左面，R表示右面，T表示顶面，D表示底面。相应地，2表示前面，3表示背面，0表示侧面，1表示右面，5表示顶面，4表示底面。例如，在示例输出文件中，第3行的6个数0,2,1,3,0,0分别表示第1个立方体的左面的颜色为R，右面的颜色为Ｂ，前面的颜色为Ｇ，背面的颜色为Ｙ，底面的颜色为Ｒ，顶面的颜色为Ｒ．结果输出：将计算的ｎ个立方体的一种可行的叠置方案输出到文件output.txt。每行6个字符，表示立方体个面的颜色。如果不存在所要求的叠置方案，输出“NoSolution”输入文件示例输出文件示例Input.txtout

8、put.t