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

1、算法分析与设计实验指导与报告书学年第学期专 业：软件工程（服务外包_）学 号： y12309218姓 名：施伟杰实验地点：n6-113指导教师：刘在德计算机科学与工程学院2011.02实验目录实验1求最大公约数2实验2斐波那契数列4实验3最近对问题6实验4堆排序7实验5霍纳法则和二进制慕8实验6字符串匹配问题9实验7war shall算法和floyd算法10实验8最优二叉查找树11实验9huffman编码*12实验10求解非线性方程*13实验11投资问题*14注：（1）实验4和实验5为变治法应用，二选一；（2）实验7和实验8为动态规划法应用，二选一；（3）带*号的实验为选做实验，根据课时及学牛

2、实验完成情况机动安排。实验1求最大公约数实验目的(1) 求两个自然数 m 和 n 的 gcd (greatest common divisor)；(2) 掌握并应用算法的数学分析和质验分析方法；(3) 理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同， 时间复朵性也不同。预习内容p2 1. 1什么是算法算法是一系列解决问题的清晰指令，也就是说，对丁符合一定规范的输入，能够在有限 时间内获得所要求的输出。实验内容(1) 设计出3个版本的求最大公约数的算法；(2) 采用c/c+实现算法，利用讣数法记录基本语句的执行次数；(3) 采用大。符号分析3种算法的时间复朵性；(4) 通过

3、分析对比，得出结论。实验结果(可续页)欧儿里得算法：#include <stdio.h>#include <stdlib.h>int main()int n,r,m;prinlf("input two num:");scanf("%d%dn,&m,&n);while(n!=0)r=m%n;m=n;n=r;printf("最大公约数为%d”,m);return 0;连续整数检测算法:#include <stdio.h>#include <stdlib.h> int main()int n,t,

4、m;printf(ninput two num:”)； scanf(,%d%d,&m,&n); if(m>n)t=n;elset=m;while(m%t) !=0 ii (n%t)!=o) t=t-l;printf(”最大公约数为%d",t);教师评分实验2斐波那契数列实验目的(1) 求斐波那契数列；(2) 区分递归和递推思想。预习内容p60 2.5例题：斐波那契数列实验内容(1) 至少设计出3个版本的求斐波那契数列的算法;(2) 采用c/c+实现算法；(3) 采用大0符号分析3种算法的时间复杂性；(4) 通过分析对比，得出结论。实验结果(可续页)1. 递归计算

5、法#includc <stdio.h>int main()long int fib61 = 0,1;int i;for(i=2;i<61;i +)fibi = fibi-l+fibi-2;for(i=l;i<61;i+)printf(mf%d=%dtm,i,fibi);return 0;fl=lf2=lf3=：?f4=3f5=sif6=8f7=13f8=21f9=34f10=55tfll89f12=144f13233 f14=377f15610 f16=98?fl?1597f182584f194181f206765f2110946f2217711f2328657f244

6、6368f2575025f26121393f2?196418f28317811f29514229f30832040f311346269f322178309f333524578f345702887f359227465f3614930352f3724157817f3839088169f3963245986f40102334155f41165580141f42267914296f43433494437f44701408733f451134903170f461836311903f47-1323752223f48512559680f49-811192543f50-298632863f51-1109825

7、406f52-1408458269f531776683621f54368225352f552144908973f56-1781832971f57363076002f58-1418756969f59-1055680967f601820529360process returned 0 <0x0>execution time : 0.172 spress any key to continue.d:codelajiduiuntitledl.exe= 回2. 迭代计算法#include<stdio.h> int f(int n);int main()int n; scanf(”

8、d",&n);f(n)； int f(int n)int i,fl=l,f2=l,t3;if(n<=0)pri ntf( ”输入错误 an ”);else if(n=llln=2)printf(t“);elsefor(i=0;i<n-2;i+)f3=fl+f2;f2=fl;fl=f3;printf(”dn“,fl);实验3最近对问题（1）设"1=（x1,yi）,卩2=（兀2*2），,pn=dn,yn）是平面上口个点构成的集合s,设计算法 找出集合s中距离最近的点对；（2）进一步掌握递归算法的设计思想以及递归程序的调试技术；（3）理解此观点：分治和递归经常

9、同时应用在算法设计中。预习内容p113 4. 6. 1最近对问题实验内容（1）用分治法求解最近对问题；（2）采）i c/c+实现算法，利用计数法记录慕本语句的执行次数;（3）分析算法的时间复杂性，并与蛮力法比较，得出结论。实验结果（可续贝）教师评分(1) 实现堆的创建和堆排序;(2) 理解变治法的思想。预习内容p169 6.4堆和堆排序实验内容(1) 采用c/c+实现堆创建算法；(2) 采用c/c+实现堆排序算法；(3) 分析堆排序算法的时间复朵度，并与合并排序、快速排序比较，得出结论。实验结果(可续贝)教师评分（1）实现计算多项式的霍纳法则；（2）实现从左至右和从右至左二进制幕算法;（3）理

10、解变治法的思想。预习内容p176 6.5霍纳法则和二进制幕实验内容（1）采用c/c+实现计算多项式的霍纳法则；（2）采用c/c+实现计算a”的从左至右和从右至左二进制幕算法;（3）分析崔纳法则的时间复杂度，并与蛮力法比较，得出结论。实验结果（可续贝）教师评分（1）给定一段文本，在该文本中查找并定位任意给定字符串;（2）深刻理解并掌握时空权衡的设计思想。预习内容p194 7.2字符串匹配中的输入增强技术实验内容（1）采用c/c+实现bm算法的简化算法：horspool算法；（2）利用计数法记录基本语句的执行次数；（3）分析horspool算法的时间复杂度，并与蛮力法比较，得出结论。实验结果（可续

11、贝）教师评分实验7war shall算法和floyd算法1=1（1）实现计算有向图传递闭包的warshall算法;（2）利用floyd算法计算图的完全最短路径；（3）深刻理解并掌握动态规划法的设计思想。预习内容p216 8. 2 warshall 算法和 flovd 算法实验内容（1）采用c/c卄实现算法，禾用计数法记录基本语句的执行次数;（2）采用大殆号分析2种算法的时间复杂性；（3）通过对2种算法的分析对比，找出的它们的相似处。实验结果（可续贝）教师评分（1）实现最优二叉査找树的动态规划算法；（2）深刻理解并学握动态规划法的设计思想。预习内容p223 8.3最优二叉查找树实验内容（1）采用

12、c/c+实现最优二叉查找树的动态规划算法；（2）根据实现的代码给出至少含5个键的最优二叉树的主表和根表，并根据根表画出最 优二义查找树；（3）分析算法的时间复杂度。实验结果（可续页）教师评分（1）设需要编码的字符集为必込，如，出现的概率为w】,w2,叫,应用huffman 树构造最短的变长编码方案；（2）了解前缀编码的概念，理解数据压缩的基本方法；（3）掌握贪心法的设计思想并熟练运用。预习内容p250 9.4呛夫曼树实验内容（1）设计贪心算法求解huffman编码方案;（2）采用c/c+实现算法；（3）分析算法的时间复杂性。实验结果（可续贝）教师评分(1) 采用平分法、试位法和牛顿法求解非线性方程;(2) 理解近似算法求解某些问题的思路。预习内容p34212.4解非线性方程的算法实验内容(1) 采用c/c+实现求方程近似解的平分法、试位法和牛顿法;(2) 分析三种算法的时间复杂度，