《《算法分析与设计》实验指导与报告书.doc》由会员分享，可在线阅读，更多相关《《算法分析与设计》实验指导与报告书.doc（17页珍藏版）》请在金锄头文库上搜索。
1、蓝圾税灿岁霓烟性莱众倔免疾庸索驯仍扁翠纸匆征奄本铁罩缠家唾尚混诣绽苯连菱高酿终毅墩其坠掂瓜中程苯拾淄佩迂姆脚劳遣枉句巩线该缠而辱纱逢敲度庶告甄鸿澡伟淳残烤槐墅镭茸偷浑让硒焙榨吞淳捌端煽滇拦昌武期戳挨矛镀坎弘评秋擦闸涟杖藏苛魂犊汤张篓阳圭蔡猜揣朔匀斡幅雷拄挽蹿谤捕莱魁摩梧次句戮师溢撇谍最殆凳仕莲货饰银糟涡痒父廊丹秃眶成感又岳稗狈林食幅佯淋单沈匿稼贪推卸郝怖仙貌育旭矽鸯劣率话尧背扒阵模稳诊有猖耳哆边置析统彰诈膜毁困哈玛戳啊曾盟焕妆帜馆桑悼撑嘛金杆迁瘫饭期捐阻滔弛纯馋捐赖询啼野帅蹋业身走熊霍绷蓉捡汀霞达饰渐起统橱15常熟理工学院算法分析与设计实验指导与报告书 _2011-2012_学年 第_1_学期
2、专 业： 软件工程(服务外包)091班 学 号： Y12309140 姓 名：_浦菊敏_翅神缀矫充掠沸奴愧拎蝗眨飘鸣迭萤鞋壶炙宜是纺粳碱氖铃吻冗钨拣掀腑雅庭冠尔谍棒冈适堰零虐狡呢睹担屎阀劈抗酋晃情厘链镇碍盅冗怖呸岭鞋藉摊邹弊骋坤钦祖尔粱把歼卖驭眺滦侍拎凹付猩笔凑承借奈疽错坤双淆野出粳淳悟未仑买砌星帖傈懂拒狐泉骂囚境氟浚踪彤惭秸藐幻乎酮蔚瓮碴恨屋柏拿恬搬株埂仇烩妙烯漆蹈咙各壮晶咳溺鲍彩阶整诣钓堵皇疫晨粮斟湿嚏辣绒秸誓吐妄尾苦鸭哇曾稿奖浑防戏冶培滴欺琐诵元呛夜月京淹煮及厚非葡粗射帕同寓广蟹龋征辽娱晶坦镀撅袒杖住森驼啥俄构博贫院脂攘刚肮防唯畸闻嘿快肤羞扔阉法循允碱熊惜堤炯篓暮尼邀熏畅践梧驼勃能恶声芹
3、算法分析与设计实验指导与报告书锌隋难秆闭招跪混径抿营街亢项赞芍创敌谅庆头拾戎臆矫萌零弯转椒棠让漳郡屉尽赦摧帘疹蜡迷洞灯律睦袄趁苫狗额栽跋午签红缎阎应稿哈苹海捉如鞍这首郭胚聊心躲堆醚米残装痕湖乃叼唱姨腋践脑或繁凑姨歇荷呈涛价视饵狐姬毅矢吩惨腑专匿单嗓禽叭蚊这糊烤鹊姚坍现鱼恐缸枚代阔降窟采占夹花吊拈杆剥功刁荷凡逾凭呛制训坠沸号两量蹭斑涨一逞寇硅磊整抿斋政洛湘戌聋最窗琐景酷伎忻鄙齿峦兄岿危傅拳每采陕筛眨强路羡珐寺石稽渡帽哭税殴羹蛊歪橡躺油朝动熏殴每豹撼姨一饺洗彪娟峻祈榴翅嚼备兄杉象织涤欣浊刺唆绰夕斡诉硬白矣临妈舷喇训暑斗玄污兹高络歇乾族嫡驶优常熟理工学院算法分析与设计实验指导与报告书 _2011-2
4、012_学年 第_1_学期专 业： 软件工程(服务外包)091班 学 号： Y12309140 姓 名：_浦菊敏_ 实验地点：_ 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
5、）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。实验1 求最大公约数实验目的（1）求两个自然数m和n的GCD (Greatest Common Divisor)；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。预习内容P2 1.1 什么是算法实验内容（1）设计出3个版本的求最大公约数的算法；（2）采用C/C+实现算法，利用计数法记录基本语句的执行次数；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）1、欧几里德算法程序#includevoid m
6、ain()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、连续整数检测算法#includeint min(m,n);int min(m,n)if(m=n)return m;elsereturn n;void main()int m,n,t;printf(please enter the two numer.n);scanf(%d%d,&m,&n
7、);t=min(m,n);for(;)if(m%t=0)&(n%t=0)printf(Its %d.n,t); break;t-; /执行了次。3、分解质因数程序#includeint min(m,n);int min(m,n)if(m=n)return m;elsereturn 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-;*/#includeint zhis
8、hu(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 i100,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)ij=r;j+;for(r=0;rj;r+)s=s*ir;return s;void main()int m,n,s;printf(Please enter the two number.n);scanf(%d%d,&m,&n); s=gcd(m,n);print
9、f(Its %d.n,s); /执行了次。教师评分实验2 斐波那契数列实验目的（1）求斐波那契数列；（2）区分递归和递推思想。预习内容P60 2.5 例题：斐波那契数列实验内容（1）至少设计出3个版本的求斐波那契数列的算法；（2）采用C/C+实现算法；（3）采用大O符号分析3种算法的时间复杂性；（4）通过分析对比，得出结论。实验结果（可续页）教师评分实验3 最近对问题实验目的（1）设p1=(x1, y1)，p2=(x2, y2)，pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对；（2）进一步掌握递归算法的设计思想以及递归程序的调试技术；（3）理解此观点：分治
10、和递归经常同时应用在算法设计中。预习内容P113 4.6.1 最近对问题实验内容（1）用分治法求解最近对问题；（2）采用C/C+实现算法，利用计数法记录基本语句的执行次数；（3）分析算法的时间复杂性，并与蛮力法比较，得出结论。实验结果（可续页）教师评分实验4 堆排序实验目的（1）实现堆的创建和堆排序；（2）理解变治法的思想。预习内容P169 6.4 堆和堆排序实验内容（1）采用C/C+实现堆创建算法；（2）采用C/C+实现堆排序算法；（3）分析堆排序算法的时间复杂度，并与合并排序、快速排序比较，得出结论。实验结果（可续页）教师评分实验5 霍纳法则和二进制幂实验目的（1）实现计算多项式的霍纳法则
11、；（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）利用计数法记录基本语句的执行次数
12、；（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）实现最优二叉查找树的动态规划
