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

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

1、常熟理工学院《算法分析与设计》实验指导与报告书__________学年第____学期专业：____软件工程（服务外包_）__________学号：____Y12309218______________________姓名：______施伟杰______________________实验地点：______N6-113______________________指导教师：____________刘在德_________计算机科学与工程学院2011.0215实验目录实验1求最大公约数2实验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(GreatestCommonDivisor)；（2）掌

3、握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。预习内容P21.1什么是算法算法是一系列解决问题的清晰指令，也就是说，对于符合一定规范的输入，能够在有限时间内获得所要求的输出。实验内容（1）设计出3个版本的求最大公约数的算法；（2）采用C/C++实现算法，利用计数法记录基本语句的执行次数；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）欧几里得算法：#include

4、io.h>#includeintmain(){intn,r,m;printf("inputtwonum:");scanf("%d%d",&m,&n);while(n!=0){r=m%n;m=n;n=r;}printf("最大公约数为%d",m);return0;}15连续整数检测算法：#include#includeintmain(){intn,t,m;printf("inputtwonum:");scanf("%d%d",&m,&n);if

5、(m>n)t=n;elset=m;while((m%t)!=0

6、

7、(n%t)!=0){t=t-1;}printf("最大公约数为%d",t);}15教师评分实验2斐波那契数列实验目的（1）求斐波那契数列；（2）区分递归和递推思想。预习内容P602.5例题：斐波那契数列实验内容（1）至少设计出3个版本的求斐波那契数列的算法；（2）采用C/C++实现算法；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）1.递归计算法#includeintma

8、in(){longintfib[61]={0,1};inti;for(i=2;i<61;i++)fib[i]=fib[i-1]+fib[i-2];for(i=1;i<61;i++)printf("F%d=%dt",i,fib[i]);return0;}152.迭代计算法#includeintf(intn);intmain(){intn;scanf("%d",&n);f(n);}intf(intn){inti,f1=1,f2=1,f3;if(n<=0){printf("输入错误.

9、n");}elseif(n==1

10、

11、n==2){printf("1");}else{for(i=0;i#includeintmain(){intn,f;printf("输入n：");scanf("%d",&n);f=pow(((1+sqrt(5))/2.0),n)/sqrt(5)-pow(((1-sqrt(5))/2.0),n)/sq

12、rt(5);printf("%d",f);}教师评分实验3最近对问题15实验目的（1）设p1=(x1,y1)，p2=(x2,y2)，…，pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对；（2）进一步掌握递归算法的设计思想以及递归程序的调试技术；（3）理解此观点：分治和递归经常同时应用在算法设计中。预习内容P1134.6.1最近对问题实验内容（1）用分治法求解最近对问题；（2）采用C/C++实现算法，利用计数法记录基本语句的执行次数；（