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

《算法分析与设计》实验指导与报告书 实验目录 实验1 求最大公约数.................................................................................................................... 1 实验2 斐波那契数列.................................................................................................................... 3 实验3 最近对问题........................................................................................................................ 6 实验4 堆排序................................................................................................................................ 7 实验5 霍纳法则和二进制幂........................................................................................................ 8 实验6 字符串匹配问题................................................................................................................ 9 实验7 Warshall算法和Floyd算法 ........................................................................................ 10 实验8 最优二叉查找树.............................................................................................................. 11 实验9 Huffman编码* ................................................................................................................ 12 实验10 求解非线性方程*.......................................................................................................... 13 实验11 投资问题*...................................................................................................................... 14

注：（1）实验4和实验5为变治法应用，二选一； （2）实验7和实验8为动态规划法应用，二选一； （3）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。 1

实验1 求最大公约数 实验目的 （1）求两个自然数m和n的GCD (Greatest Common Divisor)； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。 预习内容 P2 1.1 什么是算法

实验内容 （1）设计出3个版本的求最大公约数的算法； （2）采用C/C++实现算法，利用计数法记录基本语句的执行次数； （3）采用大O符号分析3种算法的时间复杂性； （4）通过分析对比，得出结论。

实验结果（可续页）

欧几里得最大公约数算法： #include int main() { int a, b, c; printf("Please input two integers: "); scanf("%d %d", &a, &b); if(a2

{ c = a; a = b; b = c; } while(a % b != 0) { c = a % b; a = b; b = c; } printf("%d", b); return 0; }

连续整数检测算法最大公约数算法： #include int main() { int a,b,t; printf("Please input two integers: "); scanf("%d %d",&a,&b); if(at=a; else t=b; while(t>=1) { if((a%t==0)&&(b%t==0)) break; t--; } printf("%d",t); return 0; } 3

相减 循环： #include int main() { int m,n; printf("Please input two integers: "); scanf("%d%d",&m,&n); while(m!=n) if(m>n) m=m-n; else n=n-m; printf("%d",m); return 0; }

教师评分 实验2 斐波那契数列 实验目的 （1）求斐波那契数列； （2）区分递归和递推思想。 4

预习内容 P60 2.5 例题：斐波那契数列

实验内容 （1）至少设计出3个版本的求斐波那契数列的算法； （2）采用C/C++实现算法； （3）采用大O符号分析3种算法的时间复杂性； （4）通过分析对比，得出结论。

实验结果（可续页）

迭代法 #include int f(int n); int main()

{ int n; scanf("%d",&n); f(n); }

int f(int n) { int i,f1=1,f2=1,f3;

if(n<=0) { printf("输入错误.\n");

} else if(n==1||n==2) { printf("1"); } else { for(i=0;i{ f3=f1+f2; //f1表示当前的值 f2=f1; f1=f3; }

printf("%d\n",f1); 5

} }

递归法 #include int main() { int fib[41] = {0,1}; int i;

for(i=2;i<41;i++) fib[i] = fib[i-1]+fib[i-2]; for(i=1;i<41;i++) printf("F%d=%d\n",i,fib[i]);

return 0; }

公式法 #include #include #include #define ROOT_OF_FIVE sqrt(5.0) int F(int n) { return (pow(((1 + ROOT_OF_FIVE) / 2.0),n) / ROOT_OF_FIVE - 6

pow(((1 - ROOT_OF_FIVE) / 2.0),n) / ROOT_OF_FIVE); } int main() { int n; printf("please input n:\n"); scanf("%d",&n); printf("%d",F(n)); return 0; }

通过本次实验我了解到递归方法简洁而且容易理解，不过时间复杂度太大，随着n的增大，运算时间将也会不断增加。 迭代法相对递归来说时间复杂度上减小了不少，但是代码相对要复杂的多。 公式法的时间复杂度上比前2种方法都要小。

教师评分 实验3 最近对问题 7

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

实验内容 （1）用分治法求解最近对问题； （2）采用C/C++实现算法，利用计数法记录基本语句的执行次数； （3）分析算法的时间复杂性，并与蛮力法比较，得出结论。

实验结果（可续页）

教师评分 实验4 堆排序