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 }
