【vc++精品源码栏目提醒】:本文主要为网学会员提供“武汉理工大学算法实验报告 - 商业合同”,希望对需要武汉理工大学算法实验报告 - 商业合同网友有所帮助,学习一下!
学号 0121010680514 实验成绩 武汉理工大学 实验报告 实验课程名称: 算法分析与设计 开课学院: 计算机科学与技术学院 指导老师名: 桂江亨 学生专业班级: 软件工程 Sy1001 班 2012 – 2013 学年 第 一 学期实验课程名称: 分治法写一个二分检索的递归算法实验项目名称 分治法写一个二分检索的递归算法 实验成绩实验者 桂江亨 专业班级 软件 Sy1001 组别同组者 实验日期 年 月 日第一部分:实验分析与设计(可加页)一、实验内容(问题域描述) 1. 利用分治法,编写一个检索算法,并在计算机上实现,同时进行时间复杂性分析。
本实验是综合型、设计型实验,在实验中需要综合运用《数据结构》中的递归方 法和树的知识;《程序设计》中的数组、条件控制、循环控制和《算法设计与分 析》中的分治法、计算时间的渐进表示和算法的时间复杂性分析等等方面的知识。
2.实验内容: (2.1)利用分治法,写一个二分检索的递归算法,并利用任何一种语言,在计算 机上实现,同时进行时间复杂性分析。
3.实验要求: 首先要对实验内容进行描述,用伪代码设计算法,并对算法在最好,最差和平 均情况下的时间复杂性进行分析,然后 C/C或 JAVA 语言编写程序对算法实 现,同时用具用代表性的数据进行测试,实验后,进行实验总结,描述设计过 程步骤及各步骤含义。
该实验要求用递归实现。
二、实验基本原理与设计(包括实验方案设计,实验手段的确定,实验步骤, 用硬件逻辑或者算法描述) 在本次试验中假设要检索的的数据 vectorltintgt data 中的元素并没有按从大到小的 顺序排好序。
因此算法将遍历数据的每一个元素,比较该元素与目标预算 e 的大小关 系,如果相等则将该元素在数组里面的序号压入 vectorltintgt result 数组中。
当遍历完 成时,输出 result 数组。
为了体现分支的思想,遍历并不是从头依次遍历的数组的结尾,而是将数组从中间分 开,然后依次二分检索数组的前半部分和后半部分。
下面是伪代码vectorltintgt data resultbinarySearch const vectorltintgt ampdata vectorltintgt ampresult int e int beg int end if beg end if databeg e result.push_back beg else int middle beg end / 2 binarySearch data result e beg middle binarySearch data result e middle 1 end 算法时间复杂性分析 在这个递归算法中,问题被分解成两个子问题,假设用 T(n)表示问题规模为 n 的二分检索程序的时间复杂性,那么有下面的公式成立: T n T n / 2 T n / 2 2 T n / 2 因此有: Tn 2 2 T n / 2 / 2 2 2 2 T n / 2 / 2 / 2 pow 2 log 2 n T n / pow 2 log 2 n 当迭代次数足够多时,最终会得到: Tn pow 2 log 2 n T 1 而 T1 1 故:Tn n。
实际上,这个递归算法和一个 for 循环的效率是一样的,因为它最终还是要对每一个元素进行检索。
而且该算法的最好和最差以及平均时间复杂度都是 On。
算法空间复杂性分析 该算法只需要一个数组存储查找的结果,最好情况下为 C,最坏为 On,平均为 On。
三、主要仪器设备及耗材 PC 一台,VC Express Edition 2008.第二部分:实验调试与结果分析(可加页)一、调试过程(包括调试方法描述、实验数据记录,实验现象记录,实验过程发现的问题等) 本次试验遇到的一个问题是输入数据到 vectorltintgt data 数组,然后再按 Ctrl Z 停止输入后,不能再输入值给要查找的元素 e。
后来才知道,C标准程序库把输入 流当做文件,按下 Ctrl Z 后表示输入流到达文件尾,不能继续往下读了。
为了使输 入流重新开始读数据,并需调用 clear函数来清除文件尾状态标记。
二、实验结果及分析(包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等)下面是程序的源代码includeltiostreamgtincludeltvectorgtusing namespace stdvoid binarySearch vectorltintgt ampdata vectorltintgt ampresult int begin int end int e if begin end if databegin e result.push_back begin else int middle begin end / 2 binarySearch data result begin middle e binarySearch data result middle 1 end e void search vectorltintgt ampdata vectorltintgt ampresult int e binarySearch data result 0 data.size - 1 e int main int tmp e vectorltintgt data result cout ltlt quot请输入要查找的数组:quot ltlt endl while cin gtgt tmp data.push_back tmp cout ltlt quot请输入要查找的值:quot ltlt endl cin.clear cin gtgt e search data result e for vectorltintgt::iterator itr result.begin itr result.end itr cout ltlt itr ltlt system quotpausequot return 0程序运行的截图 运行截图(1) 运行截图(2) 运行截图(3)四、实验小结、建议及体会 本次试验中由于要查找的数组都没有进行排序,所以采用分治法和使用一次循环遍历的效果是一样的。
但是如果数组进行了排序,而且数组中没有重复的元素,那么采用分治法的效率将非常之高。
分治法将问题分解成一个个问题规模更小的子问题,然后采用递归的方式解决。
在设计递归程序时不需要知道递归是怎样完成问题的,只需要遵循下面几个准则: (1) 基准情况,必须存在基准情况,不需要通过递归就能求解问题。
(2) 递归必须朝着基准情况靠近。
(3) 假设递归是正确的。
(4) 避免重复递归。
第三条准则方便我们设计递归,它让我们不需要关注递归是如何将子问题解决的,我们只需要假定子问题已经解决后,该如何解决父问题。
实验课程名称: 分治法实现对 n 个元素进行排序实验项目名称 分治法实现对 n 个元素进行排序 实验成绩实验者 桂江亨 专业班级 软件 Sy1001 组别同组者 实验日期 年 月 日第一部分:实验分析与设计(可加页)一、实验内容描述(问题域描述) 1. 实验描述: 利用分治法实现对 n 个元素排序,并在计算机上实现,同时进行时间复杂性分析。
本实验是综合型、设计型实验,在实验中需要综合运用《数据结构》中的递归方法 《程序设计》中的数组、条件控制、循环控制和《算法设计与分析》中 和树的知识; 的分治法、计算时间的渐进表示和算法的时间复杂性分析等等方面的知识。
2.实验内容: 用分治法,实现对 n 个元素进行排序的算法,并进行时间复杂性分析。
3.实验要求: 首先要对实验内容进行描述,用伪代码设计算法,并对算法在最好,最差和平均 情况下的时间复杂性进行分析,然后 C/C或 JAVA 语言编写程序对算法实现,同时 用具用代表性的数据进行测试,实验后,进行实验总结,描述设计过程步骤及各步 骤含义。
要求用非递归方式实现。
二、实验基本原理与设计(包括实验方案设计,实验手段的确定,试验步骤等,用硬件逻辑或者算法描述) 用递归写一个归并排序是比较容易的,递归隐藏了复杂头疼的出栈入栈,调用与回溯,使得程序简洁干净,而且思路清晰。
改成非递归就显得比麻烦了,理论上递归程序都可以转化为非递归程序,不过有时候可能需要自己维护一个栈。
一开始我也想自己维护一个栈来模拟递归的归并算法的解题过程,但觉得这样很复杂,而且一直没想到办
上一篇:
并行编程模式
下一篇:
视频在线点播系统:ASP.NET 和 SQL Server 2005 实现一个简易的在线视频点播系统。按功能的不同可以划分为 5 个模块