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

常熟理工学院《算法设计与分析》实验指导与报告书学年第____学期专业：___________________________________________学号：___________________________________________姓名：___________________________________________实验地点：___________________________________________指导教师：___________________________________________计算机科学与工程学院2012实用标准文案实验目录实验一 求最大公约数 4实验二 串匹配问题 7实验三 斐波那契数列 10实验四 堆的创建与堆排序 13实验五 霍纳法则 16实验六 Warshall 算法和Floyed 算法 19实验七 最优二叉查找树 22实验八 解非线性方程的算法 25精彩文档实用标准文案精彩文档实用标准文案实验一 求最大公约数实验目的与任务⑴复习数据结构课程的相关知识，实现课程间的平滑过渡；⑵掌握并应用算法的数学分析和后验分析方法；⑶理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。预习内容：第一章 绪论1.1算法的概念实验内容及要求⑴至少设计出三个版本的求最大公约数算法；⑵对所设计的算法采用大 O符号进行时间复杂性分析；⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间；⑷通过分析对比，得出自己的结论。精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验二 串匹配问题实验目的与任务⑴深刻理解并掌握蛮力法的设计思想；理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。（了解空间换时间权衡的思想）预习内容BruteForce 算法,Horspool 算法.(P1977.2串匹配中的输入增强技术 )实验内容及要求⑴实现BruteForce 算法；⑵实现BM算法的简化算法：Horspool 算法；⑶对上个算法进行时间复杂性分析，并设计实验程序验证分析结果。精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验三 斐波那契数列实验目的与任务⑴深入理解斐波那契数列；理解递归的思想；预习内容斐波那契数列；实验内容及要求⑴上机实现斐波那契数列的四种算法，并用计时法测算四种算法的运行时间；⑵对所设计的算法采用大 O符号进行时间复杂性分析；⑶通过对四种算法分析对比，得出自己的结论精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验四 堆的创建与堆排序实验目的与任务、深刻理解变换（变治法）的思想。预习内容堆的定义。堆创建的算法与堆排序算法。实验内容及要求1、代码实现堆的创建。2、代码实现堆排序算法。3、分析堆排序算法的时间复杂度并与合并排序，快速排序算法进行比较，最后得出自己的结论。精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验五 霍纳法则实验目的与任务（1）深刻理解变治法的思想。预习内容霍纳法则，二进制幂实验内容及要求（1） 代码实现霍纳法则算法。并实现求任给一个多项式除以 (x-c)的商和余数。2）代码实现计算an的从左至右二进制幂算法。3）分析霍纳法则与蛮力计算多项式的算法时间复杂度，并进行比较。精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验六Warshall 算法和Floyed算法实验目的与任务⑴利用warshall 算法计算有向图传递闭包和利用 Floyed算法计算全部最短路径。(2)深刻理解并掌握动态规划法的设计思想；预习内容warshall 算法与Floyed算法实验内容及要求⑴上机实现算法，并用计数法和计时法分别测算算法的运行时间；⑵对所设计的算法采用大 O符号进行时间复杂性分析；⑶通过对warshall 算法与Floyed算法分析对比，找出的他们的相似处。精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验七最优二叉查找树实验目的与任务、深刻理解动态规划法的思想。预习内容最优二叉查找树的定义与算法实验内容及要求代码实现动态规划算法求最优二叉树的算法。根据实现的代码给出至少含5个键的最优二叉树主表和根表，并根据根表画出最优二叉查找树。分析此算法的时间复杂度。精彩文档实用标准文案实验结果（可续页）精彩文档实用标准文案教师评分精彩文档实用标准文案实验八 解非线性方程的算法实验目的与任务理解NP困难问题，了解其中一些问题的近似算法预习内容解非线性方程的算法 平分法，试位法，牛顿法实验内容及要求1）代码实现平