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

算法与分析
课程设计报告

题 目： 算法设计和分析
专 业： 网络工程
班 级： 1020552
学 号： 11
姓 名： 赫前进

太原工业学院计算机工程系

2012年 11月 24 日

第二章 主元素问题
一、 算法问题描述
主元素问题:  设T[0..n-1]是n个元素的数组。对任一元素x，设S(x)={i|T[i]=x}。当|S(x)|>n/2时，称x为T的主元素。如果T中元素存在序关系，按分治策略设计并实现一个线性时间算法，确定T[0..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。如果k>n/2，那么继续用同样的方法在左边部分找；如果k<n/2就在右边部分找；k=n/2就找到了中位元素。根据快速排序的思想，可以在平均时间复杂度为O(n)的时间内找出一个数列的中位数。然后再用O(n)的时间检查它是否是主元素。
五、 问题实例及算法运算步骤
首先运行程序，按照提示输入数据；其次求出在数组T[0:n]中出现次数最多的元素x出现的次数k；然后用select方法线性时间选择，找到第（n+1）/2大的数；用QuickSort进行快速排序；用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。
六、 算法运行截图

七、 算法复杂度分析
根据快速排序的思想，可以在平均时间复杂度为O(n)的时间内找出一个数列的中位数。然后再用O(n)的时间检查它是否是主元素, 时间复杂度分析master()中求中位数可以在平均时间复杂度为O(n)的时间内完成,检查中位数是否是主元素耗时O(n),所以时间复杂度为O(n)。

第三章 字符串问题
一、 算法问题描述
设A和B是两个字符串，要用最少的字符操作将字符串A转换为字符串B
字符串操作包括，
1）删除一个字符
2）插入一个字符
3）将一个字符改为另一个字符
将字符串A变换成字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A，B）。试着设计一个有效算法，对任意给出的俩个字符串A和B，计算出他们的编辑距离d(A,B)。
二、 算法问题形式化表示
定义一个二维数组D[][]存储中间结果，如下图所示，为已经初始化后的情况。然后从D[1,1]开始从左到右，从上到下依次按填表，表的最后一个元素D[m,n]就是要求的最终结果。

0
1
2
3
4
5
6
0
0
1
2
3
4
5
6
1
1

2
2

3
3

4
4

5
5

6
6

三、 期望输入与输出
输入：由文件input.txt 提供输入数据，文件的第一行是字符串A，文件的第二行是文件B。
输出：程序运结束时，将编辑距离d（A，B），输出到文件output.txt的第一行中。
四、 算法分析与步骤描述
注意：报告中不附加程序代码，主要程序要描述程序流程
设所给的两个字符串为A[1:m]和B[1:n]。定义D[i][j]=d(A[1:i],B[1,j])。单字符a,b间的距离定义为：
d(a,b)=0 (a=b)
d(a,b)=1(a!=b)
考察从字符串A[1:i]到字符串B[1:j]的变换。可分成以下几种情况：
（1）字符A[i]改为字符B[j]；需要d(A[i],B[j])次操作。
（2）删除字符A[i]；需要1次操作。
（3）插入字符B[j]；需要1次操作。
因此，D[i][j]可递归地计算如下。
D[i][j]=min{D[i-1][j-1]+d(A[i],B[j]),D[i-1][j]+1,D[i][j-1]+1}。
五、 问题实例及算法运算步骤
例子：下面实际解决一下从srcStr = "bd"  到 dstStr = "abcd"的过程，上面这三种情况分别是初始化的时候要做的,首先用一维数组表示两位数组,纵向 i = 0 -> m+1 ， d[i * (n + 1)] = i
横向 i = 0 -> n+1, d[i] = 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] 修改字符srcStr[i - 1], 使之变为dstStr[j - 1], 如果srcStr[i - 1] == dstStr[j - 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行的数据，因此可以用一个一维数组dis[0…n]代替二维数组D[0…m,0…n]，因此空间复杂性降为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=cΣpik 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.txt
6 15
3 5 4 9 7 8 3
四、 算法分析与步骤描述
因为长度和检索该程序的时间成正比，输入程序后，先按程序长度由小到大排序，即程序短的放在前面，则由题意的检索方法可知该方法检索时间最短。
1.输入n和L[1],L[2],...L[n];
2.将L数组从小到大排序；
3.计算出个个程序的从头查到的检索时间T[i]；
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 (1≤m,n≤20)。接下来的n行中，每行有m个数。第k行的第j个数为0 表示电路板k不在连接块j 中，1 表示电路板k在连接块j中。
输出:将计算出的电路板排列最小长度及其最佳排列输出。第1 行是最小长度；接下来的1 行是最佳排列。
Input： output：
8 5 4
1 1 1 1 1 5 4 3 1 6 2 8 7
0 1 0 1 0
0 1 1 1 0
1 0 1 1 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 0 0 1
四、 算法分析与步骤描述
当i=n时，算法搜索到叶结点，所有n块电路板都已经排定， 其密度为cd；
当i<n时，电路板尚未排列完成。X[1:i-1]是当前扩展结点所 相应的部分排列，cd是相应的部分排列密度。
在当前部分排列之后加入一块未排定的电路板，扩展当前部分排列 产生当前扩展结点的一个子结点。对于这个子结点，计算新的部分 排列密度ld
如果ld<bestd，继续按深度优先方式递归地对相应子树进行搜索
否则，剪去该子树，算法回溯到为活结点的最近的父结点处继续 按深度优先方式进行搜索；
五、 问题实例及算法运算步骤
例如，设n=8，m=5。给定n块电路板及其m个连接块如下：
B={1，2，3，4，5，6，7，8}；
L={ N 1 ， N 2 ，N 3 ， N 4 ， N 5 }；
N 1 ={4，5，6}； N 2 ={2，3}； N 3 ={1，3}； N 4 ={3，6}； N 5 ={7，8}。
在最小长度电路板排列问题中，连接块的长度是指该连接块中第1 块电路板到最后1块电路板之间的距离。例如在图示的电路板排列中，连接块N 4 的第1 块电路板在插槽3 中，它的最后1块电路板在插槽6中，因此N 4 的长度为3。同理N 2 的长度为2。图中连接块最大长度为3。试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。对于给定的电路板连接块，设计一个队列式分支限界法，找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
六、 算法运行截图

七、 算法复杂度分析
在解空间排列树的每个结点处，算法backtrack花费O(m)计算时间为每个儿子结点计算密度。因此，计算密度所花费的总计算时间为O（mn!）。另外，生成排列树需要O（n!）。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd>=0。因此，最优解被更新的次数为O（m）；更新当前最优解的时间为O（mn）。
综上可知，解电路板排列问题的回溯算法backtrack所要的计算时间为O（mn!）。

第六章 野人问题
一、 算法问题描述
野人过河问题描述如下： 有M个牧师和N个野人过河（M≥N），只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。
二、 算法问题形式化表示
该问题就是求解牧师和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（牧师数）≥N（野人数）和M+N≤2的摆渡方案。
由于牧师和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知道了。因此为了简便起见，在描述问题时，只描述一岸(如左岸）的情况就可以了。另外，该问题我们最关心的是在摆渡过程中，两岸状态的变化情况，因此船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几个牧师和野人，可以通过两个相连的状态简单得到。
三、 期望输入与输出
输入：本程序的设计考虑到了野人和牧师的人数、船可以容纳人数的动态设计，按照题目的要求，首先输入3个野人、3个牧师和船只容纳2人，也可以根据个人的需求动态输入其他数据，输入的数据限定为正整数。
输出：输出时野人和牧师每一次过河的过程都会进行输出，若动态输入的野人、牧师和船可以容纳人数无法满足安全渡河，则输出“问题无解”
四、 算法分析与步骤描述
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
     乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
     乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本算法采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
五、 问题实例及算法运算步骤
首先从比较简单的入手，先设M=N＝3，则给定的问题可用下图表示，图中L和R表示左岸和右岸，B＝1或0分别表示有船或无船。约束条件是：两岸上M≥N，船上M＋N≤2。

其实就是五种状态：
1.两个野人过河
2.两个牧师过河
3.一个野人一个牧师过河
4.一个牧师过河
5.一个野人过河
只需对这5种状态进行搜索，直到得到问题的解，或者得到问题无解，搜索过程即终止。
六、 算法运行截图

七、 算法复杂度分析
时间复杂度：因为程序中用了很多循环语句while，而且在进行广度搜索的时候要把每种情况都要运算一遍，在每进行一次渡河时都要每个进行一遍搜索，所以时间复杂度很大，要进行很多步骤。因为在程序中用了动态分配空间，用的时候再去申请空间，所以节省了很多不必要的空间，空间复杂度相对较小。