《算法递归与分治实验》由会员分享，可在线阅读，更多相关《算法递归与分治实验（4页珍藏版）》请在金锄头文库上搜索。
1、实验一、递规与分治算法实验一、递规与分治算法班级：计 072学号：3070911052姓名：赵凯一、实验目的与实验内容 1掌握递归与分治方法的基本设计思想与原则。 2二分法，汉诺塔问题，给定 a，用二分法设计出求 an的算法。 二、实验要求 1 C+/C 完成算法设计和程序设计并上机调试通过。 2 撰写实验报告，提供实验结果和数据。 3 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简 要给出算法设计小结和心得。 三、程序实现 二分法：在数组 an中找 x，将 n 个元素分成个数大致相同的两半，取 an 与 x 作比较。如果 x=a，则找到 x，算法中止；如果 xan/2
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 循环，待搜索数组的长度减少了一般，所以，在最坏 情况下 whil
3、e 被执行了 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、（见附录：源程序） 。 二分法： #include using namespace std; int binarySearch(int a, int x, int n); int main() int n; coutn; int *a=new intn;coutai; for(i=0;ix; if(binarySearch(a,x,n)!=-1)调用二分查找 cout amiddle) left = middle + 1;else right = middle - 1;return -1; / 未找到 x 汉诺塔： #include #include using namespace std;
5、void move(char e,char f)/定义方向移动函数 cout “0) hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,b,a,c); int main()int t;coutt;/测试次数for(int q=0;qd;hanoi(d,a,b,c);cout using namespace std; int pow(int,int); int main() int a,n,an,t;for(t=0;ta;coutn;an=pow(a,n);couta“的次幂是“anendl;return 0; int pow(int x,int y)/实现二分求幂 if(y=1)return x;else return pow(x,y/2)*pow(x,y-y/2);
