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

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

1、实用标准文案常熟理工学院《算法设计与分析》实验指导与报告书______学年第____学期专业：___________________________________________学号：___________________________________________姓名：___________________________________________实验地点：___________________________________________指导教师：___________________________________________计算机科学与工程学院2012实验目录精彩文

2、档实用标准文案实验一求最大公约数3实验二串匹配问题5实验三斐波那契数列7实验四堆的创建与堆排序9实验五霍纳法则11实验六Warshall算法和Floyed算法13实验七最优二叉查找树15实验八解非线性方程的算法17实验一求最大公约数精彩文档实用标准文案实验目的与任务⑴复习数据结构课程的相关知识，实现课程间的平滑过渡；⑵掌握并应用算法的数学分析和后验分析方法；⑶理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。预习内容：第一章绪论1.1算法的概念实验内容及要求⑴至少设计出三个版本的求最大公约数算法；⑵对所设计的算法采用大O符号进行时间复杂性分

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

4、性分析，并设计实验程序验证分析结果。实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验三斐波那契数列实验目的与任务⑴深入理解斐波那契数列；(2)理解递归的思想；预习内容斐波那契数列；实验内容及要求⑴上机实现斐波那契数列的四种算法，并用计时法测算四种算法的运行时间；⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶通过对四种算法分析对比，得出自己的结论实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验四堆的创建与堆排序实验目的与任务1、深刻理解变换（变治法）的思想。预习内容堆的定义。堆创建的算法与堆排序算法。实验内容及要求1、代码实现堆的创建。2、代码实

5、现堆排序算法。3、分析堆排序算法的时间复杂度并与合并排序，快速排序算法进行比较，最后得出自己的结论。实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验五霍纳法则实验目的与任务（1）深刻理解变治法的思想。预习内容霍纳法则，二进制幂实验内容及要求（1）代码实现霍纳法则算法。并实现求任给一个多项式除以(x-c)的商和余数。（2）代码实现计算的从左至右二进制幂算法。（3）分析霍纳法则与蛮力计算多项式的算法时间复杂度，并进行比较。实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验六Warshall算法和Floyed算法实验目的与任务⑴利用warshall算法计算

6、有向图传递闭包和利用Floyed算法计算全部最短路径。(2)深刻理解并掌握动态规划法的设计思想；预习内容warshall算法与Floyed算法实验内容及要求⑴上机实现算法，并用计数法和计时法分别测算算法的运行时间；⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶通过对warshall算法与Floyed算法分析对比，找出的他们的相似处。实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验七最优二叉查找树实验目的与任务1、深刻理解动态规划法的思想。预习内容最优二叉查找树的定义与算法实验内容及要求(1)代码实现动态规划算法求最优二叉树的算法。(2)根据实现的代码给出至少含5个键

7、的最优二叉树主表和根表，并根据根表画出最优二叉查找树。(3)分析此算法的时间复杂度。实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验八解非线性方程的算法实验目的与任务理解NP困难问题，了解其中一些问题的近似算法预习内容解非线性方程的算法平分法，试位法，牛顿法实验内容及要求（1）代码实现平分法求方程近似解的算法（2）代码实现试位法，牛顿法求方程近似解的算法（3）分析三种算法的时间复杂度，比