アルゴリズム入門編:円盤が1枚、2枚、3枚のときの解法を考えよう

// ハノイの塔の解説 - 手動で円盤を移動する
import java.util.*;

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

    static List<LinkedList<Integer>> piles;

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

	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();
		}
	}

	static void moveOne(int from, int to) {
		int disk = piles.get(from).removeLast();
	    piles.get(to).add(disk);
	}

	public static void main(String args[] ) {
		int n = 3;
		System.out.println(n);

		initialize(n);
		printPiles();
		moveOne(0, 2);
		printPiles();
	}
}

// ハノイの塔の解説 - 手動で円盤を移動する
import java.util.*;

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

    static List<LinkedList<Integer>> piles;

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

	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();
		}
	}

	static void moveOne(int from, int to) {
		int disk = piles.get(from).removeLast();
	    piles.get(to).add(disk);
	}

	public static void main(String args[] ) {
		int n = 3;
		System.out.println(n);

		initialize(n);
		printPiles();
		moveOne(0, 2);
		printPiles();
	}
}

// ハノイの塔の解説 - 手動で円盤を移動する
import java.util.*;

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

    static List<LinkedList<Integer>> piles;

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

    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();
        }
    }

    static void moveOne(int from, int to) {
        int disk = piles.get(from).removeLast();
        piles.get(to).add(disk);
    }

    public static void main(String args[] ) {
        int n = 3;
        System.out.println(n);

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

// ハノイの塔の解説 - 手動で円盤を移動する
import java.util.*;

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

    static List<LinkedList<Integer>> piles;

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

    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();
        }
    }

    static void moveOne(int from, int to) {
        int disk = piles.get(from).removeLast();
        piles.get(to).add(disk);
    }

    public static void main(String args[] ) {
        int n = 3;
        System.out.println(n);

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

// ハノイの塔の解説 - 手動で円盤を移動する
import java.util.*;

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

    static List<LinkedList<Integer>> piles;

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

    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();
        }
    }

    static void moveOne(int from, int to) {
        int disk = piles.get(from).removeLast();
        piles.get(to).add(disk);
    }

    public static void main(String args[] ) {
        int n = 3;
        System.out.println(n);

        initialize(n);
        moveOne(0, 1); printPiles();
        moveOne(0, 2); printPiles();
        moveOne(1, 2); printPiles();

        moveOne(1, 2); printPiles();

        moveOne(2, 0); printPiles();
        moveOne(2, 1); printPiles();
        moveOne(0, 1); printPiles();
    }
}

// ハノイの塔の解説 - 手動で円盤を移動する
import java.util.*;

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

    static List<LinkedList<Integer>> piles;

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

    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();
        }
    }

    static void moveOne(int from, int to) {
        int disk = piles.get(from).removeLast();
        piles.get(to).add(disk);
    }

    public static void main(String args[] ) {
        int n = 3;
        System.out.println(n);

        initialize(n);
        moveOne(0, 1); printPiles();
        moveOne(0, 2); printPiles();
        moveOne(1, 2); printPiles();

        moveOne(1, 2); printPiles();

        moveOne(2, 0); printPiles();
        moveOne(2, 1); printPiles();
        moveOne(0, 1); printPiles();
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1
演習2

問題ログインすると模範解答や入力を見ることができます

演習課題「円盤3枚のを0番から1番の杭に手動で移動する」

右側のコードエリアのJavaプログラムは、ハノイの塔で、2枚の円盤を、0番の杭から2番の杭へ手動で移動します。このコードを使って、3枚の円盤を0番の杭から1番の杭に、移動する手順を出力してください。

期待する出力値

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

問題ログインすると模範解答や入力を見ることができます

演習課題「間違い探し」

右側のコードエリアのJavaプログラムは、ハノイの塔で、3枚の円盤を0番の杭から1番の杭に移動する手順を出力します。ただし、mainメソッドに間違いがあって、正しい手順を出力しません。このコードを修正して、正常な手順を出力してください。

期待する出力値

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

Tips

動画へ戻る

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

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

詳しい説明を読む

＃04:円盤が1枚、2枚、3枚のときの解法を考えよう

ここでは、円盤の枚数を増やした時に、どのように移動させるのか、いろいろ試してみたいと思います。円盤が1枚や2枚なら簡単ですが、3枚以上の時、どんな手順になるのか、プログラムで記述してみましょう。

参考になる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

ハノイの塔 - プログラミング学習のpaiza
https://paiza.jp/learning/hanoi

プログラミング学習 > アルゴリズム入門編 > アルゴリズム入門編: 「ハノイの塔」を学ぶ > 円盤が1枚、2枚、3枚のときの解法を考えよう

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

コードの実行

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

出力タイプ：