1.是什么
汉诺塔(Hanoi Tower)是一个经典的递归问题,描述了将一个由三根柱子组成的塔上的n个大小不一的圆盘从一个柱子移动到另一个柱子上的过程。每次移动只能移动一个圆盘,并且大圆盘不能放在小圆盘上面。
思路分析:
当圆盘总数是5时,要将最底层的圆盘(最大的圆盘)放到c塔,那么就要其余的圆盘(num-1)放到B塔
同理要想将4号盘放到B塔,就要将上面其余的盘放到C盘,最底层的5号盘先忽视
同理,要想将3号盘放到C塔就要将上面的盘放到B塔
同理,要将2号盘放到B塔就要将1号盘放到C塔
演示:
到了这步骤已经堆好了以2为底的盘了,后面的步骤就是从A塔中拿出来的大盘为底盘再按顺序叠好
以3号为底的盘子按顺序(大到小)叠好,以此类推
这样,5号盘就可以放到C塔了,那么如果想将4号盘放到C塔,那么其余的盘子就要放到A塔
同理可得,要将3号盘放到A塔,那么上面的盘就要放到C塔
同理:
继续步骤:
每次从B塔中拿出来的大盘就要按照从大到小叠好
分析思路同理,这里就不叙说了
总结:这里细心的朋友就会发现了规律,奇数号盘为底盘时都是放在同一个塔(结合上面的图)这样,首先拿出的是1号盘(奇数盘)就可以判断应该放到哪个塔了
代码:
public class Test {
public static void main(String[] args) {
Test test = new Test();
test.test(5, 'A', 'B', 'C');
}
public void test(int num, char a, char b, char c) {
if (num == 1) {
System.out.println(a + "---->" + c);
} else {
//理解为实参位置一一对应A,B,C
test(num - 1, a, c, b);
System.out.println(a + "---->" + c);
test(num - 1, b, a, c);
}
}
}
解释:
好啦,今天的干货就到这啦~ 有什么建议或疑问的小伙伴欢迎到评论区留言!
标签:同理,游戏,递归函数,放到,圆盘,num,汉诺塔,test,号盘 From: https://blog.csdn.net/2401_83418369/article/details/142443776