Java汉诺塔算法

Java汉诺塔算法

 

　　汉诺塔问题[又称河内塔]是印度的一个古老的传说。

　　据传开天辟地之神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。就是这看似简单的问题，却困扰了人们千年以上。

　　后来，这个传说就演变为汉诺塔游戏，玩法如下:

　　1.有三根杆子A,B,C。A杆上有若干碟子  
　　2.每次移动一块碟子,小的只能叠在大的上面  
　　3.把所有碟子从A杆全部移到C杆上

　　解题思维：题中只给了三座塔，我们利用C塔将圆盘堆在B塔。首先将A塔的1号圆盘放在B塔，A塔的2号圆盘放在C塔，再把放在B塔的1号圆盘放在C塔，此时C塔拥有两个圆盘按要求自下而上从小到大排列。接下来将A塔的3号圆盘放在B塔，将C塔的1号圆盘放在B塔，把C塔德2号圆盘放在A塔，再把B塔的1号圆盘放在A塔，此时C塔空，1号2号按要求排在A塔，B塔只有3号圆盘。此时把B塔3号圆盘放在C塔，把A塔德1号放在B塔吗，把A塔德2号房在C塔，再把B塔德1号放在C塔，此时B塔空，C塔按要求排有123号圆盘。这次把A塔的4号圆盘放在B塔，这次就比较麻烦了先把C塔的1号放在A塔，C塔的2号房在B塔，再把A塔德1号放在B塔，把C塔德3号放在A塔，再把B塔的1号放在C塔，把B塔德2号放在A塔，再把C塔德1号放在A塔，此时C塔空，B塔只有4号圆盘，A塔按要求房有123到N号圆盘，缺4号圆盘。现在把B塔的4号圆盘房在C塔，现在推回去，把A塔德1号房在C塔，A塔的2号房在B塔，再把C塔的1号放在B塔，把A塔德3号房再C塔，此时刚好是3号压4号于C塔，再把，B塔的1号房在A塔，把C塔的2号放在C塔，把A塔的1号放在C塔，这下刚好推回来，此时B塔空，A塔最上面是5号圆盘，C塔按要求放有1234号圆盘。

　　按这样的递推方法，将n-1个圆盘按要求放在C塔，第n个圆盘放在B塔，现在A塔空。n号圆盘是最大的圆盘，按问题要求我们终于把n号最大的圆盘放在了B塔，这下借助已空的A塔联合BC塔推回来，就可以把n个圆盘按要求放在B塔。

 

 1 import java.io.BufferedReader;
 2 import java.io.InputStreamReader;
 3 
 4 public class Hanoi {
 5     public static void main(String args[]) throws Exception {
 6         int n;
 7         BufferedReader buf = 
 8                 new BufferedReader(new InputStreamReader(System.in));
 9         System.out.print("请输入盘数：");
10         n = Integer.parseInt(buf.readLine());
11         Hanoi hanoi = new Hanoi();
12         hanoi.move(n, 'A', 'B', 'C');
13     }
14 
15     public void move(int n, char a, char b, char c) {
16         if (n == 1)
17             System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
18         else {
19             move(n - 1, a, c, b);
20             System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
21             move(n - 1, b, a, c);
22         }
23     }
24 }