酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年7月1日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html.

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造 2011年7月7日
Advertisements

基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
アルゴリズムとデータ構造 2012年6月14日
情報処理Ⅱ 2005年12月9日(金).
アルゴリズムとデータ構造 2011年6月13日
アルゴリズムとデータ構造 2012年7月5日
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
二分探索木によるサーチ.
アルゴリズムとデータ構造 2011年6月30日
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
Cプログラミング演習 中間まとめ2.
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
オブジェクト指向 プログラミング 第十三回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
二分木のメソッド(続き).
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
大岩 元 慶応大学環境情報学部 再帰 データ構造とプログラミング(8) 大岩 元 慶応大学環境情報学部
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
離散数学 07. 木 五島.
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2005年7月5日
復習+α JBuilderの使い方を思い出す。 配列とGUI 再帰とマージソート 木と二分木の探索
プログラミング 4 整列アルゴリズム.
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
オブジェクト指向プログラミングと開発環境
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
プログラミング演習Ⅲ- Sorting Quick Sort and Merge Sort
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
アルゴリズムとプログラミング (Algorithms and Programming)
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
アルゴリズムとデータ構造1 2006年6月23日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2013年6月20日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造1 2005年7月12日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
情報処理Ⅱ 小テスト 2005年2月1日(火).
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年7月1日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html

クイックソート 基準値を決定 10 1 8 3 15 5 32 12 6 24 基準値を決定 10 8 3 5 1 6 15 32 12 24 < 10 整列済み 基準値を決定 5 15 < 3 1 8 6 12 32 24 10 5 15 < 3 1 8 6 12 32 24 10 10 1 8 3 15 5 32 12 6 24

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

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27 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) { System.out.print(sb.toString()); 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 79

クイック ソート (最悪の 場合) 32 24 15 12 10 8 6 5 3 1 5 24 15 12 10 8 6 3 1 < 32 5 15 12 10 8 6 3 1 < 32 24 5 12 10 8 6 3 1 < 15 32 24 5 10 8 6 3 1 < 15 12 32 24 5 8 6 3 1 < 10 15 32 12 24 5 6 3 1 < 10 8 15 32 12 24 5 3 1 < 10 8 15 32 12 6 24 3 1 < 10 8 15 5 32 12 6 24 1 < 10 8 3 15 5 32 12 6 24 10 1 8 3 15 5 32 12 6 24

再帰的アルゴリズム 再帰は重要なアルゴリズムの概念である. とくに参照型を用いた柔軟なデータ構造を扱う場合には,基本的に再帰的アルゴリズムを用いるしかない. ここでは,再帰的アルゴリズムを詳細に検討し,その動作の理解をする

漸化式からの計算 階乗 フィボナッチ数列 いずれも再帰的に関数を呼ぶ形に書ける 再帰呼び出しの場合 f(0)やf(1)といった      数列の最初の値のところで停止

末尾再帰なので再帰呼び出しをループに変換することは容易 階乗を求めるプログラム 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) { int total = aTarget; for(int count = aTarget - 1; 0 < count; count--){ total *= count; 末尾再帰なので再帰呼び出しをループに変換することは容易

f(0)から順にたどれば結果を求めることができる フィボナッチ数を求めるプログラム 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) { int old1 = 1, old2 = 1, total = 0; for(int count = 2; count <= aTarget; count++){ total = old1 + old2; old2 = old1; old1 = total; f(0)から順にたどれば結果を求めることができる f(x)に必要とされるのはf(x-1)とf(x-2)なので変数を2つ追加すれば足る

[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(2) から出ます: 2 fibonatti(3) から出ます: 3 fibonatti(4) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) に入ります fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(3) から出ます: 3 fibonatti(4) から出ます: 5 fibonatti(5) から出ます: 8 [sakai@star 13]$

通りがけ順の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 親の頂点に戻る 二分探索木を走査すると 横倒しの木を表示できる 29 29 20 20 32 32 14 14 24 24 30 30 48 48 7 7 19 19 21 21 31 31

木の根が左にある、 左から右へ生えている木を表示するプログラム 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'グレープフルーツ)

this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 this.printTreeRecursive((23, “マンゴー”), 4); 左部分木探索中 this.printTreeRecursive((23, "マンゴー"), 4);出力 this.printTreeRecursive((23, "マンゴー"), 4); 右部分木探索中 this.printTreeRecursive((17, “モモ”), 4); 左部分木探索中 this.printTreeRecursive((17, "モモ"), 4);出力 this.printTreeRecursive((31, “スイカ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3);出力 this.printTreeRecursive((19, "ナシ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3); 右部分木探索中 this.printTreeRecursive((19, “ナシ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3); 右部分木探索中 this.printTreeRecursive((28, “ブドウ”), 3); 左部分木探索中 this.printTreeRecursive((19, "ナシ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, "グレープフルーツ"), 3);出力 this.printTreeRecursive(( 7, "グレープフルーツ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, “グレープフルーツ”), 3); 左部分木探索中 this.printTreeRecursive((21, “レモン”), 3); 左部分木探索中 this.printTreeRecursive((21, "レモン"), 3);出力 this.printTreeRecursive((21, "レモン"), 3); 右部分木探索中 this.printTreeRecursive((24, “ブルーベリー”), 2); 左部分木探索中 this.printTreeRecursive((48, "メロン"), 2); 右部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2); 右部分木探索中 this.printTreeRecursive((14, "サクランボ"), 2); 右部分木探索中 this.printTreeRecursive((30, "イチゴ"), 2); 右部分木探索中 this.printTreeRecursive((14, “サクランボ”), 2); 左部分木探索中 this.printTreeRecursive((30, “イチゴ”), 2); 左部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2);出力 this.printTreeRecursive((48, "メロン"), 2);出力 this.printTreeRecursive((30, "イチゴ"), 2);出力 this.printTreeRecursive((14, "サクランボ"), 2);出力 this.printTreeRecursive((48, “メロン”), 2); 左部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 左部分木探索中 this.printTreeRecursive((20, "ミカン"), 1); 右部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 出力 this.printTreeRecursive((32, “バナナ”), 1); 左部分木探索中 this.printTreeRecursive((32, "バナナ"), 1); 右部分木探索中 this.printTreeRecursive((32, “バナナ”), 1); 出力 this.printTreeRecursive((29, “リンゴ”), 0); 左部分木探索中 this.printTreeRecursive((29, "リンゴ"), 0);出力 this.printTreeRecursive((29, "リンゴ"), 0); 右部分木探索中

再帰呼び出しの除去 再帰呼び出しでは同じ関数を呼ぶ 一時変数は、名前が同じだけで、実体は別 最も最後に呼ばれた関数が最初に抜ける 実体は関数エントリ時に確保される 関数から抜けるときに開放される 最も最後に呼ばれた関数が最初に抜ける つまりLIFO、スタック 一時変数や途中経過を退避する領域が あればループにより実現できる

退避すべきデータ 部分木の根 今何をしているか? ループに変換するにはこれをスタックに退避 再帰呼び出しでは、プログラムの流れとして 保持していた。つまりCPUのプログラムカウンタ 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る ループに変換するにはこれをスタックに退避 探索中の頂点の深さは計算できるので退避不要

木の根が左にある、 左から右へ生えている木を表示するプログラム 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()); // 続く… ループ版 木の根が左にある、 左から右へ生えている木を表示するプログラム

一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る 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--; 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る

JDK5での拡張forループ 配列・リスト・Setといった集合を楽に扱うための拡張 for(要素型名 要素型変数: 集合型変数){ 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()); 総称型については、次回にでも…