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

《算法设计与分析课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法与分析课程设计报告题目：算法设计和分析专业：网络工程班级：学号：11姓名：赫前进太原工业学院计算机工程系2012年11月24日第二章主元素问题一、算法问题描述主元素问题:  设T[0..n-1]是n个元素的数组。对任一元素x，设S(x)={i

2、T[i]=x}。当

3、S(x)

4、>n/2时，称x为T的主元素。如果T中元素存在序关系，按分治策略设计并实现一个线性时间算法，确定T[0..n-1]是否有一个主元素。二、算法问题形式化表示若T中存在主元素，则将T分为两部分后，T的主元素也必为两部分中至少一部分的主元素，因此可用分治法。将元素划分为两部分，递归地

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

6、、算法分析与步骤描述选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为k。如果k>n/2，那么继续用同样的方法在左边部分找；如果k

7、（n+1）/2大的数；用QuickSort进行快速排序；用Partition方法进行数组划分，用swap将小于x的元素移到x左边，大于x的元素移到x右边；然后就可以得到时候存在主元素，输出到屏幕上。从屏幕得到数组001108111后，可以得到出现次数最多的元素为1，其次数为5，第（n+1）/2大的数字为0,可以判断存在主元素，然后进行快排，移动元素得到数组为000111118，此时就可以得到主元素为1。一、算法运行截图二、算法复杂度分析根据快速排序的思想，可以在平均时间复杂度为O(n)的时间内找出一个数列的中位数。然后再用O(n)的时间检查它是否是主

8、元素,时间复杂度分析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[][]存储中间

9、结果，如下图所示，为已经初始化后的情况。然后从D[1,1]开始从左到右，从上到下依次按填表，表的最后一个元素D[m,n]就是要求的最终结果。 01234560012345611      22      33      44      55      66      三、期望输入与输出输入：由文件input.txt提供输入数据，文件的第一行是字符串A，文件的第二行是文件B。输出：程序运结束时，将编辑距离d（A，B），输出到文件output.txt的第一行中。一、算法分析与步骤描述注意：报告中不附加程序代码，主要程序要描述程序流程设所给的两个字符串为A

10、[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}。二、问题实例

11、及算法运算步骤例子：下面实际解决一下从srcStr="bd" 到dstStr="abcd"的过程，上面这三种