アルゴリズム入門編:円盤の移動回数を調べる

// ハノイの塔の解説 - 移動回数を調べる
import java.util.*;

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

    static List<LinkedList<Integer>> piles;
    static int count;

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

        // 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);

        count = 0;
    }

    static void printPiles() {
        System.out.println("--");
        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++;
    }

    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;
        System.out.println(n);

        initialize(n);
        printPiles();
        hanoi(n, 0, 2, 1);
    }
}

// ハノイの塔の解説 - 移動回数を調べる
import java.util.*;

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

    static List<LinkedList<Integer>> piles;
    static int count;

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

        // 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);

        count = 0;
    }

    static void printPiles() {
        System.out.println("--");
        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++;
    }

    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;
        System.out.println(n);

        initialize(n);
        printPiles();
        hanoi(n, 0, 2, 1);
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

Tips

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃08:円盤の移動回数を調べる

ここでは、追加したカウント変数を利用して、円盤の枚数が変化した時、その移動回数を調べます。

参考になるWebサイト

ハノイの塔 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94

ハノイの塔解説
http://www.slideshare.net/paiza_official/ss-42702412

プログラミング学習 > アルゴリズム入門編 > アルゴリズム入門編: 「ハノイの塔」を学ぶ > 円盤の移動回数を調べる

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：