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

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造 2012年6月27日
Advertisements

アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング論 I 関数の再帰呼び出し
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
アルゴリズムとデータ構造 2011年6月13日
アルゴリズムとデータ構造1 2009年6月25日
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
二分探索木によるサーチ.
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
第9章 例外処理,パッケージ 9.1 例外処理 9.2 ガーベッジコレクション.
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング2 関数の再帰呼び出し
アルゴリズムとデータ構造勉強会 第6回 スレッド木
アルゴリズムとデータ構造 2010年6月28日
アルゴリズムとデータ構造1 2005年6月28日
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
アルゴリズムとデータ構造 2012年7月17日
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
離散数学 07. 木 五島.
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
復習+α JBuilderの使い方を思い出す。 配列とGUI 再帰とマージソート 木と二分木の探索
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
オブジェクト指向プログラミングと開発環境
再帰的手続き.
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
AVL木.
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2013年6月20日
アルゴリズムとデータ構造 2012年6月21日
プログラミング2 関数の再帰呼び出し
プログラミング演習I 2003年6月11日(第9回) 木村巌.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

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

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

通りがけ順の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 親の頂点に戻る 二分探索木を走査すると 横倒しの木を表示できる 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); 右部分木探索中

漸化式からの計算 階乗 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)で停止

末尾再帰なので再帰呼び出しをループに変換することは容易 public class Factorial { public static int factorial(int aTarget) { if(0 > aTarget) throw new IllegalArgumentException(); 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) throw new IllegalArgumentException(); if(0 == aTarget){ return 1; } int total = aTarget; for(int count = aTarget - 1; 0 < count; count--){ total *= count; return total; 末尾再帰なので再帰呼び出しをループに変換することは容易

f(0)から順にたどれば結果を求めることができる public class Fibonatti { public static int fibonatti(int aTarget) { if(0 > aTarget) throw new IllegalArgumentException(); 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) throw new IllegalArgumentException(); if((0 == aTarget) || (1 == aTarget)){ return 1; } int old1 = 1, old2 = 1, total = 0; for(int count = 2; count <= aTarget; count++){ total = old1 + old2; old2 = old1; old1 = total; return 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]$

再帰的アルゴリズム ハノイの塔 一回に一枚の円盤しか動かしてはいけない。 移動の途中で円盤の大小を逆に積んではいけない。 常に大きい方の円盤が下になるようにする。 棒以外のところに円盤を置いてはいけない。

円盤オブジェクトと 指定の大きさの円盤を生成するメソッド public class Disk { public Disk(int aSize) { if(1 > aSize){ throw new IllegalArgumentException(); } this.size = aSize; public int size() { return this.size; private int size = 0; 円盤オブジェクトと 指定の大きさの円盤を生成するメソッド

塔オブジェクトと スタックを用いて円盤操作を実現する import java.util.Stack; public class Tower { public Tower() { this.stack = new Stack(); } public Disk get() { return (Disk)this.stack.pop(); public Disk get(int anIndex) { return (Disk)this.stack.get(anIndex); public int size() { return this.stack.size(); } public boolean put(Disk aDisk) { if(this.stack.isEmpty()){ this.stack.push(aDisk); return true; int topSize = ((Disk)this.stack.peek()).size(); if(aDisk.size() < topSize){ return false; private Stack stack; 塔オブジェクトと スタックを用いて円盤操作を実現する

再帰呼び出し public class Hanoi { private Tower[] tower = new Tower[] { }; private int disks; } public Hanoi(int aDisks) { this.disks = aDisks; for(int count = aDisks; 0 < count; count--){ this.tower[0].put(new Disk(count)); } this.printAll(); public void doHanoi() { this.doHanoi(this.disks, 0, 1, 2); private void doHanoi (int aDisks, int aFrom, int aTo, int anOther) { if(1 == aDisks){ Disk disk = this.tower[aFrom].get(); this.tower[aTo].put(disk); } else { this.doHanoi(aDisks - 1, aFrom, anOther, aTo); this.doHanoi(aDisks - 1, anOther, aTo, aFrom); 再帰呼び出し

private void printAll() { int[] towerSizes = { tower[0].size(), tower[1].size(), tower[2].size() }; int towerSizeTotal = (towerSizes[0] + towerSizes[1] + towerSizes[2]); int[] sizes = {towerSizes[0], towerSizes[1], towerSizes[2]}; for(int count = 0; count < towerSizeTotal; count++){ for(int tcount = 0; tcount < 3; tcount++){ if((towerSizeTotal - towerSizes[tcount]) <= count){ Disk disk = this.tower[tcount].get(--sizes[tcount]); System.out.print("\t"); for(int disks = 0; disks < disk.size();disks++){ System.out.print("-"); } }else{ System.out.print("\t|\t"); System.out.println(""); System.out.println("-------------------------------------------------");

再帰呼び出しの除去 再帰呼び出しでは同じ関数を呼ぶ 一時変数は、名前が同じだけで、実体は別 最も最後に呼ばれた関数が最初に抜ける 実体は関数エントリ時に確保される 関数から抜けるときに開放される 最も最後に呼ばれた関数が最初に抜ける つまり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--; 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る