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

常熟理工学院 《算法分析与设计》实验指导与报告书 ____2011-2012______学年 第__1__学期 专 业： 软件工程(服务外包)091班 学 号： 姓 名：___________浦菊敏___________ 实验地点：__________ N6-113 _______________ 指导教师：________ 刘在德 _________ 计算机科学与工程学院 2011.02 实验目录 实验1 求最大公约数 2 实验2 斐波那契数列 3 实验3 最近对问题 4 实验4 堆排序 5 实验5 霍纳法则和二进制幂 6 实验6 字符串匹配问题 7 实验7 Warshall算法和Floyd算法 8 实验8 最优二叉查找树 9 实验9 Huffman编码* 10 实验10 求解非线性方程* 11 实验11 投资问题* 12 注：（1）实验4和实验5为变治法应用，二选一； （2）实验7和实验8为动态规划法应用，二选一； （3）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。 实验1 求最大公约数 实验目的 （1）求两个自然数m和n的GCD (Greatest Common Divisor)； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。 预习内容 P2 1.1 什么是算法 实验内容 （1）设计出3个版本的求最大公约数的算法； （2）采用C/C++实现算法，利用计数法记录基本语句的执行次数； （3）采用大O符号分析3种算法的时间复杂性； （4）通过分析对比，得出结论。 实验结果（可续页） 1、欧几里德算法程序 #includestdio.h void main() { int m,n,r; printf(please enter the two numer.\n); scanf(%d%d,m,n); r=m%n; while(r!=0) { m=n; n=r; r=m%n; } printf(The greatest common divisor is %d.\n,n); } //执行了次。 2、连续整数检测算法 #includestdio.h int min(m,n); int min(m,n) { if(m=n) return m; else return n; } void main() { int m,n,t; printf(please enter the two numer.\n); scanf(%d%d,m,n); t=min(m,n); for(;;) { if((m%t==0)(n%t==0)) { printf(Its %d.\n,t); break; } t--; } } //执行了次。 3、分解质因数程序 #includestdio.h int min(m,n); int min(m,n) { if(m=n) return m; else return n; } void main() { int m,n,t; printf(please enter the two numer.\n); scanf(%d%d,m,n); t=min(m,n); for(;;) { if((m%t==0)(n%t==0)) { printf(Its %d.\n,t); break; } t--; } } */ #includestdio.h int zhishu(m) { int i,r; if(m=2) return 1; for(i=2;im;i++) { r=m%i; if(r==0) return 0; } return 1; } int gcd(m,n) { int i[100],r,j=0,s=1; for(r=1;r=m/2;r++) { if(zhishu(r)==0) continue; else if((m%r==0)(n%r==0)) { i[j]=r; j++; } } for(r=0;rj;r++) s=s*i[r]; return s; } void main() { int m,n,s; printf(Please enter t