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

算 法 与 分 析

课 程 设 计 报 告

题

目： 算法设计和分析

专

班

学

姓

业：

级：

号：

名：

网络工程

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

边部分找；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。

五、 问题实例及算法运算步骤

最多数量是最优先解决的问题，然后再数量最大的前提下让利用率站到最大,

所以按照贪心策略先将占用的长度从小到大进行排序，以此输入到磁带中,