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

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

1、常熟理工学院《算法分析与设计》实验指导与报告书____2011-2012______学年第__1__学期专业：软件工程(服务外包)091班学号：Y12309140姓名：___________浦菊敏___________实验地点：__________N6-113_______________指导教师：________刘在德_________计算机科学与工程学院2011.0215实验目录实验1求最大公约数2实验2斐波那契数列3实验3最近对问题4实验4堆排序5实验5霍纳法则和二进制幂6实验6字符串匹配问题7实验7War

2、shall算法和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）通过分析对比，得出结论。实验结果（可续页）1、欧几里德算法程序#includevoidmain(){intm,n,r;printf("pleaseenterthetwonumer.");scanf("%d%d",&m,&n);r=m%n;while(r!=0){m=n;n=r;r

4、=m%n;}printf("Thegreatestcommondivisoris%d.",n);}//执行了次。2、连续整数检测算法#includeintmin(m,n);intmin(m,n)15{if(m<=n)returnm;elsereturnn;}voidmain(){intm,n,t;printf("pleaseenterthetwonumer.");scanf("%d%d",&m,&n);t=min(m,n);for(;;){if((m%t==0)&&(n%t==0)){p

5、rintf("It's%d.",t);break;}t--;}}//执行了次。3、分解质因数程序#includeintmin(m,n);intmin(m,n){if(m<=n)returnm;elsereturnn;}voidmain(){intm,n,t;printf("pleaseenterthetwonumer.");scanf("%d%d",&m,&n);15t=min(m,n);for(;;){if((m%t==0)&&(n%t==0)){printf("It's%d.",

6、t);break;}t--;}}*/#includeintzhishu(m){inti,r;if(m<=2)return1;for(i=2;i

7、r];returns;}15voidmain(){intm,n,s;printf("Pleaseenterthetwonumber.");scanf("%d%d",&m,&n);s=gcd(m,n);printf("It's%d.",s);}//执行了次。教师评分实验2斐波那契数列实验目的（1）求斐波那契数列；（2）区分递归和递推思想。预习内容P602.5例题：斐波那契数列实验内容（1）至少设计出3个版本的求斐波那契数列的算法；（2）采用C/C++实现算法；（3）采用大O符号分析3种算法的时间复杂性；（4

8、）通过分析对比，得出结论。实验结果（可续页）15教师评分实验3最近对问题实验目的（1）设p1=(x1,y1)，p2=(x2,y2)，…，pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对；（2）进一步掌握递归算法的设计思想以及递归程序的调试技术；（3）理解此观点：分治和递归经常同时应用在算法设计中。预习内容P1134.6.1最近对问题实验内