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

常熟理工学院《算法设计与分析》实验指导与报告书_2013-2014_学年第_1_学期专业：_____物联网________学号：__________姓名：____________实验地点：_____N6-107________指导教师：_____聂盼红________计算机科学与工程学院2013-2-实验目录实验一求最大公约数.....................................................................................................................3实验二斐波那契数列.....................................................................................................................8实验三串匹配问题.......................................................................................................................13实验四堆的创建与堆排序...........................................................................................................17实验五霍纳法则...........................................................................................................................21实验六Warshall算法和Floyed算法.......................................................................................26实验七最优二叉查找树...............................................................................................................30实验八解非线性方程的算法..........................................................................错误!未定义书签。-3-实验一求最大公约数实验目的与任务⑴复习数据结构课程的相关知识，实现课程间的平滑过渡；⑵掌握并应用算法的数学分析和后验分析方法；⑶理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。预习内容：第一章绪论1.1算法的概念实验内容及要求⑴至少设计出三个版本的求最大公约数算法；⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间；备注:说明：为了度量算法的运行时间，可以借助于clock（）函数或者time（）函数完成它们的使用方法参见如下实例：/*clock版本*/#includestdio.h#includestdlib.h#includetime.hintmain(void){doublet1,t2;inti,j;doublek;t1=clock();/*在下方添加待测试运行时间的代码;*/for(i=0;i10000;i++)for(j=0;j10000;j++)k=0.123*j+3.567*i;t2=clock();printf(Ittakes%lf\n,(t2-t1)/CLK_TCK);/*其中CLK_TCK是时钟周期，是一个常量,clock()函数计算出来的是硬件滴答的数目，不是毫秒。在TC2.0中硬件每18.2个滴答是一秒，*/return0;}/*time版本*/#includetime.h#includestdio.h#includedos.hintmain(void){-4-time_tstart,end;inti,j;doublek;start=time(NULL);/*在下方添加待测试运行时间的代码;*/for(i=0;i10000;i++)for(j=0;j10000;j++)k=0.123*j+3.567*i;end=time(NULL);printf(Thetimewas:%f\n,difftime(end,start));return0;}⑷通过分析对比，得出自己的结论。提示:下列程序可实现求出n的质因数的个数number.并可求出n的质因数。for(i=2;i=n;i++){while(n=i){if(n%i==0){number++;n=n/i;}elsebreak;}}/*计算n有多少个质因数*/-5-实验结果（可续页）（1）欧几里得算法计数法：源代码：#includestdio.h#includestdlib.h#includetime.h#includemath.hintEuclid(intm,intn){intr;while(n!=0){r=m%n;m=n;n=r;}returnm;}intmain(void){intm,n;doublet1,t2;scanf(%d%d,&m,&n);t1=clock();printf(%d\n,Euclid(m,n));t2=clock();printf(Ittakes%lf\n,(t2-t1)/CLK_TCK);return0;}-6-#includestdio.h#includedos.h#includetime.h#includemath.hintEuclid(intm,intn){intr;while(n!=0){r=m%n;m=n;n=r;}returnm;}intmain(void){intm,n;time_tstart,end;scanf(%d%d,&m,&n);start=time(NULL);printf(%d\n,Euclid(m,n));end=time(NULL);printf(Thetimewas:%f\n,difftime(end,start));return0;}（2）连续整数检测算法计数法：源代码：#includestdio.h#includestdlib.h#includetime.h#includemath.hintgcd(intm,intn){intt;-7-if(mn)t=n;elset=m;while(!(m%t==0&&n%t==0)){t--;}returnt;}intmain(void){intm,n;doublet1,t2;scanf(%d%d,&m,&n);t1=clock();printf(%d\n,gcd(m,n));t2=clock();printf(Ittakes%lf\n,(t2-t1)/CLK_TCK);return0;}教师评分-8-实验二斐波那契数列实验目的与任务⑴深入理解斐波那契数列；(2)理解递归的思想；预习内容斐波那契数列；实验内容及要求⑴上机实现斐波那契数列的四种算法，并用计时法测算四种算法的运行时间；⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶通过对四种算法分析对比，得出自己的结论实验结果（可续页）#includestdio.h#includemath.h//迭代法intfb1(intn){longintfib[100000]={1,1};inti;for(i=2;in;i++)fib[i]=fib[i-1]+fib[i-2];for(i=0;in;i++)printf(Fib[%d]=%d\n,i,fib[i]);return0;}//递归法longfb2(inti){if(i=1)returni;elsereturnfb2(i-1)+fb2(i-2);}//公式法intfb3(intn){intfib[1000];inti;for(i=0;in;i++){fib[i]=pow(((1+sqrt(5))/2.0),i)/sqrt(5)-pow(((1-sqrt(5))/2.0),i)/sqrt(5);}-9-for(i=1;in;i++){printf(%d\n,fib[i]);}}intfb4(intn){intm[2][2]={1,1,1,0};intn[2][2]={1,1,1,0};intk[2][2]={1,1,1,0};inta=1;intb=1;if(top==1){returna;}elseif(top==2){returnb;}intres;inti;for(i=3;itop;i++){k[0][0]=m[0][0]*n[0][0]+m[0][1]*n[1][0];k[0][1]=m[0][0]*n[0][1]+m[0][1]*n[1][1];k[1][0]=m[1][0]*n[0][0]+m[1][1]*n[1][0];k[1][1]=m[1][0]*n[0][1]+m[1][1]*n[1][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;returnres;}intmain(){intn;printf(plsinputn:);scanf(%d,&n);inti;for(i=0;in;i++){printf(%ld\n,fb2(i));}//fb3(n);-10-}各算法之间的比较：（1）递归算法是最好理解的算法,和人的思路相当接近,对应的数学描述很清晰,容易编程.如果使用递归函数,将会占用大量的内存资源,在大量调用递归函数之后很可能造成内存崩溃,就算不崩溃,也会是长时间的运算.在调用了clock函数后,计算出了递归函数的耗时,是四个函数中最大的.而且这是个致命的缺点.（2）迭代算法：虽然迭代算法的思路稍难于递归算法，但是时间复杂度与空间复杂度均优于递归算法。-11-（3）公式算法:使用一个数学公式来进行计算,几乎不耗什么时间,一次运算就可以得到结果,时间和n的取值没有太大关系,只和运算性能有关.-12-教师评分-13-实验三串匹配问题实验目的与任务⑴深刻理解并掌握蛮力法的设计思想；(2)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。（了解空间换时间权衡的思想）预习内容BruteForce算法,Horspool算法.(P1977.2串匹配中的输入增强技术)实验内容及要求⑴实现BruteForce算法；⑵实现BM算法的简化算法：Horspool算法；⑶对上个算法进行时间复杂性分析，并设计实验程序验证分析结果。实验结果（可续页）BruteForce算法：#includestdio.h#includestring.h#defineM100intmain(){charst1[M],st2[M];intlen1,len2;printf(plsinputstring1\n);gets(st1);len1=strlen(st1);printf(plsinputstrint2\n);gets(st2);len2=strlen(st2);if(len1len2)printf(error:st2islongerthanst1!);else{inti,j;for(i=0;ilen1-len2;i++){j=0;while(jlen2&&(st2[j]!='\0')&&(st1[i+j]!='\0')&&(st2[j]==s