算法与分析 课程设计报告
题 目： 算法设计和分析 专 业： 网络工程 班 级： 1020552 学 号： 11 姓 名： 赫前进
太原工业学院计算机工程系
2012年 11月 24 日
1 / 10
第二章 主元素问题
一、 算法问题描述
主元素问题: 设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 五、 问题实例及算法运算步骤 首先运行程序，按照提示输入数据；其次求出在数组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,可以判断存在主 2 / 10 元素，然后进行快排，移动元素得到数组为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 三、 期望输入与输出 3 / 10
算法设计与分析课程设计报告
