实验模板——分治法

《实验模板——分治法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程：算法分析与设计系科：计算机科学系班级：2004级姓名：学号：年度：2006-2007学期：下计算机与信息科学学院计算机科学实验教学中心实验报告填写说明：1、实验内容：填写本次实验的主要内容；2、实验原理：应详细描述该实验所涉及到的理论，并画出相关原理图（如果有则画出，如计算机网络中的拓扑图等）；3、实验要求：该实验的具体要求以及应达到的实验目的；4、实验环境：该实验所涉及到的软、硬件环境；5、实验步骤：详细描述该实验的实验过程；6、实验分析与总结：应详细填写完成该实验的收获和得失，并写出在实验过程中遇到的问题、解决办法、实验心得以及对该实验的建议和意见。实

2、验名称分治法成绩实验内容//请填写你所选定的实验题目1、用分治策略写出并实现，三分法检索算法。2、实现一个“由底向上”的归并分类算法，要求取消栈空间的需要。3、实现斯特拉森矩阵乘法（任选一个完成）实验原理分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。实验要求分析问题，在分治法的基本思想基础上设计出相应的

3、分治算法，分析算法的时间复杂度和空间复杂度。选择自己熟悉的编程环境和编程语言实现相应的算法，并通过具体的数据说明算法的可行性和正确性。通过实验加深对分治法的解题思路，并将其应用于实际问题，同时进一步提高算法设计和程序编写能力。实验环境Pc机，windows操作系统，win-tc，vc++6.0或Java2作为编程环境。实验步骤1、分析问题//说明问题为什么可以使用分治法求解2、根据问题分析，设计利用分治法解决问题的基本思路//简单说明分治法解题的基本思路3、算法设计//请用类C++语言写出问题的算法4、算法的时间复杂度和空间复杂度分析//列出相应的公式或者分析结果，同时

4、进行简要的说明1、算法实现//具体代码参见文件…2、程序运行实例//请将程序运行情况截图说明实验分析与总结请从下面方面进行总结1、分治法可以用于哪类问题，有什么优势？2、在设计算法和调试程序过程中，遇到那些主要问题，解决的经验和方法有哪些？3、你在本次实验中学到了什么？4、是否还存在不足，应该怎么改进？实验日期2007年3月指导教师