【Java】ハノイの塔1

ハノイの塔とは

ハノイの塔とは、19世紀にフランスの数学者エドゥアール・リュカによって提唱されました。
ハノイの塔は、3本の杭とその中に円盤が積まれた状態で始まります。最初は、すべての円盤が1つの杭に大きい順に積まれています。この状態から、下記のルールに従ってすべての円盤を別の杭に移動させることが目的です。

1. 1度に1つの円盤のみ移動できます。
2. 大きな円盤を小さな円盤の上に置くことはできません。

「ハノイの塔」で検索し画像を探してみると、一度は見たことがあるかもしれません。

ハノイの塔1のコード

まず、ここでは、下記のハノイの塔の最初の状態を出力できるコードを紹介します。

ハノイの塔の最初の状態

0: 3 2 1
1:
2:

以下、ハノイの塔の最初の状態を出力できるコード。

import java.util.*;

public class Main {
    /*
    3本の杭をまとめるList。                -> 外側のリスト:piles
    杭の状態を表すLinkedList。円盤を格納。  -> 内側のリスト:名前なし
    円盤の大きさを整数で表す。              -> 内側のリストの要素:名前なし
    */
    
    // 二重リストpilesを宣言
    static List <LinkedList<Integer>> piles;
    
    // ハノイの塔を初期化するメソッド
    static void initialize(int n) {
        // 3本の杭をまとめるListの初期化
        piles = new LinkedList<>();
        
        // 杭の状態を表すLinkedListを3つ生成し、3本の杭を作る。
        for (int i = 0; i < 3; i++) {
            piles.add(new LinkedList<>());
        }
        
        // 0番目の杭に、n枚の円盤を追加
        for (int i = n; i >= 1; i--) {
            piles.get(0).add(i);
        }
    }
    
    // ハノイの塔を表示するメソッド
    static void printPiles() {
        System.out.println("--"); // 区切り線を表示
        
        for (int i = 0; i < 3; i++) {
            System.out.print(i + ":"); // 杭の番号を表示
            
            for (int disk : piles.get(i)) {
                System.out.print(" " + disk); // 円盤の大きさを表示
            }
            System.out.println(); // 改行して次の杭に移る
        }
    }
    
    public static void main(String args[] ) {
        int n = 3; // 円盤の数を宣言
        System.out.println(n); // 円盤の数を表示
        
        initialize(n); // ハノイの塔を初期化

        printPiles(); // ハノイの塔の最初の状態を表示　
                      // 0: 3 2 1
                      // 1:
                      // 2:
    }
}

ハノイの塔1のコードの解説

二重リストの宣言

static List <LinkedList<Integer>> piles;

pilesという変数は、List型のオブジェクトであり、その要素としてLinkedList<Integer>オブジェクトを持ちます。
さらに、LinkedList<Integer>オブジェクトは、Integer型の要素を持ちます。

繰り返しになりますが、二重リストであるpilesは、上記のように、
外側のListは、要素としてLinkedListを持ち、
内側のLinkedListは、要素としてIntegerを持ちます。

---

ハノイの塔を初期化するメソッド

static void initialize(int n) {
    // 3本の杭をまとめるListの初期化
    piles = new LinkedList<>();
    
    // 杭の状態を表すLinkedListを3つ生成し、3本の杭を作る。
    for (int i = 0; i < 3; i++) {
        piles.add(new LinkedList<>());
    }
    
    // 0番の杭に、n枚の円盤を追加
    for (int i = n; i >= 1; i--) {
        piles.get(0).add(i); // 最初の杭に円盤を追加する
    }
}

上記のコードをその都度、標準出力に出力し、その結果を書き加えたものが下記になります。

// ハノイの塔を初期化するメソッド -> [[3, 2, 1], [], []]を作る
static void initialize(int n) {
    // 3本の杭をまとめるListの初期化
    piles = new LinkedList<>();
    System.out.println(piles.toString()); // 出力結果 -> []
    
    // 杭の状態を表すLinkedListを3つ生成し、3本の杭を作る。
    for (int i = 0; i < 3; i++) {
        piles.add(new LinkedList<>());
    }
    System.out.println(piles.toString()); // 出力結果 -> [[], [], []]
    
    // 0番の杭に、n枚の円盤を追加
    for (int i = n; i >= 1; i--) {
        piles.get(0).add(i); // 最初の杭に円盤を追加する
    }
    System.out.println(piles.toString()); // 出力結果 -> [[3, 2, 1], [], []]
}

1. 仮引数nを受け取るinitializeメソッドを定義して、
2. 変数pilesに外側のListのインスタンスを代入します。

pilesの出力結果は[]となり、Listが1つ作成されました。

3. 3回の反復処理を行うfor文を定義して、
4. 変数piles（＝Listのインスタンス）に3つのLinkedListのインスタンスを生成します。

pilesの出力結果は[[], [], []]となり、1つのListの中に3つのLinkedListが作成されました。

5. 後述しますがnは3なので、i = 3 → 2 → 1と繰り返す、for文を定義して、
6. 0番目のLinkedListにiを追加します。

pilesの出力結果は[[3, 2, 1], [], []]となります。

---

ハノイの塔を表示するメソッド

static void printPiles() {
    System.out.println("--"); // 区切り線を表示
    
    for (int i = 0; i < 3; i++) {
        System.out.print(i + ":"); // 杭の番号を表示
        
        for (int disk : piles.get(i)) {
            System.out.print(" " + disk); // 円盤の大きさを表示
        }
        System.out.println(); // 改行して次の杭に移る
    }
}

1. printPilesメソッドを定義して、
2. 区切り線--を出力します。
3. for文を定義して、
4. 0番目の杭を表す0:を出力します。以降、順番に1: → 2:と出力します。
5. for文の中に拡張for文を定義して、0番目の杭のLinkedListの要素を取り出し、変数diskに代入します。
6. 半角スペースと0番目の杭の円盤3 → 2 → 1を出力します。
7. 改行を出力して、次の1番目の杭に移るために3.for文に戻ります。

---

mainメソッド

public static void main(String args[] ) {
    int n = 3; // 円盤の数を宣言
    System.out.println(n); // 円盤の数を表示
    
    initialize(n); // ハノイの塔を初期化

    printPiles(); // ハノイの塔の最初の状態を表示
}

mainメソッドで、

1. 変数nに3を代入します。これは円盤の枚数が3であることを宣言しています。
2. 変数nを出力します。これは円盤の枚数である3を出力します。
3. 3が代入された実引数nを渡すinitializeメソッドを呼び出します。
4. printPilesを呼び出します。これにより下記の通り出力されます。

0: 3 2 1
1:
2:

---

ハノイの塔1のコードによって、最終的な標準出力は下記の通り出力されます。

3
--
0: 3 2 1
1:
2: