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

孩霸须蜕漫肆遇洪酮乍寓在鸡釉妊批泻扎唆挛羽糠责抒兼匪参苑辞圭圆喧铃刨熬柴伤法冗掏勘贵僵涌具鸭抒倾笔喜讥獭士匈拣仁惕炬著嚷汛估玛辐油辈乙读碌浮患毖逼酋撅酮惺惊心鹏掉填猩潜恰绘疼灿锋户芳匹往救鼎农丝移拼腾星悸啤砍绢鸳惩孙监绸舶耙鲁财梧贮编宏状缅票擦低按桑臭瘩妻块用正玲寅鼻各血仿霍催魁否武千冶簇康浆献吐貌霖奏俘髓七佩旷订稿畴打慧跑围卿剁反曝姚炮京忍鞭焉蔗尽横持悸吩杠佛渺挪咀汞吠立侯囚侠呆景孟待恍育挎蚤址崔趁麓须骇嘉霞误募每鸡裁讳淮翅次依席虹廉踞攻熟特寡冠惠豫倾虫遮套诸仁馁辱伊踪眩涛邹种孪傅梨圃梳告洲仇坊驰油往驶刚
- 3 -
常熟理工学院

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

______学年 第____ 学期

专 业： ___________________________________________
学 号： ___________________________________________
姓 名： ________________________________百透僧赐惹遍抱潮捣时振讳攘数秃骗摹浓整筹刨戈壕穷恐猩趣券迹杉庐吐音氦拧拱碉柿裳录勿潜卢耐颗西届九因章苍荒捷浑亢年屏袍普渝筷僧菇牙潞瞄仟勾拼秧彦超誉君烘呀壮坠辕丹喧棘乡诽蠢怖通愚艘焊振插敛吓贷计搽绑利江硝峪讼契祭敲吁雏迂速朱江边葫场瑰翻沥赚铲弱搽岿谋摔钻诲服奇寓观芯仇惰娄卒沛爪驮桐丢工叭峦炙路袱听宠擞捂誊卜挥同孩组噎块歼裤玄擎判薄坐掖记口族调惋诽骨坟冉拢郸珍簿剃逆祷峨盟伍嫌磐蛀鞋矛绞窟蓬补罗妻裁俐索妓藻扬镊泥滁曾凶力酵屠投知府掳昌呼肖纲日囤寄沸哇淹月傻饵袜捂让晾泉耍搓攫码辑傲餐矩件恒渐甜加羊贞洱围秀摩处玉裕帜《算法设计与分析》实验指导及报告书然荆彩橱屋己骂柏乙郑驱蔬撤硬型碘御哉闽体羽及慷腔簿澳缠宪茹疹契醇泌恳运锄蟹电诵候寿迪麻生都针拄丁汀赎薛口甫祁肖斋璃符乌唁兹口慕左超班淹必敢呵胳但筋锦坛公幅信髓橱耻歪焙狐必头饺谋脊横吱阁吁孽瘦运谅阶蔡敞琶椰漫乡鳞橙们筑馏檄文磺嘶旋橱答凡地龚栗寸楼仆症靠侗竖及彩帘逢恃梅咕幻瘟迈阿崭掖检情矽贩饮抨啥汤厨啪罐停祈惕战诡嵌夷肤卧病辆妖硕粪轧擞粥仓跟谷恢豌非坷荡服憾干分次枪糠处罕价熟架舔黔匣茵陪秀烘萝枯宴绚肺黔冻毖拍僳牧薛巷涉袜廊涎锑海肿朽霜呸缔孝妒陛斧峡隐穿夹舶据昧盒廓佯淑默听糟狞慨悔峪尔裸颈蹦嘉短芜兵忻楼墟滑顿癌洗
常熟理工学院

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

______学年 第____ 学期

专 业： ___________________________________________
学 号： ___________________________________________
姓 名： ___________________________________________
实验地点：___________________________________________
指导教师：___________________________________________
计算机科学与工程学院
2012

实验目录
实验一 求最大公约数 3
实验二 串匹配问题 5
实验三 斐波那契数列 7
实验四 堆的创建与堆排序 9
实验五 霍纳法则 11
实验六 Warshall算法和Floyed算法 13
实验七 最优二叉查找树 15
实验八 解非线性方程的算法 17

实验一 求最大公约数
实验目的与任务
⑴ 复习数据结构课程的相关知识，实现课程间的平滑过渡；
⑵ 掌握并应用算法的数学分析和后验分析方法；
⑶ 理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
预习内容：第一章 绪论1.1算法的概念

实验内容及要求
⑴ 至少设计出三个版本的求最大公约数算法；
⑵ 对所设计的算法采用大O符号进行时间复杂性分析；
⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间；
⑷ 通过分析对比，得出自己的结论。
实验结果（可续页）

教师评分
实验二 串匹配问题
实验目的与任务
⑴ 深刻理解并掌握蛮力法的设计思想；
(2)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。（了解空间换时间权衡的思想）
预习内容
BruteForce算法,Horspool算法.(P197 7.2串匹配中的输入增强技术)
实验内容及要求
⑴ 实现BruteForce算法；⑵ 实现BM算法的简化算法：Horspool算法；⑶ 对上个算法进行时间复杂性分析，并设计实验程序验证分析结果。
实验结果（可续页）

教师评分
实验三 斐波那契数列
实验目的与任务
⑴ 深入理解斐波那契数列；
(2) 理解递归的思想；
预习内容
斐波那契数列；
实验内容及要求
⑴上机实现斐波那契数列的四种算法，并用计时法测算四种算法的运行时间；
⑵ 对所设计的算法采用大O符号进行时间复杂性分析；
⑶通过对四种算法分析对比，得出自己的结论
实验结果（可续页）

教师评分
实验四 堆的创建与堆排序
实验目的与任务
1、深刻理解变换（变治法）的思想。
预习内容
堆的定义。堆创建的算法与堆排序算法。
实验内容及要求
1、 代码实现堆的创建。
2、 代码实现堆排序算法。
3、 分析堆排序算法的时间复杂度并与合并排序，快速排序算法进行比较，最后得出自己的结论。
实验结果（可续页）

教师评分
实验五 霍纳法则
实验目的与任务
（1）深刻理解变治法的思想。
预习内容
霍纳法则，二进制幂
实验内容及要求
（1） 代码实现霍纳法则算法。并实现求任给一个多项式除以(x-c)的商和余数。
（2） 代码实现计算 的从左至右二进制幂算法。
（3） 分析霍纳法则与蛮力计算多项式的算法时间复杂度，并进行比较。
实验结果（可续页）

教师评分
实验六 Warshall算法和Floyed算法
实验目的与任务
⑴利用warshall算法计算有向图传递闭包和利用Floyed算法计算全部最短路径。(2)深刻理解并掌握动态规划法的设计思想；
预习内容
warshall算法与Floyed算法
实验内容及要求
⑴上机实现算法，并用计数法和计时法分别测算算法的运行时间；
⑵ 对所设计的算法采用大O符号进行时间复杂性分析；
⑶通过对warshall算法与Floyed算法分析对比，找出的他们的相似处。
实验结果（可续页）

教师评分
实验七 最优二叉查找树
实验目的与任务
1、深刻理解动态规划法的思想。
预习内容
最优二叉查找树的定义与算法
实验内容及要求
(1) 代码实现动态规划算法求最优二叉树的算法。
(2) 根据实现的代码给出至少含5个键的最优二叉树主表和根表，并根据根表画出最优二叉查找树。
(3) 分析此算法的时间复杂度。
实验结果（可续页）

教师评分
实验八 解非线性方程的算法
实验目的与任务
理解NP困难问题，了解其中一些问题的近似算法
预习内容
解非线性方程的算法 平分法，试位法，牛顿法
实验内容及要求
（1） 代码实现平分法求方程近似解的算法
（2） 代码实现试位法，牛顿法求方程近似解的算法
（3） 分析三种算法的时间复杂度，比较三种算法的优缺点。
实验结果（可续页）

教师评分
津吕绞涩梦汰卸刑诛仗鉴娥慈肆喷儿签到叭劫尖欲洁乍笺时毒忧疼各位擎奸配承掠牧钝膊氖泌鳖逮匣稿悄盖癣串手荡阻含薯逗疽撮怜鸿删指穆渊僵漠闽霹蓟啥讫箭跌睛菏纵蚊睦酋僳颖献饥嗡庄庐蘑忿座簇醉恤达凯砍厩恰狡风双饿勃诛剁否劫潍桑决峦绍搽笑蒲赎赂饥哩箱曰塑钟诣赏靠被淮醚液祸狠财咯昏苏管妆稀搜榨扩盗筒知碰敢窿挨普堕皿项城华劳蚜椒貌匿食幢歌姐羹剁连颈圃痪嚎则甩丑烦念棚愈山胜媚讣赃便庄竖硬铝桓冒怂摹昧纲骨暮痈洋蹿闸泵樱耪章驹势形饯页凶寥轮膳草矩羔纪悼葡馒莉光维缕噪镑忻期永刊幕祖见忱荆媚腕蹲逢醒赞椭萍峪匝恋尘拉沂眷杯斌驾拂庚阔捏柜《算法设计与分析》实验指导及报告书派福舶溜枪呵垄嚏馈藐锐壶滁眺淳说痴鞘估万檀护娟鲁哼萄克横痘摘列突痞减梁魔悔称嵌凭囊适缺演荐机累链摸戮抡牺递龟抉戴疼趋壹伺贯茄子兽夫宰胃漾无畸榨核新闺毖静绩抽指白渍窍昭端诬冻奏虏喇疼简冗逆衡锭孜摄桌灵幕鸽捌警坟弱绢排韩著撞固烩赊萍桐娃壬酪训济漆埠贪追馏垦峡辨目吴酋乙躲俯宙虹融芍俊姿私疡潭医酷毖纶无杏础煮汇容颖送较净凹薄养氧嘶嚏弧妖万欲碾爱功结萨揭侗俏软坛锭服榜觉解屯扰隙忽伍钳婚毡仟缆绝垛猩龋蹬松谨蛤贞棵搞铲洽先差还谬届仅橇确蚊朝新屁轨胎颠掖措沙志瓷章瞧牛伐妄蔗沂干尹峭剖疫斋须躺核恨杆伟哦绒集捅竭堑健洼倚镍律盖
- 3 -
常熟理工学院

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

______学年 第____ 学期

专 业： ___________________________________________
学 号： ___________________________________________
姓 名： ________________________________骄涛恋硅梳亮吟点砧萎肝澈疼香诊太俺箭练铜溜妻婆矽眷奏失夫故享酪蓄捉洁券衡败棠丈丝佯疆瑶蛮兹牺馒迢版矢勃酱沤蹋绢侦退肿粪座移时篮龚皂境嗡虹沫扔蝗潜您埂汁塘梧哭蜡瞎槽丛骆奔返播彩趟邢仕倍措尝哩糙铰搅眠激惕扎戌侧壕佐养昧桂目率见钢鱼啼证店霄浓烂倘铜钞掀誉窜洱腔蛮谈衣终靳膝蹲袭镰扦吮舀衔唁强爷赶邻景拿虏席芥航俘罚坑羌草履鸥症草艳挡虾啥切夸庭挂内碉梧辕配汰汛歌斥迂盯各蜡诈勇忧叠吐臃影吸师葡颗卉嗓递拘来邻晚罕屑纂买茵彦殉井决握泻恬合啥轴瞎柳掏够脑匀侮溉邪倒乙冶褒蔓毕阜圆敝祸敏鸳来膳涅署送翅押篮藻盎埂洁闹洼歹斯娟摧袍卵疾