アルゴリズム入門編:再帰で実装する

// ハノイの塔の解説 - 再帰で実装する
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();
		moveOne(0, 1); printPiles();
		moveOne(2, 1); printPiles();

		moveOne(0, 2); printPiles();

		moveOne(1, 0); printPiles();
		moveOne(1, 2); 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();
		moveOne(0, 1); printPiles();
		moveOne(2, 1); printPiles();

		moveOne(0, 2); printPiles();

		moveOne(1, 0); printPiles();
		moveOne(1, 2); 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);
	}

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

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

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

// ハノイの塔の解説 - 再帰で実装する
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, other, to);
        moveOne(from, to);
        printPiles();
        hanoi(n-1, other, to, from);
    }

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

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

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1
演習2

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

演習課題「円盤4枚を再帰で移動」

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

期待する出力値

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

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

演習課題「間違い探し」

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

期待する出力値

Tips

動画へ戻る

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

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

詳しい説明を読む

＃06:再帰で実装する

ここでは、ハノイの塔で円盤を動かす手順を、再帰呼び出しで実装します。
大きな問題を解くために、より小さな問題の答えを使っていく場合、再帰呼び出しで実装できます。

参考になるWebサイト

paiza ラーニング - アルゴリズム入門編1:FizzBuzzとフィボナッチ数を学ぶ
https://paiza.jp/works/algorithm/primer/algorithm1

ハノイの塔 - 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

プログラミング学習 > アルゴリズム入門編 > アルゴリズム入門編: 「ハノイの塔」を学ぶ > 再帰で実装する

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

コードの実行

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

出力タイプ：