時隔3天，我終於理解了四個盤子的漢諾塔問題（Java實現）

語言: CN / TW / HK
時間 2023-03-19 07:15:04
主題:

1.漢諾塔問題

漢諾塔是啥大家都知道，漢諾塔的故事這裡就不做介紹了，有讀者感興趣的可以去搜一搜，作者是用Java來實現的漢諾塔。

程式設計實現把 A 的 n 個盤子移動到 C

這是一個要使用遞迴解決的問題

要求：

  • 每次只能移動1個盤子
  • 大盤子只能放在小盤子下面

我們的目標是要解決4個盤子的漢諾塔問題，下面是移動完成的示意圖

移動前：

image.png

移動後：

image.png

動態演示圖 ​

​

2.思路講解

2.1 一個盤子的情況。

如果是一個盤子，直接將A上的盤子移動到C即可。（一步）

image.png

步驟：A -> C

動態演示圖 ​

​

2.2 兩個盤子的情況

如果是兩個盤子，先將A上的小盤子移動到B上。\ 再將A上的大盤子移動到C上，最後將B上的小盤子移動到C上即可。（三步）

​

步驟：A -> B    A -> C   B -> C

動態演示圖

​

2.3 三個盤子的情況

如果是三個盤子，先將A上的盤子移動到C上。\ 移動後將A上的盤子移動到B上，再將C上的盤子移動到B。\ 然後將A上的盤子移動到C，再將上B的盤子移動到A。\ 最後將B的盤子移動到C，再將A移動到C即可。（七步）

image.png

步驟：A -> C     A -> B     C -> B     A -> C     B -> A     B - > C     A -> C

動態演示圖

​

根據三個例子可以發現，除了只有一個盤子的情況。\ 盤子在移動到C的過程中會有 n-1 個盤子在B上暫存。

兩個盤子 n-1 就是會有一個盤子在B上暫存

image.png

三個盤子 n-1 就是會有兩個個盤子在B上暫存

image.png

所以解決四個盤子的方法就是先想辦法把三個的盤子暫存到B上\ 再把最後一個盤子直接放到C上。對於B上的三的盤子，可以借用A逐步放到C上。

3.四個盤子的漢諾塔問題

3.1 四個盤子的思路

  1. 藉助C把 n-1 個盤子移動到B
  2. 把A剩下的盤子移動到C
  3. 藉助A把 n-1 個盤子移動到C

3.2 實現程式碼來解決四個盤子的漢諾塔

```Java / * @name 遞迴求解漢諾塔 * @param start 起始位置 * @param transit 中轉位置 * @param end 目標位置 / public static void hanio(char start, char transit, char end, int number) { if (1 == number) {//只有一個盤子 //直接將盤紙移動到C move(start, end); return; }else {//盤子大於1個 //此時 transit 是目標位置；而 end 是中轉位置 hanio(start, end, transit, number - 1);//藉助C將n-1個盤子移動到B上 move(start, end); //此時 start 是中轉位置，而end是目標位置 hanio(transit, start, end, number - 1);//藉助A把n-1個盤子移動到C上 } }

/**
 * @param start     起始位置
 * @param transit   目標位置
 **/
public static void move(char start, char transit) {
    System.out.print(start +"->"+ transit + " ");
}

public static void main(String[] args) {
    hanio('A', 'B', 'C', 1);
    System.out.println();
    hanio('A', 'B', 'C', 2);
    System.out.println();
    hanio('A', 'B', 'C', 3);
    System.out.println();
    hanio('A', 'B', 'C', 4);
}

```

程式碼結果：

image.png

前三行分別是1、2、3個盤子的移動過程\ 對照之前的思路講解可以發現步驟沒有錯誤。

第四行就是四個盤子的漢諾塔所需要的步驟。（十五步）

「」