アルゴリズムとデータ構造 2013年7月1日 酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html 1 クイックソート 基準値を決定 10 8 3 15 5 32 12 1 6 24 基準値を決定 8 3 基準値を決定 基準値を決定 1 6 ＜ 10 ＜ 15 32 12 24 5 基準値を決定 基準値を決定 基準値を決定 整列済み 3 1 ＜ 5 ＜ 8 1 ＜ 3 6 6 ＜ 8 5 1 3 5 6 10 12 ＜ 15 ＜ 32 24 10 12 15 24 ＜ 32 8 10 12 15 24 32 2 public class QuickSort { public static <E extends Comparable<E>> int sort(E[] array) { return sort(array, 0, array.length - 1); } private static <T extends Comparable<T>> T getPivot(T[] array, int start, int end) { return array[start]; } private static <T extends Comparable<T>> int sort(T[] array, int start, int end) { int n = 0; if ((end - start) < 1) return n; // データが1個以下のとき、ソート完了 T pivot = getPivot(array, start, end); int left = start; // start以上、left未満が仕分け済 int right = end; // rightより上、end以下が仕分け済 split: while (left <= right) { for (; left <= right; left++) { n++; if (pivot.compareTo(array[left]) > 0) continue; // pivot以上の値を探せた for (; left <= right; right--) { n++; if (pivot.compareTo(array[right]) < 0) continue; // pivot以下の値を探せた if (left < right) { T temp = array[left]; array[left++] = array[right]; array[right--] = temp; continue split; } else break split; }}} n += sort(array, start, left - 1); n += sort(array, right + 1, end); return n; }} 3 private final static String[] test_data_string = { "東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"}; private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10}; public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); Integer[] data2 = test_data_int.clone(); n = sort(data2); for (Integer e : data2) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); System.out.print(sb.toString()); } 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 79 4 クイック ソート （最悪の 場合） 32 24 15 12 10 8 6 5 3 1 24 15 12 10 8 6 5 3 1 ＜ 15 12 10 8 6 5 3 1 ＜ 24 32 12 10 8 6 5 3 1 ＜ 10 8 6 5 3 1 ＜ 8 6 5 3 1 ＜ 10 12 15 24 32 6 5 3 1 ＜ 8 10 12 15 24 32 5 3 1 ＜ 6 8 10 12 15 24 32 3 1 ＜ 5 6 8 10 12 15 24 32 1 ＜ 3 5 6 8 10 12 15 24 32 1 3 5 6 8 32 15 24 32 12 15 24 32 10 12 15 24 32 5 再帰的アルゴリズム • 再帰は重要なアルゴリズムの概念である． • とくに参照型を用いた柔軟なデータ構造を 扱う場合には，基本的に再帰的アルゴリ ズムを用いるしかない． • ここでは，再帰的アルゴリズムを詳細に検 討し，その動作の理解をする 6 漸化式からの計算 • 階乗 f (0) 1, f ( x) x! x f ( x 1) • フィボナッチ数列 f (0) 1, f (1) 1, f ( x) f ( x 2) f ( x 1) • いずれも再帰的に関数を呼ぶ形に書ける 再帰呼び出しの場合 f(0)やf(1)といった 数列の最初の値のところで停止 7 階乗を求めるプログラム public class Factorial { // 再帰版 public static int factorial(int aTarget) { System.out.println("factorial(" + aTarget + ")に入ります"); if(0 == aTarget){ System.out.println("factorial(0) から出ます: 1"); return 1; } int total = aTarget * Factorial.factorial(aTarget - 1); System.out.println("factorial(" + aTarget + ") から出ます: " + total); return total; } // ループ版 public static int factorialWithoutRecursion(int aTarget) { if(0 == aTarget){ return 1; } int total = aTarget; for(int count = aTarget - 1; 0 < count; count--){ total *= count; } return total; } 末尾再帰なので再帰 } 呼び出しをループに 変換することは容易 8 フィボナッチ数を求めるプログラム public class Fibonatti { // 再帰版 public static int fibonatti(int aTarget) { System.out.println("fibonatti(" + aTarget + ") に入ります"); if((0 == aTarget) || (1 == aTarget)){ System.out.println("fibonatti(" + aTarget + ") から出ます: 1"); return 1; } int total = fibonatti(aTarget - 2) + fibonatti(aTarget - 1); System.out.println("fibonatti(" + aTarget + ") から出ます: " + total); return total; } // ループ版 public static int fibonattiWithoutRecursion(int aTarget) { if((0 == aTarget) || (1 == aTarget)){ return 1; } f(0)から順にたどれば int old1 = 1, old2 = 1, total = 0; 結果を求めることがで for(int count = 2; count <= aTarget; count++){ きる total = old1 + old2; old2 = old1; old1 = total; f(x)に必要とされるの } はf(x-1)とf(x-2)なので return total; 変数を2つ追加すれば } } 足る 9 [sakai@star 13]$ java FactorialTest 720 factorial(6)に入ります factorial(5)に入ります factorial(4)に入ります factorial(3)に入ります factorial(2)に入ります factorial(1)に入ります factorial(0)に入ります factorial(0) から出ます: 1 factorial(1) から出ます: 1 factorial(2) から出ます: 2 factorial(3) から出ます: 6 factorial(4) から出ます: 24 factorial(5) から出ます: 120 factorial(6) から出ます: 720 [sakai@star 13]$ [sakai@star 13]$ java FibonattiTest 8 fibonatti(5) に入ります fibonatti(3) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(1) に入ります fibonatti(2) から出ます: 2 fibonatti(1) から出ます: 1 fibonatti(3) から出ます: 3 fibonatti(2) から出ます: 2 fibonatti(3) に入ります fibonatti(4) に入ります fibonatti(1) に入ります fibonatti(2) に入ります fibonatti(1) から出ます: 1 fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) から出ます: 3 fibonatti(4) から出ます: 5 fibonatti(5) から出ます: 8 10 [sakai@star 13]$ 通りがけ順の走査 二分木を次のルールで走査 1. 自分の左部分木をたどる 2. 自分を訪ねる 3. 自分の右部分木をたどる 4. 親の頂点に戻る 29 20 二分探索木を走査すると 横倒しの木を表示できる 14 7 24 19 21 32 30 48 31 11 public void printTreeRecursive() { this.printTreeRecursive(this.root, 0); } private void printTreeRecursive(MyNode aLocalRootNode, int depth) { if(null == aLocalRootNode) return; this.printTreeRecursive(aLocalRootNode.getRight(), depth+1); for(int i=0; i < depth; i++){ System.out.print("\t"); } System.out.println(aLocalRootNode.getData().toString()); this.printTreeRecursive(aLocalRootNode.getLeft(), depth+1); } 再帰呼び出し版 木の根が左にある、 左から右へ生えている 木を表示するプログラム (29, "リンゴ") (20, "ミカン") (14, "サクランボ") (32, "バナナ") (30, "イチゴ") (24, "ブルーベリー") ( 7, "グレープフルーツ") (21, "レモン") (48, "メロン") (31, "スイカ") (19, "ナシ") (17, "モモ") (23, "マンゴー") (28, "ブドウ") 再帰呼び出し (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) 12 (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) this.printTreeRecursive((23, "モモ"), this.printTreeRecursive((17, “モモ”), "マンゴー"), “マンゴー”), 4); 4);出力 左部分木探索中 右部分木探索中 4); 4);出力 左部分木探索中 右部分木探索中 this.printTreeRecursive((31, this.printTreeRecursive((28, this.printTreeRecursive((19, this.printTreeRecursive(( this.printTreeRecursive((21, 7, "ナシ"), "スイカ"), "グレープフルーツ"), “グレープフルーツ”), “スイカ”), “ナシ”), "ブドウ"), “ブドウ”), "レモン"), “レモン”), 3); 3);出力 3); 3);出力 3); 3);出力 3); 3);出力 左部分木探索中 右部分木探索中 左部分木探索中 右部分木探索中 左部分木探索中 右部分木探索中 左部分木探索中 右部分木探索中 3); 3);出力 左部分木探索中 右部分木探索中 this.printTreeRecursive((48, "サクランボ"), this.printTreeRecursive((30, this.printTreeRecursive((24, this.printTreeRecursive((14, “サクランボ”), "イチゴ"), "ブルーベリー"), "メロン"), “メロン”), 2); “イチゴ”), “ブルーベリー”), 2);出力 2); 2);出力 左部分木探索中 右部分木探索中 左部分木探索中 右部分木探索中 2); 2);出力 2); 2);出力 左部分木探索中 右部分木探索中 左部分木探索中 右部分木探索中 this.printTreeRecursive((32, "ミカン"), this.printTreeRecursive((20, "バナナ"), “バナナ”),1); “ミカン”), 1);左部分木探索中 出力 右部分木探索中 出力 左部分木探索中 右部分木探索中 this.printTreeRecursive((29, "リンゴ"), “リンゴ”), 0); 0);出力 左部分木探索中 右部分木探索中 13 再帰呼び出しの除去 再帰呼び出しでは同じ関数を呼ぶ 一時変数は、名前が同じだけで、実体は別 実体は関数エントリ時に確保される 関数から抜けるときに開放される 最も最後に呼ばれた関数が最初に抜ける つまりLIFO、スタック 一時変数や途中経過を退避する領域が あればループにより実現できる 14 退避すべきデータ • • 部分木の根 今何をしているか？ – 再帰呼び出しでは、プログラムの流れとして 保持していた。つまりCPUのプログラムカウンタ 1. 2. 3. 4. • 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る ループに変換するにはこれをスタックに退避 • 探索中の頂点の深さは計算できるので退避不要 15 public void printTreeLoop() { MyNode node, currentRootNode = this.root; int depth = 0, todo = 0; Stack stack = new Stack(); while(true){ switch(todo++){ case 0: node = currentRootNode.getRight(); if(node != null){ ループ版 stack.push(currentRootNode); currentRootNode = node; 木の根が左にある、 stack.push(new Integer(todo)); todo = 0; 左から右へ生えている depth++; 木を表示するプログラム } break; case 1: for(int i=0; i < depth; i++){ System.out.print("\t"); } System.out.println(currentRootNode.getData().toString()); break; // 続く… 16 } } } case 2: node = currentRootNode.getLeft(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 3: if(stack.empty()){ return; } todo = ((Integer)stack.pop()).intValue(); currentRootNode = (MyNode)stack.pop(); depth--; 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 1. 右部分木の訪問 2. 自分の値の表示 3. 左部分木の訪問 4. 親の頂点に戻る 17 JDK5での拡張forループ • 配列・リスト・Setといった集合を楽に扱うための拡張 • http://java.sun.com/j2se/1.5.0/ja/docs/ja/guide/language/index.html for(要素型名 要素型変数: 集合型変数){ for文本体; } ListやSetや配列を表す変数 public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); System.out.print(sb.toString()); } 総称型については、次回にでも… 18
© Copyright 2024 ExpyDoc
