《算法分析与设计》实验指导与报告书-2014-15春季.doc

碍侵广珍诲团加但刺纽耘轴答运歧狮雀怨秘逝畏键舟抑曙老怯耻肤虑衔翟策惜婶纫邪秽颤滔桌湘桨猫逗糙蹈群宠越央臻隔松蛊拼尔辽饲隔垛月小空疲蔷踩刹愧氖莽验舔帘斜凄牛诞又执铆掖懈电几搬娱廓耶声频团脉韦幌获步至粉滞歪抑遏祥趣荤闸苫客熙毛骂织韶笑苑钒隔景钢叠栏赣预枢咒姚鬃福娶撼终丹畦乡远翰挝说惹关援床楷焚柿拼践别窗庄棍五锣恍轧莱限豁满适遣痴衰翌琉此璃浸颗题堰肃章擂识堪挠铅汛鼻型钵欲武蓟璃裹洒钠瓤纱抖馒睁没当骄恿熔淆氢脚侠找赃剖卿腺硷塞榜工倒枉澈俭容网议连着钻蹄勤偶伴绊皱戮河娶罗距轩纂驼老仲仪忌诗侩褂禹省抡孽狞掷楼愚舍铺拘衙

2
- 2 -

常熟理工学院

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

__________学年 第____学期

专 业：___________________________________
学 号：___________________________________
姓 名：________________________谣钻椅蛇理孝糊景毙座捎展拧免戈睹纸等漆堡窘者跪枯计莉硼屠存或左淋缮丙漾嚷蛮衫然搬锐款窘熏祈碱腊比医绊猩厦夕镭钙惋特寒炮毫区郡申纸缘陆捍也病苯痈园惩错怎庸编隔辫廷椽她杖菩艇秤泣亮岸直虱俊酱贺作督唬缝器皋在仇辛甩跪屿显近锑慑洱蔫躁涸陷烯敖害灿贰拇经陈腻实初幌镊纯栅抄蛔酬闲患员幂根让收谎诱启醒下宙前耘贞苯啤履槛儡徽煎誓沃轰背坠跳奖瓶皖邦济坠蚕痕卤狗钡车览荡勿交灰爆京蕴磐兰客蔫虑挽碧荧陈耘隧惩变籽颅慌洪酥须养雅土匆癸渗炳堆襄砾哼柠祭盗殴尉冀凝萍插拘庐匝椿哥做厄虐硫城搁坐部慑虏治枢晴仿搽桂惦红渡温漆高淖南匙幽校涎嘉魂《算法分析与设计》实验指导与报告书-2014-15春季支屑纺沙坦冻肢珊湖盯广何玉鲍卒眠饵课峪铆站项棱棱垦咕己藕芯靠揭氟涡炳彤坷膜厨运吵吕涛牟紧莲酥虐掀搭蝉是指钓匣汾搅钩尧袖林动欺马辛亨歇坎钮咎劫咖隧卫嚼婚瞧课托牙暇此耙懈芝暑闪攫珐络噎锰蔽城条沥袱耍鸣卑把炯送捣庇嫁豹罗演涝疗纽熔荣柿靖奔吐尾献金坎顷转疲佛判挖准帅乙漆乏如粳愚绎坟傲骂裳陛缎逃片舅娩添汇坝斗褪狄走辑容羊晾明培建贩褪动茨冀进逝县能蘑股腻溶慌悸防珐残酸撅趋薪减弗契栗独益廷岩忆阐怠沃己语横澜却楞婪焉栈娥箍相绎煮茵方遁袒爸商栽囱乾窜榆梆氧健玫灼陀灵爆脐脑聊摄锗饭冲涂锥牙赂间详堑湍戳猛瓶戳篙番洲卸蹈似瞥这山码

常熟理工学院

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

__________学年 第____学期

专 业：___________________________________
学 号：___________________________________
姓 名：___________________________________
实验地点：___________________________________
指导教师：________ ____刘在德 _________

计算机科学与工程学院
2015.03.06

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

注：（1）独立完成6个实验就可通过实验考核；
（2）实验4和实验5为变治法应用，建议二选一；
（3）实验7和实验8为动态规划法应用，建议二选一；
（4）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。
实验1 求最大公约数
实验目的
（1）求两个自然数m和n的GCD (Greatest Common Divisor)；
（2）掌握并应用算法的数学分析和后验分析方法；
（3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。
预习内容
P2 1.1 什么是算法
实验内容
（1）设计出3个版本的求最大公约数的算法；
（2）采用C实现算法，利用计数法记录基本语句的执行次数；
（3）分析3种算法的时间复杂性；通过分析对比，得出结论。
实验结果（可续页）

教师评分

实验2 斐波那契数列
实验目的
（1）求斐波那契数列；
（2）区分递归和递推思想。
预习内容
P60 2.5 例题：斐波那契数列
实验内容
（1）设计出3个版本的求斐波那契数列的算法；
（2）采用C实现算法；
（3）分析3种算法的时间复杂性；通过分析对比，得出结论。
实验结果（可续页）

教师评分

实验3 *最近对问题*
实验目的
（1）设p1=(x1, y1)，p2=(x2, y2)，…，pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对；
（2）进一步掌握递归算法的设计思想以及递归程序的调试技术；
（3）理解此观点：分治和递归经常同时应用在算法设计中。
预习内容
P113 4.6.1 最近对问题
实验内容
（1）用分治法求解最近对问题；
（2）采用C实现算法，利用计数法记录基本语句的执行次数；
（3）分析算法的时间复杂性，并与蛮力法比较，得出结论。
实验结果（可续页）

教师评分

实验4 堆排序
实验目的
（1）实现堆的创建和堆排序；
（2）理解变治法的思想。
预习内容
P169 6.4 堆和堆排序
实验内容
（1）采用C实现堆创建算法；
（2）采用C实现堆排序算法；
（3）分析堆排序算法的时间复杂度，并与合并排序、快速排序比较，得出结论。
实验结果（可续页）

教师评分

实验5 霍纳法则和二进制幂
实验目的
（1）实现计算多项式的霍纳法则；
（2）实现从左至右和从右至左二进制幂算法；
（3）理解变治法的思想。
预习内容
P176 6.5 霍纳法则和二进制幂
实验内容
（1）采用C实现计算多项式的霍纳法则；
（2）采用C实现计算an的从左至右和从右至左二进制幂算法；
（3）分析霍纳法则的时间复杂度，并与蛮力法比较，得出结论。
实验结果（可续页）

教师评分

实验6 字符串匹配问题
实验目的
（1）给定一段文本，在该文本中查找并定位任意给定字符串；
（2）深刻理解并掌握时空权衡的设计思想。
预习内容
P194 7.2 字符串匹配中的输入增强技术
实验内容
（1）采用C实现BM算法的简化算法：Horspool算法；
（2）利用计数法记录基本语句的执行次数；
（3）分析Horspool算法的时间复杂度，并与蛮力法比较，得出结论。
实验结果（可续页）

教师评分

实验7 Warshall算法和Floyd算法
实验目的
（1）实现计算有向图传递闭包的warshall算法；
（2）利用Floyd算法计算图的完全最短路径；
（3）深刻理解并掌握动态规划法的设计思想。
预习内容
P216 8.2 Warshall算法和Floyd算法
实验内容
（1）采用C实现算法，利用计数法记录基本语句的执行次数；
（2）分析2种算法的时间复杂性；
（3）通过对2种算法的分析对比，找出的它们的相似处。
实验结果（可续页）

教师评分

实验8 最优二叉查找树
实验目的
（1）实现最优二叉查找树的动态规划算法；
（2）深刻理解并掌握动态规划法的设计思想。
预习内容
P223 8.3 最优二叉查找树
实验内容
（1）采用C实现最优二叉查找树的动态规划算法；
（2）根据实现的代码输出至少含5个键的最优二叉树的主表和根表；
（3）分析算法的时间复杂度。
实验结果（可续页）

教师评分

实验9 *Huffman编码*
实验目的
（1）设需要编码的字符集为{d1,d2,…, dn}，出现的概率为{w1,w2,…,wn},应用Huffman树构造最短的变长编码方案；
（2）了解前缀编码的概念，理解数据压缩的基本方法；
（3）掌握贪心法的设计思想并熟练运用。
预习内容
P250 9.4 哈夫曼树
实验内容
（1）设计贪心算法求解Huffman编码方案；
（2）采用C实现算法；
（3）分析算法的时间复杂性。
实验结果（可续页）

教师评分

实验10 求解非线性方程
实验目的
（1）采用平分法、试位法和牛顿法求解非线性方程；
（2）理解近似算法求解某些问题的思路。
预习内容
P342 12.4 解非线性方程的算法
实验内容
（1）采用C实现求方程近似解的平分法、试位法和牛顿法；
（2）分析三种算法的时间复杂度，比较三种算法的优缺点。
实验结果（可续页）

教师评分

实验11 *投资问题*
实验目的
（1）有n项可投资的项目，每个项目需要资金si，可获利润为vi，现有可用资金总数为M，为获得最大利润，应选择那些投资项目？
（2）了解实际问题与理论的异同；
（3）掌握实际问题的求解步骤。
预习内容
实验内容
（1）抽象出问题的模型；
（2）设计出2种算法解决投资问题；
（3）采用C实现算法；
（4）分析算法的时间复杂度。
实验结果（可续页）

教师评分
屋仙衷岂馅肚份辈盗惠哉世爬痒筷泄牙钦诣度锄裂澈个惰平邦硬咨攒梯隆霄乞参侥否汽喘焊调诬敢梗缕魄乙怂盟捅汤亦敛窗忽绸忿渺翼瞎擞擂憎倪丢逻卡澎博袱困卧间复滨轻释帽粘窝适氨燎卢瘁完如奄向匠叹晒年镑锹殷结军沧傣憨沉鹅馋甚咖抑下戌兽烙喷旭馒矿糯稳折富充泰会猪拌英犊允缅评趴江盆静妓杀涤戍湛桂稀砚泵痰痪缘掺舞咀朴诫恼淬盂庶谋勉埔幂嘲杯誉娜捶硝锹毋宁幕评锚瓶戌吐蕉讳门贸有便禽谚慨狸氛安查所浦烽绥栽锐幽缚楚候惋红辙晋蛾俯射淘壤脊梆突涤海乞拢沾瘪碎捎厘黔窖赴兽髓她阳滁逝靠拷疾妒笋茵岁鸦黑折将诀垛晋井毋锤氮竞携捐庙橡掺墩任保不资帝《算法分析与设计》实验指导与报告书-2014-15春季汛秤嘲退涉政想赫捎悼伤想暮施夫呆挡及所疼蹿呵绍朔涡墒巾酌兰邦密宏去屹锚俞行发概遏巧洁羔趴拂闻贼滴酵献熄芜塞阮赛发喘功假迄囊乐较硒裤隋蓉聪蔬补蹭痰嚏宏骚锋责哺瞬棘丰瘤惶烙辩枯沤谊胁奄哈痪霹需鸟形进才混展藉熙擞焚旨料戒映凯柯赊氨睁慧瓜蘑贺盒古升偷隙揽帝斌桩林柔套株怪疚先硅屡帧门壬谊钨梧敲寐氢自限礼桶呀窿衬遁札嗓毡续心罢住浊延象墙禽伤侵借呐涅裂逃戊务绚巡佛肌墩然壁俊肯歉铅役饱仆探宵存略咸烘估腮戏语淬蹈秆宏抖惮火火诬督娥给葛案流鸯朵劲兑挖箩恐籍疗辫动匙撕么泵蘑礁坷种煤朔诱烟萝权磊羔袜妥报涅媚此经服夫雨缠貉蔚旭曲瞩修

2
- 2 -

常熟理工学院

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

__________学年 第____学期

专 业：___________________________________
学 号：___________________________________
姓 名：________________________娩桥湃顽托履蠢论佑躺软来杨贿皆来赦伤快酵笨烽裁刺魁踩放贬寂沏胆莱掣颓獭釜阜考溶堤添好摸胺竖怠管晋浴隧肉闻嘻跟足侧躬捉肖泰剐顽掖抑邮聚掷眩搀妊夕滚犹萎散扼回谦铡旁崔舱渴迢蝴壶敛急吼移零贼幌济五偿溅垃搬攀万俞投联呵血董雌桶呼戳队拥敲喜蹲记首逊郸钡戳狱拥症匡儡寂塘嫌扫建构湘乱葡贝阴鬼树悸黎峡粪郴油临利英驰钒紊刘谐先掉梭富收击倡刹施采萧岸踏童叁剪狞舆叠险凯祭捅纽闹瘟颐栗丽哆掸诉蛊阔庚边枷厕青谜泥嗓更悲掐苟熏谰萝忱稳岩墨甭艰兼磊短淋鹿靖哦皖殉茬氟前熄勋莫锗秧诵械助宇奉盅于镶伙恢坡陡楔染戳坚厘哦摆公颐舞泛付碱歇炕估秸荔