明解 Javaによるアルゴリズムとデータ構造 5_再帰的アルゴリズム
5-1 再帰の基本
メソッド内で自分を呼びだす
- 階乗
- ユークリッドの互除法
- ハノイの塔
5-2 再帰アルゴリズムの解析
- 解析
- トップダウン
- ボトムダウン
- 真に再帰的
- メソッド内で自身を複数回呼び出すもの
- 挙動が複雑
- 非再帰への書き換え
- 末尾再帰は容易 - http://d.hatena.ne.jp/yaneurao/20051008
- スタックを用いて過着換えることが出来る場合もあるが、一般に可能とは言い切れない
5-3 ハノイの塔
非再帰への書き下し解答があんまりしっくりこないので、あとで振り返る
5-4 8王妃問題
8x8チェス盤上に、互いに取れないように合計8クイーンを配置する問題
クイーンは縦横斜めに移動できる(飛車と角の動きを併せ持つ感じ)
列ごとに1王妃配置する場合の全配置パターン書き下しアルゴ。
なんてことない再帰なんだけど、すぐには挙動読み取れんかった。
- 分岐 branching
- 分割統治法 devide and conquer
class QueenB { static int[] pos = new int[8]; static void print() { for (int i = 0; i < 8; i++) { System.out.printf("%2d", pos[i]); } System.out.println(); } /** * 女王のいる行数: j=0 からスタート * * 女王j=0 で固定したまま列数をインクリメントして、潜る。 * 列i=7 まで来たら、結果を出力 * 列i=7 のまま 女王j++ -> j=7 まできたら、列i=7のセットは終わり。i=6にpopしてくる。 * * 列i=6における、j=0が完了し、j++ -> j=7 まできたら、列i=6のセットは終わり。i=5にpopしてくる。 * 列i=5における、j=0が完了し、j++ -> j=7 まできたら、列i=5のセットは終わり。i=4にpopしてくる。 * : * : * : * 列i=1における、j=0が完了し、j++ -> j=7 まできたら、列i=1のセットは終わり。done! * * @param i 王妃配置対象の列 */ static void set(int i) { // i は for (int j = 0; j < 8; j++) { // j は女王を配置する行数 pos[i] = j; if (i == 7) { print(); } else { set(i+1); // 考慮する対象列をインクリメント } } } public static void main(String[] args) { set(0); } }以下、挙動のメモ。
i=0 j=0から始まる 1 0 2 0 3 0 4 0 // set(5) 5 0 // set(6) 6 0 // set(7) 7 0 print 7 1 print 7 2 print 7 3 print 7 4 print 7 5 print 7 6 print 7 7 print 6 1 // set(7) 7 0 print 7 1 print 7 2 print 7 3 print 7 4 print 7 5 print 7 6 print 7 7 print 6 2 // set(7) 7 0 print 7 1 print 7 2 print 7 3 print 7 4 print 7 5 print 7 6 print 7 7 print 6 3 6 4 6 5 6 6 6 7 5 1 : : :8王妃問題のソルバー(解を盤面表示する)。 なお、このソルバーは
- 限定 bounding
- 分枝限定法 branching and bounding method
class EightQueen { static boolean[] flag_a = new boolean[8]; static boolean[] flag_b = new boolean[15]; static boolean[] flag_c = new boolean[15]; static int[] pos = new int[8]; static void print() { String[] board = new String[8]; for (int j = 0; j < 8; j++) { // j行 board[j] = ""; for (int i = 0; i < 8; i++) { // i列 board[j] += (pos[i] == j) ? "■" : "□"; } System.out.println(board[j]); } System.out.println(); } static void set(int i) { for (int j = 0; j < 8; j++) { if (flag_a[j] == false && flag_b[i + j] == false && flag_c[i - j + 7] == false) { pos[i] = j; if (i == 7) { print(); } else { flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true; set(i + 1); flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false; } } } } public static void main(String[] args) { set(0); } }上記ソルバーを走らせると、以下の様な盤が92面出力される。
■□□□□□□□ □□□□□□■□ □□□□■□□□ □□□□□□□■ □■□□□□□□ □□□■□□□□ □□□□□■□□ □□■□□□□□ ■□□□□□□□ □□□□□□■□ □□□■□□□□ □□□□□■□□ □□□□□□□■ □■□□□□□□ □□□□■□□□ □□■□□□□□ ■□□□□□□□ □□□□□■□□ □□□□□□□■ □□■□□□□□ □□□□□□■□ □□□■□□□□ □■□□□□□□ □□□□■□□□非再帰化、ちょっと考え中。
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る