算法设计与分析实验报告样本

《算法设计与分析实验报告样本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计实验报告重庆交通大学学生实验报告实验课程名称算法设计与分析开课实验室数学实验室学院年级09专业班信息2班学生姓名学号09180223开课时间2011至2012学年第1学期评分细则评分报告表述的清晰程度和完整性（20分）程序设计的正确性（40分）实验结果的分析（30分）实验方法的创新性（10分）总成绩教师签名2010-2011学年第一学期算法分析与设计实验报告实验报告题目实验一递归与分治策略开课实验室：数学实验室指导老师：韩逢庆时间：2011.9学院：专业：信息与计算科学班级：2009级2班姓名：学号：09180223一、实验目的1

2、．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。二、实验内容题目见：二分搜索问题、三分搜索问题、整数规划、全排列问题三、实验要求（1）用分治与递归法求解二分搜索问题、三分搜索问题、整数规划、全排列问题。（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）2010-2011学年第一学期算法分析与设计实验报告以二分搜索为例，设计如下算法过程：startLeft=1,right

3、=n-1Middle=(left+right)/2Right=middle-1Left=middle+1Nb>a[middle]Ynob=a[middle]NYReturnmiddleend一、实验结果分析2010-2011学年第一学期算法分析与设计实验报告（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，最坏情况下最好情况下：对二分搜索与三分搜索，刚好处在整行数的中间位置或三分之一或三分之二位置处，一次搜索便找到。因此，时间复杂度如下：最坏情况下：所要找的数处在两端位置上，时间复杂度如下：总的情况下，时间复杂度为：空间复杂性分

4、析：一、实验体会通过该实验，我体会到了递归与分治思想的精髓所在，对其算法的特点有了深刻理解，在以后遇到类似的问题的时候，有了这样的指导思想！递归与分治经常结合到一起解决实际问题，是一种高效率且简洁的算法。具有很强的实际应用意义。优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点2010-2011学年第一学期算法分析与设计实验报告：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。一、附录：（源代码）程序一、二分搜索与三分搜索源代码：#include

5、stream.h>#includeinterfensousuo(int*a,intb,intn){intleft=0,right=n-1;while(left<=right){intmiddle=(left+right)/2;if(b==a[middle])returnmiddle;elseif(b>a[middle])left=middle+1;elseright=middle-1;}return-1;}intsanfensousuo(int*a,intb,intn)2010-2011学年第一学期算法分析与设计实验报告{int

6、low=0,high=n-1,middle1,middle2;while(low<=high){middle1=low+(high-low)/3;middle2=high-(high-low)/3;if(a[middle1]==b)returnmiddle1;elseif(b

7、ow=middle2+1;//处于middle2右边2010-2011学年第一学期算法分析与设计实验报告}return-1;}voidmain(){inti=0,k,z,zhi,*a,n;cout<<"您给定要输入数字的个数n"<>n;a=newint(n);cout<<"请输入"<>a[i];}cout<<"请输入你要查找的数："<>zhi;cout<<"二分搜索结果为："<

8、sousuo(a,zhi,n);if(k==-1)cout<<"数组里面没有您要查找的数"<