算法设计与分析-实验指导书(供参考).doc

《算法设计与分析-实验指导书(供参考).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验指导书院系：数学与计算机专业：计算机科学与技术课程：算法设计与分析编者：刘胜实验一递归与分治法1实验二贪心算法2实验三回溯法3实验四动态规戈U4实验五分支限界法5实验六综合实验6实验一递归与分治法—、实验目的:利用递归与分治法解决简单问题，加深对分治算法的理解与掌握。二、实验内容：利用递归与分治法解决Strassen矩阵乘法问题。三、实验原理与方法：递归与分治法。四、实验条件：具有C语言编程平台和JAVA语言编程平台的计算机系统；Internet环境。五、实验步骤：1、设计解决"Strassen矩阵乘法”的分治算法；2、编程实现“Strassen矩阵

2、乘法”分治算法。六、实验注意事项：算法设计要求能解决一定规模的问题,Strassen矩阵乘法中N*N可达16*16；算法实现后要有一定的测试量和等价覆盖。七、实验报告要求：1、实验报告格式应使用院系实验报告参考格式；2、“一、实验预习部分”，主要填写实验目的、实验内容、实验原理、实验条件、算法设计等，其中算法设计是主要部分。3、“二、实验过程记录”，主要记录实验的步骤与方法，主体部分是算法的实现，结果等，要有算法实现核心代码。4、“三、实验结果与讨论”，主要总结做了什么，结果怎样，遇到哪些重要问题，如何解决的，有哪些技术提高，还有哪些问题有待进一步研究。

3、5、实验报告用语应尽量采用书面技术语言，以求简明准确；6、实验报告应独立完成，在规定时间内提交。实验二贪心算法—、实验目的:利用贪心算法解决简单问题，加深对贪心算法的理解与掌握。二、实验内容：利用贪心算法解决有期限的任务安排问题。有期限的任务安排问题：有n个任务每个任务丁都有一个完成期限山,若任务丁在它的期限d,内完成，则可以获利G,问如何安排使得总的收益最大（假设完成每一个任务所需时间均为一个单位肘间）。三、实验原理与方法：贪心算法。四、实验条件：具有C语言编程平台和JAVA语言编程平台的计算机系统；Internet环境。五、实验步骤：1、设计解决有期

4、限的任务安排问题的贪心算法；2、编程实现解决有期限的任务安排问题的贪心算法。六、实验注意事项：算法实现需能解决16个任务以内的有期限的任务安排问题。需给出最优解（任务安排）与最优值（最大获利）。七、实验报告要求：实验报告应遵循实验报告一般性要求（见实验一）。实验三回溯法—、实验目的:利用回溯法解决简单问题，加深对回溯算法的理解与掌握。二、实验内容：利用回溯法解决8皇后问题。三、实验原理与方法：回溯法。四、实验条件：具有C语言编程平台和JAVA语言编程平台的计算机系统；Internet环境。五、实验步骤：1、设计解决8皇后问题的回溯算法；2、编程实现解决8

5、皇后问题的回溯算法。六、实验注意事项：算法实现需给出8皇后问题所有可行解。七、实验报告要求：实验报告应遵循实验报告-•般性要求（见实验一）。实验四动态规划—、实验目的:利用动态规划算法解决简单问题，加深对登台规划算法的理解与掌握。二、实验内容：利用动态规划算法解决伪币辨别问题。伪币辨别问题：有n块硬币，其中有一块伪币，比正常的硬币轻。现有一•天平，通过天平找出其中的伪币，要求在最坏的情况下，使用天平次数最少，给出最优值（最少使用天平次数）和最优解。三、实验原理与方法：动态规划算法。四、实验条件：具有C语言编程平台和JAVA语言编程平台的计算机系统；Int

6、ernet环境。五、实验步骤：1、设计解决伪币辨别问题的动态规划算法；2、编程实现解决伪币辨别问题的动态规划算法。六、实验注意事项：算法实现可解决64枚以内硬币的伪币辨别问题，得出最优值与一个最优解。七、实验报告要求：实验报告应遵循实验报告一般性要求（见实验一）。实验五分支限界法—、实验目的:利用分支限界算法解决简单问题，加深对分支限界算法的理解与掌握。二、实验内容：利用分支限界算法解决旅行售货员问题。三、实验原理与方法：分支限界算法。四、实验条件：具有C语言编程平台和JAVA语言编程平台的计算机系统；Internet环境。五、实验步骤：1、设计解决旅行

7、售货员问题的分支限界算法；2、编程实现解决旅行售货员问题的分支限界算法。六、实验注意事项：算法实现可解决8城市以内非对称旅行售货员问题，得出最优值与一•个最优解。七、实验报告要求：实验报告应遵循实验报告一般性要求（见实验一）。实验六综合实验—、实验目的:利用2种常用算法设计策略，解决同一简单问题，训练灵活选择与使用适当算法的能力。二、实验内容:利用2种常用算法解决旅行售货员问题，比较2种方法的复杂度和解决问题的精度。三、实验原理与方法:综合利用算法设计与分析知识。、实验条件:具有C语言编程平台和JAVA语言编程平台的计算机系统；Internet环境。五、

8、实验步骤:1、设计2种常用算法解决旅行售货员问题;2、编程实现2种常用算法解决旅