汉诺塔

package com.atguigu.dac;
/**
 * 汉诺塔 -- 分治算法
 *
 * @author Dxkstart
 * @create 2022-04-12-15:13
 */
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(4,'A','B','C');
    }
    // 使用分治算法，汉诺塔的移动方法
    public static void hanoiTower(int num, char a, char b, char c) {
        // 如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘从 " + a + "->" + c);
        } else {
            // 如果我们有 n >= 2 情况，我们总是可以看做是两个盘
            //  1.最下边的一个盘       2.上面的所有盘
            // 一：先把最上面的所有盘A -> B,移动过程会使用到c塔
            hanoiTower(num - 1, b, a, c);
            // 二：把最下边的盘A -> C
            System.out.println("第" + num + "个盘从" + a + "->" + c);
            // 三：把B塔的所有盘从B -> C,移动过程使用到a塔
            hanoiTower(num - 1,b,a,c);
        }
    }
}