武汉理工大学 学 生 实 验 报 告 书 实验课程名称 《算法设计与分析》 开 课 学 院 计算机科学与技术学院 指导老师姓名 何九周 学 生 姓 名 学生专业班级 软件 0802班 2 0 1 0 — 2 0 1 1 学年 第 一 学期 学生学号 实验课成绩 实验课程名称： 算法设计与分析 实验项目名称 分治法应用及设计 实验成绩 实验者 专业班级 组别 同组者 实验日期 年 月 日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 1 .利用分治法，写一个二分检索的递归算法，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析。 2.要求用递归方法实现 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） int besearch(int n,int m,int c,int *source) { if(第 n个点大于第 m个点的值) return 失败; h=n与 m的中点 if(h的值等于目标) return h; if(h的值小于目标) return besearch(n,h-1,c,source);//在 n至 h-1找 else return besearch(h+1,m,c,source); //在 h+1至 m找 } 三、主要仪器设备及耗材 Visual C++,Windows Xp 第二部分：实验调试与结果分析（可加页） 一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等） 调试方法：直接在函数体内定义测试，负责初始化查找的有序表。 1. 没有设定好中值点，忘记在两个端点的差值上增加左边端点的内容。 2. 递归调用时，错误使用了边界条件，导致结果不正确，应该是n – h-1 和 h+1 - m 二、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等） 实验结果： 查找均为正确结果。 时间复杂度：O(n lo gn ) 空间复杂度：无需大量增加空间，仍为 O(n) 算法总结：算法效率很高，但是采用递归调用使得数据入栈出栈，开销稍大。 三、实验小结、建议及体会 经过实际动手操作，我掌握了采用分治法的2分检索算法，实际书写中出现了很多开始没有想到的问题。认识到了自己的不足。 实验课程名称： 算法设计与分析 实验项目名称 分治法应用及设计 实验成绩 实验者 专业班级 组别 同组者 实验日期 年 月 日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 用分治法，实现对n 个元素进行排序的算法，并进行时间复杂性分析。 要求用非递归...
