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

《《算法设计与分析》实验指导及报告书.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途常熟理工学院《算法设计与分析》实验指导与报告书＿_＿__＿学年第____学期专业：_____＿_____＿＿_＿______＿__＿__＿＿____＿_＿_______学号:____＿____＿___＿_＿_＿_＿_＿_＿___＿＿____＿__＿______姓名：__＿＿______＿______＿＿__＿_____＿＿___＿＿____＿_＿__实验地点：____＿_＿＿__＿_________＿__________＿____＿＿_____指导教师：____＿＿_＿＿_＿____________＿＿_＿___＿＿

2、＿_____＿___＿计算机科学与工程学院２012个人收集整理勿做商业用途实验目录实验一求最大公约数3实验二串匹配问题５实验三斐波那契数列7实验四堆的创建与堆排序9实验五　霍纳法则ﻩ１１实验六Ｗarｓhａll算法和Floｙed算法13实验七最优二叉查找树１５实验八解非线性方程的算法ﻩ17个人收集整理勿做商业用途实验一求最大公约数实验目的与任务⑴　复习数据结构课程的相关知识,实现课程间的平滑过渡；⑵掌握并应用算法的数学分析和后验分析方法；⑶　理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同，复杂程度不同,解题效率也不同。

3、预习内容：第一章绪论１.１算法的概念实验内容及要求　⑴至少设计出三个版本的求最大公约数算法；⑵对所设计的算法采用大Ｏ符号进行时间复杂性分析;⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间;⑷通过分析对比，得出自己的结论。个人收集整理勿做商业用途实验结果(可续页）个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验二串匹配问题实验目的与任务⑴深刻理解并掌握蛮力法的设计思想;（2）理解这样一个观点:用蛮力法设计的算法，一般来说,经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。(了解空间换时间权衡的

4、思想)预习内容BrｕteFoｒｃｅ算法,Ｈorspｏol算法.(P1９77．2串匹配中的输入增强技术)实验内容及要求⑴实现BruteＦoｒce算法；⑵　实现BM算法的简化算法：Horｓpool算法；⑶对上个算法进行时间复杂性分析,并设计实验程序验证分析结果。　个人收集整理勿做商业用途实验结果（可续页)个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验三斐波那契数列实验目的与任务⑴　深入理解斐波那契数列;(2)理解递归的思想;预习内容斐波那契数列；实验内容及要求⑴上机实现斐波那契数列的四种算法，并用计时法测算四种算法的运行时间；⑵对

5、所设计的算法采用大O符号进行时间复杂性分析;⑶通过对四种算法分析对比,得出自己的结论实验结果(可续页)　个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验四堆的创建与堆排序实验目的与任务　１、深刻理解变换（变治法)的思想。预习内容堆的定义。堆创建的算法与堆排序算法。实验内容及要求1、代码实现堆的创建。2、代码实现堆排序算法。3、分析堆排序算法的时间复杂度并与合并排序，快速排序算法进行比较，最后得出自己的结论。实验结果（可续页）　个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验五霍纳法则实验目的与任务　(1)深刻理解变治

6、法的思想。预习内容霍纳法则,二进制幂实验内容及要求（1）代码实现霍纳法则算法。并实现求任给一个多项式除以(x－c)的商和余数。（2）代码实现计算　的从左至右二进制幂算法。（3）分析霍纳法则与蛮力计算多项式的算法时间复杂度，并进行比较。实验结果(可续页）　个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验六Warshａll算法和Ｆloyed算法实验目的与任务⑴利用ｗarshａll算法计算有向图传递闭包和利用Ｆｌｏyeｄ算法计算全部最短路径。（2)深刻理解并掌握动态规划法的设计思想；预习内容　wａrｓhａll算法与Floyed算法实验

7、内容及要求⑴上机实现算法，并用计数法和计时法分别测算算法的运行时间;⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶通过对warｓhall算法与Fｌｏyｅd算法分析对比,找出的他们的相似处。实验结果(可续页)个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验七最优二叉查找树实验目的与任务1、深刻理解动态规划法的思想。预习内容　最优二叉查找树的定义与算法实验内容及要求(1)代码实现动态规划算法求最优二叉树的算法。(2)根据实现的代码给出至少含5个键的最优二叉树主表和根表,并根据根表画出最优二叉查找树。(3)分析此算法的时间复杂度。

8、实验结果(可续页）个人收集整理勿做商业用途教师评分个人收集整理勿做商业用途实验八解非线性方程的算法实验目的与任务理解NＰ困难问题，了解其中一些问题的近似算法预习内容　解非线性方程