实验一 递归与分治策略 一、实验目的 1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容 1、 ①设a[0:n -1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x 不在数组中时，返回小于x 的最大元素位置i 和大于x 的最小元素位置j。 当搜索元素在数组中时，i 和 j 相同，均为x 在数组中的位置。 ②写出三分搜索法的程序。 三、实验要求 （ 1）用分治法求解上面两个问题； （ 2）再选择自己熟悉的其它方法求解本问题； （ 3）上机实现所设计的所有算法； 四、实验过程设计（算法设计过程） 1 、 已知a[0:n -1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x 与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x 的最大元素的位置i 和大于x 的最小元素位置j。 2、将n 个元素分成大致相同的三部分，取在数组a 的左三分之一部分中继续搜索x 。如果x >a[2(n -1)/3]，则只需在数组a 的右三分之一部分中继续搜索x 。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x 。 五、实验结果分析 二分搜索法： 三分搜索法： 时间复杂性： 二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。 （ n 代表集合中元素的个数） 三分搜索法：O（ 3log3n） 空间复杂度：O（ 1）。 六、实验体会 本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。 七、附录：（源代码） 二分搜索法： #include #include int binarySearch(int a[],int x,int n) { int left=0;int right=n-1;int i,j; while(left<=right) { int middle=(left+right)/2; if(x==a[middle]){i=j=middle;return 1;} if(x>a[middle])left=middle+1; else right=middle-1; } i=right;j=left; return 0; } int main() { int a[10]={0,1,2,3,4,5,6,7,8,9}; int n=10; int x=9; if(binarySearch(a,x,n)) cout<<"找到"<
