当前位置：首页 > article >正文

用递归函数实现汉诺塔游戏

article 2024/11/14 21:09:55

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);
        }
    }

}

解释：