常熟理工学院

《算法设计与分析》实验指导与报告书

_2013-2014_学年 第_1_ 学期

专 业： _____物联网________ 学 号： __________ 姓 名： ____________ 实验地点：_____N6-107________ 指导教师：_____聂盼红________

计算机科学与工程学院

2013

实验目录

实验一 求最大公约数..................................................................................................................... 3 实验二 斐波那契数列..................................................................................................................... 8 实验三 串匹配问题....................................................................................................................... 13 实验四 堆的创建与堆排序 ........................................................................................................... 17 实验五 霍纳法则........................................................................................................................... 21 实验六 Warshall算法和Floyed算法 ....................................................................................... 26 实验七 最优二叉查找树 ............................................................................................................... 30 实验八 解非线性方程的算法 ....................................................................... 错误！未定义书签。

实验一 求最大公约数

time_t start, end; int i,j; double k; start = time(NULL); /*在下方添加待测试运行时间的代码;*/ for(i=0;i<10000;i++) for(j=

0;j<10000;j++) k=0.123*j+3.567*i; end = time(NULL); printf("The time was: %f\n", difftime(end,start)); return 0; }

⑷ 通过分析对比，得出自己的结论。 提示:下列程序可实现求出n的质因数的个数number.并可求出n的质因数。for(i=2;i<=n;i++) { while(n>=i) { if(n%i==0) { number++; n=n/i; } else break; } }/*计算n有多少个质因数*/

-4-

实验结果(可续页)(1) 欧几里得算法 计数法： 源代码： #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> int Euclid(int m,int n) { int r; while(n!=0){ r=m%n; m=n; n=r; } return m; } int main( void ) { int m,n; double t1,t2; scanf("%d %d",&m,&n); t1=clock(); printf("%d\n",Euclid(m,n)); t2=clock(); printf("It takes %lf \n",(t2-t1)/CLK_TCK); return 0; }

-5-

#include <stdio.h> #include <dos.h> #include <time.h> #include <math.h> int Euclid(int m,int n) { int r; while(n!=0){ r=m%n; m=n; n=r; } return m; } int main( void ) { int m,n; time_t start, end; scanf("%d %d",&m,&n); start = time(NULL); printf("%d\n",Euclid(m,n)); end = time(NULL); printf("The time was: %f\n", difftime(end,start)); return 0; }

(2)连续整数检测算法 计数法： 源代码： #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> int gcd(int m,int n) { int t;-6-

if(m>n)t=n; else t=m; while(!(m%t==0&&n%t==0)){ t--; } return t; } int main( void ) { int m,n; double t1,t2; scanf("%d %d",&m,&n); t1=clock(); printf("%d\n",gcd(m,n)); t2=clock(); printf("It takes %lf \n",(t2-t1)/CLK_TCK); return 0; }

教师评分

-7-

实验二 斐波那契数列

for(i=1;i<n;i++) { printf("%d\n",fib[i]); } } int fb4(int n) { int m[2][2] = {1,1,1,0}; int n[2][2] = {1,1,1,0}; int k[2][2] = {1,1,1,0}; int a = 1; int b = 1; if(top == 1){ return a; }else if(top == 2){ return b; } int res; int i; for(i=3;i<top;i++){ k[0][0] = m[0][0]*n[0][0] k[0][1] = m[0][0]*n[0][1] k[1][0] = m[1][0]*n[0][0] k[1][1] = m[1][0]*n[0][1] m[0][0] = k[0][0]; m[0][1] = k[0][1]; m[1][0] = k[1][0]; m[1][1] = k[1][1]; } res = k[0][0]*a + k[0][1]*b; return res; } int main() { int n; printf("pls input n:"); scanf("%d",&n

); int i; for(i =0;i<n;i++) { printf("%ld\n",fb2(i)); } //fb3(n);-9-

+ + + +

m[0][1]*n[1][0]; m[0][1]*n[1][1]; m[1][1]*n[1][0]; m[1][1]*n[1][1];

}

各算法之间的比较： (1)递归算法是最好理解的算法,和人的思路相当接近,对应的数学描述很清晰,容 易编程. 如果使用递归函数,将会占用大量的内存资源,在大量调用递归函数之后很 可能造成内存崩溃 ,就算不崩溃,也会是长时间的运算 .在调用了clock函数后,计算 出了递归函数的耗时,是四个函数中最大的.而且这是个致命的缺点. (2)迭代算法：虽然迭代算法的思路稍难于递归算法，但是时间复杂度与空间复杂 度均优于递归算法。- 10 -

(3)公式算法:使用一个数学公式来进行计算,几乎不耗什么时间,一次运算就可以 得到结果,时间和n的取值没有太大关系,只和运算性能有关.

- 11 -

教师评分

- 12 -

实验三 串匹配问题

}

Horspool算法： #include<stdio.h> #include<stdlib.h> #include<string.h> #define HASH_SIZE 256 int table[HASH_SIZE]; void ShiftTable(char pattern[]){

int m=strlen(pattern);int i,j; for(i=0;i<HASH_SIZE;i++) table[i]=m; for(j=0;j<m-1;j++) table[ pattern[j] ]=m-1-j; return table; } int HorspoolMatching(char pattern[],char text[]){ ShiftTable(pattern); int m=strlen(pattern); int n=strlen(text); int i=m-1; while(i <= n-1){ int k=0; while(k<=m-1 && pattern[m-1-k] == text[i-k] ) k++; if(k==m)- 14 -

{ printf("%d\n",i-m+1);break; } // return 0; else i=i+table[ text[i] ]; } return 0; }

int main() { char pattern[]="asd"; char text[]="ghiasdiou"; HorspoolMatching(pattern,text);

}

关于BruteForce算法,Horspool算法的比较： 蛮力算法就是简单地从左到右比较模式和文 本中的每一个对相应的字符，如果一旦不匹配，就把模式向右移动一格，在进行下一轮

尝试。这种尝试的最大次数是n-m+1次，所以这使得蛮力算法的最差性能是Θ (nm)的类 型。平均效率是Θ (n)。Horspool算法的最差效率是Θ (nm),但对于随机文本来说， 它的效率是Θ (n),但是就平均来说，Horspool算法显然要比蛮力算法快许多。

- 15 -

时间复杂度： (1)BF算法就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配， 主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O(n*m),其中n和m分别为 串s和串t的长度。 (2) horspool算法将主串中匹配窗口的最后一个字符跟模式串中的最后一个字符比 较。如果相等，继续从后向前对主串和模式串进行比较，直到完全相等或者在某个字符 处不匹配为止(如下图中的α 与σ 失配) 。如果不匹配，则根据主串匹配窗口中的最后 一个字符β 在模式串中的下一个出现位置将窗口向右移动。Horspool算法最坏情况下的 时间复杂度是O(mn),但平均情况下它的时间复杂度是O(n)。

教师评分

- 16 -