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

1、算法与分析课程设计报告题目:算法设计和分析专业：网络工程班级：1020552学号: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 的主元素也必为两部分中至少一 部分的主元素，因此可用分治法。将元素划分为两部分，递归地检查两部分有 无主元素。算法如下：若

2、T 只含一个元素，则此元素就是主元素，返回此数。将T分为两部分T1和T2 (二者元素个数相等或只差一个)，分别递归调用此 方法求其主元素 m1 和 m2。若ml和m2都存在且相等，则这个数就是 T的主元素，返回此数。若 m1 和 m2 都存在且不等，则分别检查这两个数是否为 T 的主元素，若有则 返回此数，若无则返回空值。若 m1 和 m2 只有一个存在，则检查这个数是否为 T 的主元素，若是则返回此 数，若否就返回空值。若ml和m2都不存在，则T无主元素，返回空值。三、期 望输入与输出输入：数组中元素的个数 9数组元素 0 0 1 1 0 8 1 1 1 输出：显示主元素是 1。四、算 法分

3、析与步骤描述 选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边， 大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为k。如果kn/2，那么继续用同样的方法在左边部分找；如果 kvn/2就在右 边部分找； k=n/2 就找到了中位元素。根据快速排序的思想，可以在平均时间 复杂度为0(n)的时间内找出一个数列的中位数。然后再用0(n)的时间检查它是否是主元素。五、问题实例及算法运算 步骤 首先运行程序，按照提示输入数据；其次求出在数组 T0：n 中出现次数最多的 元素x出现的次数k；然后用select方法线性时间选择，找到第(n+1) /2大 的数；用 Qu

4、ickSort 进行快速排序；用 Partition 方法进行数组划分，用 swap 将小于x的元素移到x左边，大于x的元素移到x右边；然后就可以得到时候 存在主元素，输出到屏幕上。从屏幕得到数组 0 0 1 1 0 8 1 1 1 后，可以得 到出现次数最多的元素为 1，其次数为 5，第( n+1) /2 大的数字为 0,可以判断存在主元素，然后进行快排，移动元素得到数组为0 0 0 1 1 1 1 1 8 ，此时就可以得到主元素为1。六、算法运行截图卜止a MZ卩请揃入数组元素个耐：请输入数组=该数组存在主元素是2七、算法复杂度分析根据快速排序的思想，可以在平均时间复杂度为0(n)的时间内

5、找出一个数列的中位数。然后再用 0(n)的时间检查它是否是主元素，时间复杂度分析master() 中求中位数可以在平均时间复杂度为 0(n)的时间内完成，检查中位数是否是主 元素耗时0(n),所以时间复杂度为0(n)。第三章字符串问题一、算法问题描述设A和B是两个字符串，要用最少的字符操作将字符串A转换为字符串B字符串操作包括，1) 删除一个字符2) 插入一个字符3) 将一个字符改为另一个字符将字符串A变换成字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d( A，B)。试着设计一个有效算法，对任意给出的俩个字符串A和B，计算出他们的编辑距离d(A,B)。二、算法问题形式化表示定义

6、一个二维数组D存储中间结果，如下图所示，为已经初始化后的情况。 然后从D1,1开始从左到右，从上到下依次按填表，表的最后一个元素Dm,n就是要求的最终结果。0123456001 :23456112233445566三、期望输入与输出输入：由文件input.txt提供输入数据，文件的第一行是字符串A,文件的第二行是文件B。输出：程序运结束时，将编辑距离d (A, B),输出到文件output.txt 的第一行中。四、算法分析与步骤描述注意：报告中不附加程序代码，主要程序要描述程序流程设所给的两个字符串为 A1:m和B1:n。定义Dij=d(A1:i,B1,j)。单字符a,b间的距离定义为：d(a

7、,b)=0 (a=b)d(a,b)=1(a!=b)考察从字符串A1:i到字符串B1:j的变换。可分成以下几种情况：(1) 字符Ai改为字符Bj;需要d(Ai,Bj) 次操作。(2) 删除字符Ai;需要1次操作。(3) 插入字符Bj;需要1次操作。因此，Dij可递归地计算如下。Dij=mi nDi-1j-1+d(Ai,Bj),Di-1j+1,Dij-1+1。五、问题实例及算法运算步骤例子：下面实际解决一下从 srcStr = bd 至U dstStr = abcd的过程，上 面这三种情况分别是初始化的时候要做的，首先用一维数组表示两位数组，纵向i =0 - m+1 ， di * (n + 1)

8、= 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,如果 srcStrib) 从 d i - 1 j srcStr i - 1 c) 从 d i j - 1 dstStr j - 1 使之变为dstStrj - 1, -1 = dstStrj - 1则这一步可以免去在srcStr的i - 1处添加一个字符，变为

9、 dstStr j - 1 在dstStr的j - 1 处删除一个字符变为srcStr i - 1,三者之间的最小值赋给使字符,使字符 d i j 0123412六、算法运行截图input, arc Surina：口lease inpuu dm匸 Scrmg:Rc auIc Art ay:012341L13332232Edit Distanct :2七、算法 复杂度分析从上面算法可以看出，该算法时间复杂性为0(m*n),空间复杂性为O(m*n)。同时可以看出，当对第 i 行进行填表时，只需要用到第 i-1 行的数据，因此可以 用一个一维数组disOn代替二维数组 D0m,0n，因此空间复杂性降

10、为 O(n)。第四 章 磁带 存储问题算法问题描述设有n个程序1 , 2,n 要存放在长度为L的磁带上。程序i存放在磁带 上的长度是li , 1=i= n。这n个程序的读取概率分别为pl, p2, pn, 且工pi=1(i=1,2,.n)。如果将这n个程序按i1 , i2 ,in的次序存放， 则读取程序所需的时间tr=c工pik lik(k=1,2,.r)(可假定c为1)。这n个 程序的平均读取时间为 t(1)+t(2)+.+t(r)。磁带最优存储问题要求确定这 n个程序在磁带上的一个存储次序，使平均读取时间达到最小。二、算法问题形式化表示对于给定的N个程序存放在磁带上的长度，计算磁带上最多可

11、以存储的程序数 和占用磁带的长度三、期 望输入与输出输入：input.txt 给出输入数据。第1行是正整数n,表示文件个数。接下来的 n 行中，每行有 2 个正整数 a 和 b, 分别表示程序存放在磁带上的长度和读取概 率。实际上第k个程序的读取概率为 ak/工ai。对所有输入的均假定 c = 1。 输出：将编程计算出的最小平均读取时间输出到文件 output.txt 。 输入文件示例输出文件示例iput.txtoutput.txt6 153 5 4 9 7 8 3四、算 法分析与步骤描述因为长度和检索该程序的时间成正比，输入程序后，先按程序长度由小到大 排 序，即程序短的放在前面，则由题意的

12、检索方法可知该方法检索时间最短。1.输入 n 和 L1,L2,.Ln;2. 将 L 数组从小到大排序；3. 计算出个个程序的从头查到的检索时间 Ti；4. 计算出最有存储的平均检索时间 ST。五、问题实例及算法运算 步骤 最多数量是最优先解决的问题，然后再数量最大的前提下让利用率站到最大 , 所以按照贪心策略先将占用的长度从小到大进行排序，以此输入到磁带中 ,62 4831 2797排序之后3,7,7,8,9,12,最佳组合应为3912 ,先按照数量最多的前提下可存放3个程序3 7 7,然后进行第2策略让利用率最大,3+7+7 = 17 24-17 =7表明还剩下7个空间,从3，7，7最后一个

13、数开始使其尽可能的大3，7，12=22,此时磁带还剩下空间2,再从倒数第二个数开始使其尽可能的大，但是 最大上限不能超过12,3，8， 12 = 23磁带还剩下1空间,然后在分析比8大的 数9则3+9+12是24,再从倒数第三个数开始重复上述操作，但是比 3大一位是 7,如果采用7, 9, 12已经超过磁带最大上限所以停止查找，既此时最大个数3最大利用率24。六、算法运行截图&闫题仮 JavsdarTW1 Dava 胡餌文件無. txt七、算法复杂度分析时间复杂度为0(n)第五章电路板问题一、算法问题描述最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是，将n块电路板以

14、最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对应于不同的电路板插入方案。设B=1, 2,，n 是n块电路板的集合。集合 L= N 1 , N 2 ,，N m 是 n块电路板的m个连接块。其中每个连接块 Ni是B的一个子集，且Ni中的 电 路板用同一根导线连接在一起。二、算法问题形式化表示在最小长度电路板排列问题中，连接块的长度是指该连接块中第1块电路板到最后1块电路板之间的距离。例如在图示的电路板排列中，连接块 N 4的第1 块电路板在插槽3中，它的最后1块电路板在插槽6中，因此N 4的长度为3。同理N 2的长度为2。图中连接块最大长度为3。试设计一个分支限界法找 出所给n

15、个电路板的最佳排列，使得 m个连接块中最大长度达到最小。对于给定的电路板连接块，设计一个队列式分支限界法，找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。这8块电路板的一个可能的排列如图所示： 12345678三、期望输入与输出输入:第一行有2个正整数n和m (1 m,nw20)。接下来的n行中，每行有 m 个数。第k行的第j个数为0表示电路板k不在连接块j中，1表示电路板k 在连接块j中。输出:将计算出的电路板排列最小长度及其最佳排列输出。第1行是最小长度；接下来的1行是最佳排列。In put :output :8 541 1 1 1 15 4 3 1 62870 1 0 1

16、 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1四、算法分析与步骤描述当i=n时，算法搜索到叶结点，所有n块电路板都已经排定， 其密度为cd;当 i=0。因此，最优解被更新的次数为O( m);更新当前最优解的时间为 O (mr)。综上可知，解电路板排列问题的回溯算法backtrack所要的计算时间为0(mn!)。第六章野人问题一、算法问题描述野人过河问题描述如下：有M个牧师和N个野人过河(M N),只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数， 那么牧师就会有危险。二、算法问题形式化表示该问题就是

17、求解牧师和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M (牧师数)N (野人数)和M+N2的摆渡方案。由于牧师和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知 道了。因此为了简便起见，在描述问题时，只描述一岸(如左岸)的情况就可以了。另外，该问题我们最关心的是在摆渡过程中，两岸状态的变化情况，因此 船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几个牧师 和野人，可以通过两个相连的状态简单得到。三、期望输入与输出输入：本程序的设计考虑到了野人和牧师的人数、船可以容纳人数的动态设计，按照题目的要求，首先输入3个野人、3个牧师和船只容纳2人，也可以根据 个 人的需求动态

18、输入其他数据，输入的数据限定为正整数。输出：输出时野人和牧师每一次过河的过程都会进行输出，若动态输入的野人、牧师和船可以容纳人数无法满足安全渡河，则输出“问题无解”四、算法分析与步骤描述先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，3野人，3牧师；乙岸，0野人，0牧师；船停在甲岸，船上有0个人；目标状态：甲岸，0野人，0牧师；乙岸，3野人，3牧师；船停在乙岸，船上有0个人；整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题 状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的 算符，根据题目要求，可以得出以下 5个算符：渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后，剩下的核心问题就是搜索方法了，本算法采用深度优先搜索， 通过一个FindNext()函数找出下一步可以进行的渡河操作中的最优操作，如 果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process()函数递规