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

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

1、《算法分析与设计》实验指导与报告书实验目录实验1求最大公约数2实验2斐波那契数列3实验3最近对问题4实验4堆排序5实验5霍纳法则和二进制幂6实验6字符串匹配问题7实验7Warshall算法和Floyd算法8实验8最优二叉查找树9实验9Huffman编码*10实验10求解非线性方程*11实验11投资问题*12注：（1）实验4和实验5为变治法应用，二选一；（2）实验7和实验8为动态规划法应用，二选一；（3）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。15实验1求最大公约数实验目的（1）求两个自然数m和n的GCD(Great

2、estCommonDivisor)；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。预习内容P21.1什么是算法实验内容（1）设计出3个版本的求最大公约数的算法；（2）采用C/C++实现算法，利用计数法记录基本语句的执行次数；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）欧几里得最大公约数算法：#includeintmain(){inta,b,c;printf("Pleaseinp

3、uttwointegers:");scanf("%d%d",&a,&b);15if(aintmain(){inta,b,t;printf("Pleaseinputtwointegers:");scanf("%d%d",&a,&b);if(a=1){if((a%t==0)&&(b%t==0

4、))break;t--;}printf("%d",t);return0;15}相减循环：#includeintmain(){intm,n;printf("Pleaseinputtwointegers:");scanf("%d%d",&m,&n);while(m!=n)if(m>n)m=m-n;elsen=n-m;printf("%d",m);return0;}教师评分实验2斐波那契数列15实验目的（1）求斐波那契数列；（2）区分递归和递推思想。预习内容P602.5例题：斐波那契数列实验内容（1）至少设计出3个版本的求

5、斐波那契数列的算法；（2）采用C/C++实现算法；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）迭代法#includeintf(intn);intmain(){intn;scanf("%d",&n);f(n);}intf(intn){inti,f1=1,f2=1,f3;if(n<=0){printf("输入错误.");}elseif(n==1

6、

7、n==2){printf("1");}else{for(i=0;i

8、15f2=f1;f1=f3;}printf("%d",f1);}}递归法#includeintmain(){intfib[41]={0,1};inti;for(i=2;i<41;i++)fib[i]=fib[i-1]+fib[i-2];for(i=1;i<41;i++)printf("F%d=%d",i,fib[i]);return0;}公式法#include#include#include15#defineROOT_OF_FIVEsqrt(5.0)int

9、F(intn){return(pow(((1+ROOT_OF_FIVE)/2.0),n)/ROOT_OF_FIVE-pow(((1-ROOT_OF_FIVE)/2.0),n)/ROOT_OF_FIVE);}intmain(){intn;printf("pleaseinputn:");scanf("%d",&n);printf("%d",F(n));return0;}通过本次实验我了解到递归方法简洁而且容易理解，不过时间复杂度太大，随着n的增大，运算时间将也会不断增加。迭代法相对递归来说时间复杂度上减小了不少，但是代码相对要复杂的多

10、。公式法的时间复杂度上比前2种方法都要小。教师评分实验3最近对问题15实验目的（1）设p1=(x1,y1)，p2=(x2,y2)，…，pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对；（