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

《《算法设计与分析》实验指导及报告书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、常熟理工学院《算法设计与分析》实验指导与报告书_2013-2014_学年第_1_学期专业：_____物联网________学号：__________姓名：____________实验地点：_____N6-107________指导教师：_____聂盼红________计算机科学与工程学院2013实验目录-33-实验一求最大公约数3实验二斐波那契数列6实验三串匹配问题8实验四堆的创建与堆排序10实验五霍纳法则12实验六Warshall算法和Floyed算法14实验七最优二叉查找树16实验八解非线性方程的算法18实验一求最大公约数-33-实验目的与任务⑴复习数据结构课

2、程的相关知识，实现课程间的平滑过渡；⑵掌握并应用算法的数学分析和后验分析方法；⑶理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。预习内容：第一章绪论1.1算法的概念实验内容及要求⑴至少设计出三个版本的求最大公约数算法；⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间；备注:说明：为了度量算法的运行时间，可以借助于clock（）函数或者time（）函数完成它们的使用方法参见如下实例：/*clock版本*/#include#include

3、tdlib.h>#includeintmain(void){doublet1,t2;inti,j;doublek;t1=clock();/*在下方添加待测试运行时间的代码;*/for(i=0;i<10000;i++)for(j=0;j<10000;j++)k=0.123*j+3.567*i;t2=clock();printf("Ittakes%lf",(t2-t1)/CLK_TCK);/*其中CLK_TCK是时钟周期，是一个常量,clock()函数计算出来的是硬件滴答的数目，不是毫秒。在TC2.0中硬件每18.2个滴答是一秒，*/return0

4、;}/*time版本*/#include#include#includeintmain(void){time_tstart,end;inti,j;-33-doublek;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("Thetimewas:%f",difftime(end,start));return0;}⑷通过分析对比，得出自

5、己的结论。提示:下列程序可实现求出n的质因数的个数number.并可求出n的质因数。for(i=2;i<=n;i++){while(n>=i){if(n%i==0){number++;n=n/i;}elsebreak;}}/*计算n有多少个质因数*/-33-实验结果（可续页）（1）欧几里得算法计数法：源代码：#include#include#include#includeintEuclid(intm,intn){intr;while(n!=0){r=m%n;m=n;n=r;}returnm;}i

6、ntmain(void){intm,n;doublet1,t2;scanf("%d%d",&m,&n);t1=clock();printf("%d",Euclid(m,n));t2=clock();printf("Ittakes%lf",(t2-t1)/CLK_TCK);return0;}-33-#include#include#include#includeintEuclid(intm,intn){intr;while(n!=0){r=m%n;m=n;n=r;}returnm;}intmai

7、n(void){intm,n;time_tstart,end;scanf("%d%d",&m,&n);start=time(NULL);printf("%d",Euclid(m,n));end=time(NULL);printf("Thetimewas:%f",difftime(end,start));return0;}（2）连续整数检测算法计数法：源代码：#include#include#include#includeintgcd(intm,intn){intt;-33-if(m>n)

8、t=n;e