How to play the Tower of Hanoi

作者 ：ふり

专栏 ：JavaSE

格言 ： I came ; I saw ; I conquer

汉诺塔

• 汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘.梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上,移动过程中必须遵守以下规则：
• 每次只能移动柱子最顶端的一个圆盘;
• 每个柱子上,小圆盘永远要位于大圆盘之上;

思路讲解

When the starting column is only on 1 个圆盘时,We can easily move it to the target bar

A ->C

When there is on the starting column 2 个圆盘时,先将AMove to the small plate on topB上;再将AThe large plate on the move toC上,最后将BMove to the small plate on topC上即可

A -> B 、 A -> C、 B -> C

如果是三个盘子,先将A上的盘子移动到C上;再将A上的盘子移动到B上,再将C上的盘子移动到B,再将A 上的盘子移动到C,will go upB的盘子移动到A,再将B的盘子移动到C,最后将A移动到C即可.

A -> C 、 A -> B 、 C -> B 、 A -> C 、 B -> A 、 B - > C 、 A -> C

---

According to three examples can be found,Except when there is only one plate.The plate is moving toC的过程中会有 n-1 个盘子在B上暂存.

两个盘子 n-1 There will be a plateB上暂存

三个盘子 n-1 There will be two platesB上暂存

---

3One plate of the Tower of Hanoi problem

思路

• 借助C把 n-1 个盘子移动到B
• 把AMove the remaining plates toC
• 借助A把 n-1 个盘子移动到C

public class hannuota {
    
    /** * @name 递归求解汉诺塔 * @param str 起始位置 * @param transit 中转位置 * @param end 目标位置 * **/
    public static void hanio(char str, char transit, char end, int number) {
    
        if (1 == number) {
    //只有一个盘子
            //Move the tray paper directly to C
            move(str, end);
            return;
        }else {
    //The plate is larger than1个
            //此时 transit 是目标位置;而 end 是中转位置
            hanio(str, end, transit, number - 1);//借助C将n-1个盘子移动到B上
            move(str, end);
            //此时 start 是中转位置,而end是目标位置
            hanio(transit, str, end, number - 1);//借助A把n-1个盘子移动到C上
        }
    }

    /** * @param str 起始位置 * @param transit 目标位置 **/
    public static void move(char str, char transit) {
    
        System.out.print(str+"->"+ transit + " ");
    }
    public static void main(String[] args) {
    
        hanio('A', 'B', 'C', 1);
        System.out.println();
        hanio('A', 'B', 'C', 2);
        System.out.println();
        hanio('A', 'B', 'C', 3);
        System.out.println();
        hanio('A', 'B', 'C', 4);
    }
}