算法分析与设计实验报告.docx

《算法分析与设计实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告目录实验一：递归与分治………………………………………1二分查找归并排序快速排序实验二：回溯算法…………………………………………80—1背包实验三：动态规划…………………………………………12矩阵连乘最少乘法数实验一：递归与分治一、实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。二、实验内容1．二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。2．合并排序3．快速排序对本实验中的问题，

2、设计出算法并编程实现。实验总结及思考三、实验过程1.二分查找算法：BinSearch(aArray[0,1……n-1],key)low<---0;right<---n-1;whilelow<=rightdom<---(low+(right-low))/2;ifkey>aArray[mid]l<---mid+1;ifkeyusingnamespacestd;voidBinary(intaArray[],intkey,intlength)

3、//二分查找{intmid,low,high;mid=low=0;high=length-1;while(low<=high){mid=low+((high-low)/2);//使用(low+high)/2会有整数溢出的问题if(low<0

4、

5、high>=length

6、

7、high-low==0){cout<<"元素不存在，查找失败"<aArray[mid])//key在右边{low=mid+1;}elseif(key

8、dl;break;}20}}intmain(){intlength=0;intkey=0;cout<<"请输入数组的长度："<>length;int*aArray=newint[length];cout<<"请输入数组："<>aArray[i];}cout<<"请输入待查找的数字："<>key;Binary(aArray,key,length);deleteaArray;//释放空间return0;}二分查找的平均时间复杂度为O(logn)最坏情况下的时间复杂度O(n)

9、20运行截图：1.合并排序基本操作如下:（1）分解:将n个元素分成各含n/2个元素的子序列（2）解决:用合并排序法对两个子序列递归地排序（3）合并:合并两个已排好序的子序列得到排序结果在对子序列排序时，其长度为1时递归结束。单个元素被视为是已排好序的。算法：MergeSort(A[0…n-1])ifn>1copyA[0…n/2-1]toB[0…n/2-1]copyA[n/2…n-1]toC[0…n/2-1]MergeSort(B[0…n/2-1])MergeSort(C[0…n/2-1])20Merge(B,C,A)Merge(B[0…p-1],C[0…q-1],A[0…P+q

10、-1])i<---0;j<---0;k<---0whileiusingnamespacestd;voidMerge(int*a,intp,intq,intr)//把数组a[]分成L[]，R[]，再排序合并成a[]{intn1=q-p+1;intn2=r-q;int*L=

11、newint[n1+1];int*R=newint[n2+1];inti,j,k;for(i=0;i