Java使用遞歸法解決漢諾塔問題的代碼示例

漢諾（Hanoi）塔問題：古代有一個梵塔，塔內有三個座A、B、C，A座上有n個盤子，盤子大小不等，大的在下，小的在上（如圖）。

有一個和尚想把這n個盤子從A座移到B座，但每次只能允許移動一個盤子，並且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。在移動過程中可以利用B座，要求打印移動的步驟。如果只有一個盤子，則不需要利用B座，直接將盤子從A移動到C。

• 如果有2個盤子，可以先將盤子1上的盤子2移動到B；將盤子1移動到c；將盤子2移動到c。這說明了：可以藉助B將2個盤子從A移動到C，當然，也可以藉助C將2個盤子從A移動到B。
• 如果有3個盤子，那麼根據2個盤子的結論，可以藉助c將盤子1上的兩個盤子從A移動到B；將盤子1從A移動到C，A變成空座；借助A座，將B上的兩個盤子移動到C。這說明：可以藉助一個空座，將3個盤子從一個座移動到另一個。
• 如果有4個盤子，那麼首先借助空座C，將盤子1上的三個盤子從A移動到B；將盤子1移動到C，A變成空座；借助空座A，將B座上的三個盤子移動到C。

Java代碼如下：

 public class Hanoi { public static void main(String[] args) { int disk = 3; //盤子move(disk, 'A', 'B', 'C'); } /* * 根據題意，從上向下編號=> 1 ~ n */ /** * * @param topN 源塔頂的盤子編號* @param from 從哪個塔移動* @param inter 中介，過渡的塔* @param to 目的塔*/ private static void move(int topN, char from, char inter, char to) { if (topN == 1) { System.out.println("Disk 1 from " + from + " to " + to); } else { move(topN - 1, from, to, inter); System.out.println("Disk " + topN + " from " + from + " to " + to); move(topN - 1, inter, from, to); } } }

out

 Disk 1 from A to C Disk 2 from A to B Disk 1 from C to B Disk 3 from A to C Disk 1 from B to A Disk 2 from B to C Disk 1 from A to C