算法设计与分析课程设计报告

算法与分析课程设计报告题 目： 算法设计和分析 专 业： 网络工程 班 级： 学 号： 11 姓 名： 赫前进 太原工业学院计算机工程系 2012年 11月 24 日第二章 主元素问题一、 算法问题描述主元素问题:设T0.n-1是n个元素的数组。对任一元素x，设S(x)=i|Ti=x。当|S(x)|n/2时，称x为T的主元素。如果T中元素存在序关系，按分治策略设计并实现一个线性时间算法，确定T0.n-1是否有一个主元素。二、 算法问题形式化表示若T 中存在主元素，则将T 分为两部分后，T 的主元素也必为两部分中至少一部分的主元素，因此可用分治法。将元素划分为两部分，递归地检查两部分有无主元素。算法如下：若T 只含一个元素，则此元素就是主元素，返回此数。将T 分为两部分T1 和T2（二者元素个数相等或只差一个），分别递归调用此方法求其主元素m1 和m2。若m1 和m2 都存在且相等，则这个数就是T 的主元素，返回此数。若m1 和m2 都存在且不等，则分别检查这两个数是否为T 的主元素，若有则返回此数，若无则返回空值。若m1 和m2 只有一个存在，则检查这个数是否为T 的主元素，若是则返回此数，若否就返回空值。若m1 和m2 都不存在，则T 无主元素，返回空值。三、 期望输入与输出输入：数组中元素的个数9数组元素0 0 1 1 0 8 1 1 1输出：显示主元素是1。四、 算法分析与步骤描述选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为k。如果kn/2，那么继续用同样的方法在左边部分找；如果k m+1 ， di * (n + 1) = i 横向 i = 0 - n+1, di = I,即：如下图是初始化之后的表格信息，纵向是b,d 横向是a,b,c,d步骤：for(i = 1 - 2) / 2为“bd的长度 for( j = 1 - 4 ) / 4 为”abcd的长度为了确定d i j 的大小， 需要比较a)从d i - 1 j - 1 修改字符srcStri - 1, 使之变为dstStrj - 1, 如果srcStri - 1 = dstStrj - 1 则这一步可以免去b)从d i - 1 j 在srcStr的 i - 1处添加一个字符，使字符srcStr i - 1 变为dstStr j - 1 c)从d i j - 1 在dstStr的 j - 1 处删除一个字符,使字符dstStr j - 1 变为srcStr i - 1,三者之间的最小值赋给d i j 六、 算法运行截图七、 算法复杂度分析从上面算法可以看出，该算法时间复杂性为0(m*n),空间复杂性为O（m*n）。同时可以看出，当对第i行进行填表时，只需要用到第i-1行的数据，因此可以用一个一维数组dis0n代替二维数组D0m,0n，因此空间复杂性降为O(n)。第四章 磁带存储问题一、 算法问题描述设有n个程序1，2，n 要存放在长度为L的磁带上。程序i 存放在磁带上的长度是li ，1=i= n。这n个程序的读取概率分别为p1，p2， pn，且pi=1(i=1,2,.n)。如果将这n个程序按i1，i2， in的次序存放，则读取程序所需的时间tr=cpik lik(k=1,2,.r)（可假定c为1）。这n 个程序的平均读取时间为t(1)+t(2)+.+t(r)。磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到最小。二、 算法问题形式化表示对于给定的N个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数和占用磁带的长度三、 期望输入与输出输入：input.txt给出输入数据。第1行是正整数n，表示文件个数。接下来的n行中，每行有2个正整数a和b,分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率为ak/ai。对所有输入的均假定c = 1。输出：将编程计算出的最小平均读取时间输出到文件output.txt。输入文件示例 输出文件示例iput.txt output.txt6 15 3 5 4 9 7 8 3四、 算法分析与步骤描述因为长度和检索该程序的时间成正比，输入程序后，先按程序长度由小到大排序，即程序短的放在前面，则由题意的检索方法可知该方法检索时间最短。1.输入n和L1,L2,.Ln;2.将L数组从小到大排序；3.计算出个个程序的从头查到的检索时间Ti；4.计算出最有存储的平均检索时间ST。五、 问题实例及算法运算步骤最多数量是最优先解决的问题，然后再数量最大的前提下让利用率站到最大,所以按照贪心策略先将占用的长度从小到大进行排序，以此输入到磁带中, 排序之后3,7,7,8,9,12,最佳组合应为 ,先按照数量最多的前提下可存放3个程序3 7 7,然后进行第2策略让利用率最大,3+7+7 = 17 24-17 = 7表明还剩下7个空间,从3，7，7最后一个数开始使其尽可能的大3，7，12 = 22，此时磁带还剩下空间2，再从倒数第二个数开始使其尽可能的大，但是最大上限不能超过12,3，8，12 = 23磁带还剩下1空间,然后在分析比8大的数9则3+9+12 是24,再从倒数第三个数开始重复上述操作，但是比3大一位是7，如果采用7，9，12已经超过磁带最大上限所以停止查找,既此时最大个数3最大利用率24。六、 算法运行截图七、 算法复杂度分析时间复杂度为O(n)第五章 电路板问题一、 算法问题描述最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是，将n块电路板以最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对应于不同的电路板插入方案。设B=1，2，n 是n块电路板的集合。集合L= N 1 ， N 2 ， N m 是n块电路板的m个连接块。其中每个连接块N i 是B的一个子集，且N i 中的电路板用同一根导线连接在一起。二、 算法问题形式化表示在最小长度电路板排列问题中，连接块的长度是指该连接块中第1 块电路板到最后1块电路板之间的距离。例如在图示的电路板排列中，连接块N 4 的第1 块电路板在插槽3 中，它的最后1块电路板在插槽6中，因此N 4 的长度为3。同理N 2 的长度为2。图中连接块最大长度为3。试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。对于给定的电路板连接块，设计一个队列式分支限界法，找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。这8 块电路板的一个可能的排列如图所示: 三、 期望输入与输出输入:第一行有2 个正整数n和m (1m,n20)。接下来的n行中，每行有m个数。第k行的第j个数为0 表示电路板k不在连接块j 中，1 表示电路板k在连接块j中。输出:将计算出的电路板排列最小长度及其最佳排列输出。第1 行是最小长度；接下来的1 行是最佳排列。Input： output：85 411111 5431628701010011101011010100110100000101001四、 算法分析与步骤描述当i=n时，算法搜索到叶结点，所有n块电路板都已经排定， 其密度为cd； 当in时，电路板尚未排列完成。X1:i-1是当前扩展结点所 相应的部分排列，cd是相应的部分排列密度。在当前部分排列之后加入一块未排定的电路板，扩展当前部分排列 产生当前扩展结点的一个子结点。对于这个子结点，计算新的部分 排列密度ld如果ld=0。因此，最优解被更新的次数为O（m）；更新当前最优解的时间为O（mn）。综上可知，解电路板排列问题的回溯算法backtrack所要的计算时间为O（mn!）。第六章 野人问题一、 算法问题描述野人过河问题描述如下： 有M个牧师和N个野人过河（MN），只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。二、 算法问题形式化表示该问题就是求解牧师和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（牧师数）N（野人数）和M+N2的摆渡方案。由于牧师和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知道了。因此为了简便起见，在描述问题时，只描述一岸(如左岸）的情况就可以了。另外，该问题我们最关心的是在摆渡过程中，两岸状态的变化情况，因此船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几个牧师和野人，可以通过两个相连的状态简单得到。三、 期望输入与输出输入：本程序的设计考虑到了野人和牧师的人数、船可以容纳人数的动态设计，按照题目的要求，首先输入3个野人、3个牧师和船只容纳2人，也可以根据个人的需求动态输入其他数据，输入的数据限定为正整数。输出：输出时野人和牧师每一次过河的过程都会进行输出，若动态输入的野人、牧师和船可以容纳人数无法满足安全渡河，则输出“问题无解”四、 算法分析与步骤描述先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，3野人，3牧师； 乙岸，0野人，0牧师；船停在甲岸，船上有0个人；目标状态：甲岸，0野人，0牧师；乙岸，3野人，3牧师；船停在乙岸，船上有0个人；整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符：渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后，剩下的核心问题就是搜索方法了，本算法采用深度优先搜索，通过一个FindNext()函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process()函数递规调用FindNext()，一级一级的向后扩展。五、 问题实例及算法运算步骤首先从比较简单的入手，先设M=N3，则给定的问题可用下图表示，图中L和R表示左岸和右岸，B1或0分别表示有船或无船。约束条件是：两岸上MN，船上MN2。 其实就是五种状态：1.两个野人过河2.两个牧师过河3.一个