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

常熟理工学院算法分析与设计实验指导与报告书 _学年 第_学期专 业：_软件工程（服务外包_）_学 号：_Y12309218_姓 名：_施伟杰_实验地点：_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）通过分析对比，得出结论。实验结果（可续页）欧几里得算法：#include #include int main() int n,r,m; printf(input two num:); scanf(%d%d,&m,&n); while(n!=0) r=m%n; m=n; n=r; printf(最大公约数为%d,m);return 0;连续整数检测算法：#include #include int main() int n,t,m; printf(input two num:); scanf(%d%d,&m,&n); if(mn) t=n; else t=m; while(m%t)!=0 | (n%t)!=0) t=t-1; printf(最大公约数为%d,t);教师评分实验2 斐波那契数列实验目的（1）求斐波那契数列；（2）区分递归和递推思想。预习内容P60 2.5 例题：斐波那契数列实验内容（1）至少设计出3个版本的求斐波那契数列的算法；（2）采用C/C+实现算法；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）1.递归计算法#include int main() long int fib61 = 0,1; int i; for(i=2;i61;i+) fibi = fibi-1+fibi-2; for(i=1;i61;i+) printf(F%d=%dt,i,fibi); return 0;2.迭代计算法#includeint 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;in-2;i+) f3=f1+f2; f2=f1; f1=f3; printf(%dn,f1); 3.公式法#include#includeint main() int n,f; printf(输入n：); scanf(%d,&n); f = pow(1 + sqrt(5)/2.0),n)/sqrt(5) - pow(1 - sqrt(5)/2.0),n)/sqrt(5); printf(%d,f);教师评分实验3 最近对问题实验目的（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 堆排序实验目的（1）实现堆的创建和堆排序；（2）理解变治法的思想。预习内容P169 6.4 堆和堆排序实验内容（1）采用C/C+实现堆创建算法；（2）采用C/C+实现堆排序算法；（3）分析堆排序算法的时间复杂度，并与合并排序、快速排序比较，得出结论。实验结果（可续页）教师评分实验5 霍纳法则和二进制幂实验目的（1）实现计算多项式的霍纳法则；（2）实现从左至右和从右至左二进制幂算法；（3）理解变治法的思想。预习内容P176 6.5 霍纳法则和二进制幂实验内容（1）采用C/C+实现计算多项式的霍纳法则；（2）采用C/C+实现计算an的从左至右和从右至左二进制幂算法；（3）分析霍纳法则的时间复杂度，并与蛮力法比较，得出结论。实验结果（可续页）教师评分实验6 字符串匹配问题实验目的（1）给定一段文本，在该文本中查找并定位任意给定字符串；（2）深刻理解并掌握时空权衡的设计思想。预习内容P194 7.2 字符串匹配中的输入增强技术实验内容（1）采用C/C+实现BM算法的简化算法：Horspool算法；（2）利用计数法记录基本语句的执行次数；（3）分析Horspool算法的时间复杂度，并与蛮力法比较，得出结论。实验结果（可续页）教师评分实验7 Warshall算法和Floyd算法实验目的（1）实现计算有向图传递闭包的warshall算法；（2）利用Floyd算法计算图的完全最短路径；（3）深刻理解并掌握动态规划法的设计思想。预习内容P216 8.2 Warshall算法和Floyd算法实验内容（1）采用C/C+实现算法，利用计数法记录基本语句的执行次数；（2）采用大O符号分析2种算法的时间复杂性；（3）通过对2种算法的分析对比，找出的它们的相似处。实验结果（可续页）教师评分实验8 最优二叉查找树实验目的（1）实现最优二叉查找树的动态规划算法；（2）深刻理解并掌握动态规划法的设计思想。预习内容P223 8.3 最优二叉查找树实验内容（1）采用C/C+实现最优二叉查找树的动态规划算法；（2）根据实现的代码给出至少含5个键的最优二叉树的主表和根表，并根据根表画出最优二叉查找树；（3）分析算法的时间复杂度。实验结果（可续页）教师评分实验9 Huffman编码*实验目的（1）设需要编码的字符集为d1,d2, dn，出现的概率为w1,w2,wn,应用Huffman树构造最短的变长编码方案；（2）了解前缀编码的概念，理解数据压缩的基本方法；（3）掌握贪心法的设计思想并熟练运用。预习内容P250 9.4 哈夫曼树实验内容（1）设计贪心算法求解Huffman编码方案；（2）采用C/C+实现算法；（3）分析算法的时间复杂性。实验结果（可续页）教师评分实验10 求解非线性方程*实验目的（1）采用平分法、试位法和牛顿法求解非线性方程；（2）理解近似算法求解某些问题的思路。预习内容P342 12.4 解非线性方程的算法实验内容（1）采用C/C+实现求方程近似解的平分法、试位法和牛顿法；（2）分析三种算法的时间复杂度，比较三种算法的优缺点。实验结果（可续页）教师评分实验11 投资问题*实验目的（1）有n项