🎯

【Java】ハノイの塔3

2024/02/25に公開

Java

初心者

tech

ハノイの塔で指定した移動回数の円盤の状態を出力する方法を解説したいと思います。
ただし、事前に説明が必要なものについて解説してから、コードを紹介したいと思います。

事前説明

1. ハノイの塔の円盤の移動回数の公式について

円盤がn枚の時の移動回数は、下記のとおりです。

2^n - 1

これをJavaで表現すると、下記のようになります。

Math.pow(2, n) - 1

Math.pow(2, n)は2のn乗を表します。
powメソッドは、第１引数を底とし、第2引数を指数とする指数関数を計算するものです。

2. System.exit()について

System.exit()はJavaのプログラムを終了させるものです。
引数が0の場合は正常終了と見なし、0以外の場合は何らかのエラーを示して終了します。

ハノイの塔3のコード

ハノイの塔2のコードを基礎にして、指定した移動回数の円盤の状態を出力するコードを紹介します。

import java.util.*;

class Main {
    /*
    piles    :  3本の杭をListに格納
    名前なし :  杭は、LinkedList。円盤を格納
    名前なし :  円盤は、円盤の大きさを整数で表す。 ex. 4 3 2 1
    */

    static List<LinkedList<Integer>> piles;
    
    // 変数countの宣言
    static int count;
    
    // 変数targetの宣言
    static int target;

    static void initialize(int n) {
        piles = new LinkedList<>();

        for (int i=0; i<3; i++)
            piles.add(new LinkedList<>());

        for (int i=n; i>=1; i--)
            piles.get(0).add(i);

        // 変数countの初期化
        count = 0;
    }

    static void printPiles() {
        System.out.println("--");
        
        // 変数countを出力
        System.out.println("count: " + count);

        for (int i=0; i<3; i++) {
            System.out.print(i + ":");
            for (int disk : piles.get(i))
                System.out.print(" " + disk);

          System.out.println();
        }
    }

    static void moveOne(int from, int to) {
        int disk = piles.get(from).removeLast();
        piles.get(to).add(disk);
        
        // 変数countにより円盤の移動回数をカウントする
        count++;
        
        // 変数targetの回数になったら、その状態を出力し、プログラムを終了
        if (count == target) {
            printPiles();
            System.exit(0);
        }
    }

    static void hanoi(int n, int from, int to, int work) {
        if (n == 0) {
            return;
        }

        hanoi(n-1, from, work, to);
        moveOne(from, to);
        // printPiles(); -> 途中経過を出力しない
        hanoi(n-1, work, to, from);
    }

    public static void main(String args[] ) {
        int n = 3;
        
        // target回数を指定
        target = 6;
        
        // target回数が公式の円盤の移動回数以内の場合
        if (target <= Math.pow(2, n) - 1) {
            System.out.println(n);
        // target回数が公式の円盤の移動回数を超えた場合
        } else {
            System.out.println("指定した回数が円盤の移動回数より大きいです。");
            System.exit(1);
        }
        
        initialize(n);
        printPiles();
        hanoi(n, 0, 2, 1);
    }
}

ハノイの塔2のコードから書き加えたのは、コメントを付けた箇所です。

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

今回はコメントを付けた箇所のみ解説します。

class Main {
    static List<LinkedList<Integer>> piles;
    
    // 変数countの宣言
    static int count;
    
    // 変数targetの宣言
    static int target;

Mainクラスのフィールドとして、

変数countの宣言をします。countは円盤の移動回数を表します。
変数targetの宣言をします。targetは指定の回数を表します。

static void initialize(int n) {
    piles = new LinkedList<>();

    for (int i=0; i<3; i++)
        piles.add(new LinkedList<>());

    for (int i=n; i>=1; i--)
        piles.get(0).add(i);

    // 変数countの初期化
    count = 0;
}

初期化を行うinitializeメソッドで、

変数countを初期化します。

static void printPiles() {
        System.out.println("--");
        
        // 変数countを出力
        System.out.println("count: " + count);

        for (int i=0; i<3; i++) {
            System.out.print(i + ":");
            for (int disk : piles.get(i))
                System.out.print(" " + disk);

          System.out.println();
        }
    }

ハノイの塔を出力するprintPilesメソッドで、

文字列count: と変数countを出力します。

static void moveOne(int from, int to) {
    int disk = piles.get(from).removeLast();
    piles.get(to).add(disk);
    
    // 変数countにより円盤の移動回数をカウントする
    count++;
    
    // 変数targetの回数になったら、その状態を出力し、プログラムを終了
    if (count == target) {
        printPiles();
        System.exit(0);
    }
}

円盤を動かすmoveOneメソッドで、

円盤を動かす毎に、変数countの値を1ずつ増やします。
count == targetという条件式のif文を定義して、
条件を満たせば、printPilesメソッドを呼び出し、
このプログラムを正常終了とさせます。

static void hanoi(int n, int from, int to, int work) {
    if (n == 0) {
        return;
    }

    hanoi(n-1, from, work, to);
    moveOne(from, to);
    // printPiles(); -> 途中経過を出力しない
    hanoi(n-1, work, to, from);
}

再帰処理を行うhanoiメソッドで、

printPilesメソッドをコメントアウトして、円盤の移動の途中経過を出力しないようにします。

public static void main(String args[] ) {
    int n = 3;
    
    // target回数を指定
    target = 6;
    
    // target回数が公式の円盤の移動回数以内の場合
    if (target <= Math.pow(2, n) - 1) {
        System.out.println(n);
    // target回数が公式の円盤の移動回数を超えた場合
    } else {
        System.out.println("指定した回数が円盤の移動回数より大きいです。");
        System.exit(1);
    }
    
    initialize(n);
    printPiles();
    hanoi(n, 0, 2, 1);
}

Mainメソッドで、

targetの回数を指定します。
targetの回数が公式の円盤の移動回数以内という条件式のif文を定義して、
条件を満たせば、変数n（＝円盤の枚数）を出力します。
それ以外の場合（targetの回数が公式の円盤の移動回数を超えた場合）、
文字列で指定した回数が円盤の移動回数より大きいです。と出力して、
このプログラムをエラーを示して終了させます。

出力結果

target = 6の場合
```
3
--
count: 0
0: 3 2 1
1:
2:
--
count: 6
0: 1
1:
2: 3 2
```
上記のようになり、指定した6回目の円盤の状態を出力することができました。
target = 8の場合
```
指定した回数が円盤の移動回数より大きいです。
```
targetの回数が公式の円盤の移動回数（7回）を超えたため、上記が出力され、エラーを示してプログラムが終了されました。