Java漢諾塔算法

　　漢諾塔問題[又稱河內(nèi)塔]是印度的一個古老的傳說。

　　據(jù)傳開天辟地之神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。就是這看似簡單的問題，卻困擾了人們千年以上。

　　后來，這個傳說就演變?yōu)闈h諾塔游戲，玩法如下:

　　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號圓盤?，F(xiàn)在把B塔的4號圓盤房在C塔，現(xiàn)在推回去，把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塔，現(xiàn)在A塔空。n號圓盤是最大的圓盤，按問題要求我們終于把n號最大的圓盤放在了B塔，這下借助已空的A塔聯(lián)合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("請輸入盤數(shù)：");
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 }