アルゴリズム入門編:カウントを追加する

// ハノイの塔の解説 - カウントを追加する
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);
	}

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

	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);
        hanoi(n-1, work, to, from);
    }

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

        initialize(n);
        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);
        hanoi(n-1, work, to, from);
    }

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

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

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

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

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

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1
演習2

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

演習課題「円盤4枚の移動回数を表示」

右側のコードエリアのJavaプログラムは、ハノイの塔で、円盤4枚を再帰で移動します。また、移動回数をcount変数で保持しており、移動手順は出力しません。このプログラムを修正して、円盤4枚の移動回数だけを出力してください。

期待する出力値

4
15

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

演習課題「間違い探し」

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

期待する出力値

4
--
count: 0
0: 4 3 2 1
1:
2:
--
count: 1
0: 4 3 2
1: 1
2:
--
count: 2
0: 4 3
1: 1
2: 2
--
count: 3
0: 4 3
1:
2: 2 1
--
count: 4
0: 4
1: 3
2: 2 1
--
count: 5
0: 4 1
1: 3
2: 2
--
count: 6
0: 4 1
1: 3 2
2:
--
count: 7
0: 4
1: 3 2 1
2:
--
count: 8
0:
1: 3 2 1
2: 4
--
count: 9
0:
1: 3 2
2: 4 1
--
count: 10
0: 2
1: 3
2: 4 1
--
count: 11
0: 2 1
1: 3
2: 4
--
count: 12
0: 2 1
1:
2: 4 3
--
count: 13
0: 2
1: 1
2: 4 3
--
count: 14
0:
1: 1
2: 4 3 2
--
count: 15
0:
1:
2: 4 3 2 1

Tips

動画へ戻る

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

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

詳しい説明を読む

＃07:カウントを追加する

ここからは、応用編として、ハノイの塔プログラムを効率よく実行する方法を考えます。ここでは、移動する円盤の枚数が増えた時、移動回数がどうなるか調べましょう。そのために、円盤の移動回数を表示するカウント変数を追加します。

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

プログラミング学習 > アルゴリズム入門編 > アルゴリズム入門編: 「ハノイの塔」を学ぶ > カウントを追加する

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

コードの実行

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

出力タイプ：