算法 递归与分治 实验.doc

实验一、递规与分治算法 班级：计072学号：3070911052姓名：赵凯一、 实验目的与实验内容1掌握递归与分治方法的基本设计思想与原则。2二分法，汉诺塔问题，给定a，用二分法设计出求an的算法。二、 实验要求1 C+/C完成算法设计和程序设计并上机调试通过。2 撰写实验报告，提供实验结果和数据。3 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。三、 程序实现二分法：在数组an中找x，将n个元素分成个数大致相同的两半，取an与x作比较。如果x=a，则找到x，算法中止；如果xan/2，则只要在数组a的右半部继续搜索x。汉诺塔：n个盘子从a到b，可经由c。当n=1时，直接从a到b。当n1时，将上边n-1个盘子看成一个整体，从a移到辅助c上，最后一个移到b上。如此，对n-1个盘子使用同样的移动规则从c移到b。至此，n个盘子的移动可以看成两个n-1个圆盘移动的问题，这有可以递归使用上面的方法来做。a的n次幂：将指数n分解为n/2与n/2t同时递归的调用直至将n分解为一时返回时间复杂度：二分法：由于每执行一次while循环，待搜索数组的长度减少了一般，所以，在最坏情况下while被执行了0(n)次，循环体内运算需要0(1)次,因此整个算法在最坏情况下的时间复杂性为（n）。汉诺塔：规模为n问题，可以分解为两个规模为n-1的问题。所以T(n)=2*T(n-1)+1,所以汉诺塔的时间复杂度为0(2n)。a的n次幂：规模为n问题，可以分解为两个规模为n/2的问题。所以T(n)=2*T(n/2)+1,所以汉诺塔的时间复杂度为0(n*n)。四、 心得体会这次的三个实验总总体上来说，还是比较简单。实验过程比较简单，然而前期工作却不少，我认为这次试验的关键就是如何分解问题，如果相通了这个问题，那实验就比较容易了。五、 源程序清单（见附录：源程序）。二分法：#includeusing namespace std;int binarySearch(int a, int x, int n);int main()int n;coutn;int *a=new intn;coutinput nnumbers of arry:endl;for(int i=0;iai;for(i=0;in;i+)/显示数组coutai ;int x;coutx;if(binarySearch(a,x,n)!=-1)调用二分查找coutxis the binarySearch(a,x,n)+1th numberendl;elsecoutnot found!endl; return 0;int binarySearch(int a, int x, int n) int left = 0; int right = n - 1;/左右界限 while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 汉诺塔：#include#includeusing namespace std;void move(char e,char f)/定义方向移动函数 coute f0) hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,b,a,c);int main() int t; coutt;/测试次数 for(int q=0;qt;q+) int d;/盘子数 coutd; hanoi(d,a,b,c); coutTotal Steps: pow(2.0,d)-1endl; return 0;a的n次幂：#includeusing namespace std;int pow(int,int);int main() int a,n,an,t; for(t=0;t4;t+) cout输入底数 a:a; cout输入指数 nn; an=pow(a,n); couta的次幂是anendl; ret