汉诺塔问题

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

思路：

如果是有一个盘， A->C

如果我们有 n >= 2 情况，我们总是可以看做是两个盘——一是最下边的盘，二是上面的其余所有盘

  1. 先把 最上面的盘 A->B，中间需借助C盘，即hanoiTower(num-1,a,c,b)
  2. 再把最下边的盘 A->C，System.out.println("第"+num+"个盘从 "+"A->C")
  3. 最后把B塔的所有盘 从 B->C，中间需借助A盘，即hanoiTower(num-1,b,a,c)

代码实现

HanoiTower

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.yukinoshita.algorithm.hanoitower;

public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(3,'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{
            //如果num >= 2，我们总是可以看两个盘：1最下面的盘 和 上面的所有盘
            //1. 先把 上面的盘从A移动到B，移动过程会使用到C
            hanoiTower(num-1,a,c,b);
            //2. 再把 最下面的盘从A移动到C
            System.out.println("第"+num+"个盘从 "+a+"->"+c);
            //3. 把 B中所有盘移动到C，移动过程使用到A
            hanoiTower(num-1,b,a,c);
        }
    }
}