算法 递归及分治 实验

《算法 递归及分治 实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一、递规与分治算法班级：计072学号：3070911052姓名：赵凯一、实验目的与实验内容1．掌握递归与分治方法的基本设计思想与原则。2．二分法，汉诺塔问题，给定a，用二分法设计出求an的算法。二、实验要求1．C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。三、程序实现二分法：在数组a[n]中找x，将n个元素分成个数大致相同的两半，取an与x作比较。如果x=a，则找到x，算法中止；如果

2、xa[n/2]，则只要在数组a的右半部继续搜索x。汉诺塔：n个盘子从a到b，可经由c。当n=1时，直接从a到b。当n>1时，将上边n-1个盘子看成一个整体，从a移到辅助c上，最后一个移到b上。如此，对n-1个盘子使用同样的移动规则从c移到b。至此，n个盘子的移动可以看成两个n-1个圆盘移动的问题，这有可以递归使用上面的方法来做。a的n次幂：将指数n分解为n/2与n/2t同时递归的调用直至将n分解为一时返回时间复杂度：二分法：由于每执行一次while循环，待搜索数组的长

3、度减少了一般，所以，在最坏情况下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)。四、心得体会这次的三个实验总总体上来说，还是比较简单。实验过程比较简单，然而前期工作却不少，我认为这次试验的关键就是如何分解问

4、题，如果相通了这个问题，那实验就比较容易了。五、源程序清单（见附录：源程序）。二分法：#includeusingnamespacestd;intbinarySearch(inta[],intx,intn);intmain(){intn;cout<<"inputthelengthofarry:";cin>>n;int*a=newint[n];cout<<"input"<>a[i];for(i=0;

5、i>x;if(binarySearch(a,x,n)!=-1)调用二分查找cout<

6、ight=n-1;//左右界限while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;//未找到x}汉诺塔：#include#includeusingnamespacestd;voidmove(chare,charf)//定义方向移动函数{cout<"<

7、表示从e柱移动一个盘子到f柱}voidhanoi(intn,chara,charb,charc)//a初始柱，b目标柱，c中转柱{if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,b,a,c);}}intmain(){intt;cout<<"输入您要测试的次数t:";cin>>t;//测试次数for(intq=0;q>d;hanoi(d,'a','b','c');cout<<"TotalSteps:"<

8、(2.0,d)-1<usingnamespacestd;intpow(int,int);intmain(){inta,n,an,t;for(t=0;t<4;t++){cout<<"输入底数a:"<