实验一

实验一：递归与分治（4学时）姓名:田圆圆学号：2013125135一：实验目的与要求：理解递归与分治算法设计思想和方法。二：预习与准备:一个规模为n的复杂问题的求解：可以划分成若干个规模较小n的子问题进行求解，再将子问题的解合并成原问题的解，这便是分治的思想。若划分成的每一个子问题都与原问题的性质相同，可用相同的求解方法；当子问题规模划分一定小时，子问题的解已知，则逆求原问题的解，这是递归的思想。三：实验题目:1、汉诺塔（hanoi）问题。设有A、B、C共3根塔座，在塔座A上堆叠n个金盘，每个盘大小不同，只允许小盘在大盘之上，最底层的盘最大，如下图所示。现在要求将A上的盘全都移到C上，在移的过程中要遵循以下原则：每次只能移动一个盘；圆盘可以插在A、B和C任一个塔座上；在任何时刻，大盘不能放在小盘的上面。2、二分查找问题（1）设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。（2）设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。3、快速排序问题在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。四、实验过程:（1）.汉诺塔问题，根据参考资料，编程，程序代码如下：#includeiostream#includestdio.husingnamespacestd;staticints=0;voidmove(chars,chard){printf(movefrom%cto%c\n,s,d);}voidhanoi(intn,chars,chartemp,chard){if(n==1){move(s,d);++s;}else{hanoi(n-1,s,d,temp);move(s,d);++s;hanoi(n-1,temp,s,d);}}intmain(intargc,char**argv){intn=4;hanoi(n,'A','B','C');printf(Totalstepsis%d\n,s);return0;}（2）二分查找问题，根据参考资料，编程，程序代码如下#includestdio.h#includestdlib.hintSreach(inta[],intn,intx,int&i,int&j){intmid;intright=n-1;intleft=0;while(leftright){if(xa[n-1]||xa[0]){i=right;j=left;return-1;}else{mid=(right+left)/2;if(x==a[mid]){i=j=mid;returnmid;}if(xa[mid]){left=mid+1;}else{right=mid-1;}i=right;j=left;}}}intmain(){inti,j,mid;intx=4;intb[]={1,2,3,5,6,7,8,9,10};mid=Sreach(b,9,x,i,j);if(mid!=-1){printf(x的位置在:%d,i=%d,j=%d\n,mid+1,i,j+1);}else{if(xb[9])printf(不能找到x元素，大于x的最小元素不存在，小于x的最大元素下标i=%d\n,i);if(xb[0])printf(不能找到x元素，小于x的最大元素不存在，大于x的最小元素下标j=%d\n,j);}return0;}（3）.快速查找问题，根据参考资料，编程，程序代码如下#includestdio.hvoidsort(inta[],intleft,intright){if(left=right)return;inti=left;intj=right;inttemp=a[left];while(i!=j){while(tempa[j]&&ij)j--;if(i==j)break;a[i]=a[j];i++;////////////////////////////////////////////////////while(a[i]temp&&ij)i++;if(i==j)break;a[j]=a[i];j--;}a[i]=temp;sort(a,left,i-1);sort(a,i+1,right);}intmain(){intarr[7]={10,2,3,5,3,6,9};intvvv[9]={5,532,523,532,87,3124,76,4325,6};intk;sort(arr,0,6);for(k=0;k7;k++)printf(%d,arr[k]);printf(\n);sort(vvv,0,8);for(k=0;k9;k++)printf(%d,vvv[k]);printf(\n);return0;}五、实验结果与结论:(1)汉诺塔问题实验结果：当n=4时当n=5时，金盘移动过程：二分查找实验结果为：给出一个数组{1,2,3,5,6,7，8,9，10}，当查找元素x=0时：当查找元素x=4时：当查找元素x=5时：使用快速排序法：当给定的两个数组intarr[7]={10,2,3,5,3,6,9};intvvv[9]={5,532,523,532,87,3124,76,4325,6};时，所得实验结果为：