资源描述：
《算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法设计与分析实验报告重庆交通大学学生实验报告实验课程名称算法设计与分析开课实验室数学实验室学院数学与统计学院年级13专业班信息与计算科学2学生姓名辜朕圆学号631322020223开课时间2015至2016学年第1学期假设合理优良中差建模求解全面优良中差结果分析完善优良中差文档清晰优良中差综合成绩教师姓名韩逢庆2015-2016学年第一学期算法设计与分析实验报告实验报告题目实验一递归与分治策略开课实验室：数学实验室指导老师：韩逢庆时间：2015.9学院：理学院专业：信息与计算科学班级：2013级2班姓名：辜朕圆学号：63
2、1322020223一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。二、实验内容题目①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。②写出三分搜索法的程序。三、实验要求（1）用分治法求解…问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机
3、实现所设计的所有算法；四、实验过程设计（算法设计过程）2015-2016学年第一学期算法设计与分析实验报告1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。2、先判定输入的数x是否在数组的范围内，再将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果x>a[san2]，则只需在数组a的右三分之一部分中继续
4、搜索x。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。一、实验结果分析(1)例子为数组a[1,2,3,4,5,6,7,8,9],n=9,x=9。实验结果为(2)例子为数组a[1,2,3,4,5],x=3,n=5。实验结果为时间复杂性：最好情况下，最坏情况下二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(logn)。（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂性分析：O（1）。二、实验体会2015-2016学年第一学期算法设计与分析实验报告本次试验解决了二分查找和三分查找的问题，加深
5、了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，再实践操作，毕竟实践是检验真理的唯一标准，只要动手就能感受自己写出算法的喜悦，从而良性循环越学越好。一、附录：（源代码）(1)publicstaticintbinarySearch(inta[],intx,intn){intleft=0;intright=n-1;inti,j;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle]){i=j=mid
6、dle;System.out.println("getit");return1;}if(x>a[middle])left=middle+1;elseright=middle-1;}i=right;j=left;return0;}(2)publicclasssanfen{publicstaticintsanSearch(int[]a,intx,intn){intleft=0;intright=n-1;while(right>left){if(x7、
8、x>a[right]){System.out.println(
9、"根本不在数组里");break;}intsan1=(left+right)/3;intsan2=2*(left+right)/3;if(x==a[san1]){System.out.println("找到了");returnsan1;}elseif(xa[san2])left=san1+1;2015-2016学年第一学期算法设计与分析实验报告else{left=san1;right=fan2;}}return-1;}publicstaticvoidmain(S
10、tring[]args){sanfens=newsanfen();int[]b={1,2,3,4,5};s.sanSearch(b,3,5);}}实验二动态规划一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提
