首页 > 编程知识 正文

递归算法解决问题的特点,分治算法重叠子问题

时间:2023-05-04 05:24:42 阅读:242729 作者:4390

概念解读

其实ajdkl问题的实质就是利用眼前的这三根柱子,一次只能移动一个圆盘,其中一根作为中介柱,使一根柱子上的圆盘移到另一根上。在移动的过程中不能出现大的圆盘套在小的圆盘的上面。
其实这个问题体现了递归的思想,上面的三种情况列举出来以体现问题的递归性。

上面图片的解释并不完备!
以三个ajdkl举例:我们要将a柱上的ajdkl全部移到c上,b柱为中转柱

第一步:我们要设法将a柱上前两个移到b上,再将a柱上最后一个移到c上
第二步:如何将a柱上的前两个移到b上?就是将第一个移到c上将第二个移到b上
第三步: 现在思考如何将c柱上的移到b上?很显然就是一个我们直接一上去。这样就完成了我们第一步的前两个移到b上的步骤。再将a柱上最后一个移到c上。
递归步:现在思考的就是如何将b上的两个,或者是N-1个移到c上的操作。继续重复的操作

以此思想我们可以设计递归算法算法:

void Hanoi(int n,char a,char b,char c){//判断条件当只剩一个ajdkl的时候执行参数a这个柱子->参数b这个柱子//初始传值A,B,C对于a,b,c这三个参数,所以当A柱只有一个ajdkl时就是A->C的操作if(n==1){printf("%c->%cn",a,c); return; }//底下就是递归的操作了//如果不止一个ajdkl,就开始将前n-1个ajdkl执行a->b的操作Hanoi(n-1,a,c,b);//如果完成了前n-1个ajdkl从a->b的操作,我们就将a上的最后一个移到c上printf("%c->%cn",a,c);//这时候再执行b上ajdkl,到c上的操作Hanoi(n-1,b,a,c);}

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。