首页 > 代码库 > 汉诺塔-Hanoi

汉诺塔-Hanoi

1. 问题来源:

汉诺塔(河内塔)问题是印度的一个古老的传说。

  法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

  后来,这个传说就演变为汉诺塔游戏,玩法如下:
  (1). 有三根杆子A,B,C。A杆上有若干碟子
  (2). 每次移动一块碟子,小的只能叠在大的上面
  (3). 把所有碟子从A杆全部移到C杆上

2. 解题思路:

  题中只给了三座塔,我们利用B塔将圆盘全部移动到在C塔。

  为了将N个盘子从A移动到C,需要先将第N个盘子上面的N-1个盘子移动到B上,这样才能将第N个盘子移动到C上。

  同理,为了将第N-1个盘子从B移动到C上,需要将N-2个盘子移动到A上,这样才能将第N-1个盘子移动到C上。

  通过递归就可以实现汉诺塔问题的求解。

3. 源代码:

 1 public class Hanoi {
 2 
 3     private static void move(int level, char from, char inter, char to) {
 4         if (level == 1) {
 5             System.out.println(level + ":" + from + "->" + to);
 6         } else {
 7             move(level - 1, from, to, inter);
 8             System.out.println(level + ":" + from + "->" + to);
 9             move(level - 1, inter, from, to);
10         }
11     }
12 
13     public static void move(int level) {
14         move(level, ‘A‘, ‘B‘, ‘C‘);
15     }
16 }

测试代码:

1 public class Main {
2     public static void main(String[] args) {
3         int nDisks = 3;
4         Hanoi.move(nDisks);
5     }
6 }

测试结果:

1:A->C
2:A->B
1:C->B
3:A->C
1:B->A
2:B->C
1:A->C

当然,在这里圆盘的个数nDisks可以通过java.util.Scanner从控制台进行读入:

 1 import java.util.Scanner;
 2 
 3 public class Main {
 4     public static void main(String[] args) {
 5         Scanner in = new Scanner(System.in);
 6         int nDisks = in.nextInt();
 7         in.close();
 8         Hanoi.move(nDisks);
 9     }
10 }

汉诺塔问题的时间复杂度为O(2^n)

汉诺塔-Hanoi