アルゴリズムとデータ構造
1
アルゴリズムとデータ構造
アルゴリズムとデータ構造
1
1
2005
2005
年
年
7
7
月
月
22
22
日
日
酒居敬一
酒居敬一
(
(
sakai.keiichi@kochi
sakai.keiichi@kochi
-
-
tech.ac.jp
tech.ac.jp
)
)
http://www.info.kochi
再帰的アルゴリズム
• 再帰は重要なアルゴリズムの概念である．
とくに参照型を用いた柔軟なデータ構造を
扱う場合には，基本的に再帰的アルゴリ
ズムを用いるしかない．ここでは，再帰的
アルゴリズムを詳細に検討し，その動作の
理解をする
漸化式からの計算
• 階乗
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; }
階乗を求めるプログラム
末尾再帰なので再帰
呼び出しをループに
変換することは容易
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(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) から出ます: 3 fibonatti(4) に入ります fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 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 [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; }
円盤オブジェクトと
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){ this.stack.push(aDisk); return true; } return false; }
private Stack stack; }
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 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);
this.printAll(); } else {
this.doHanoi(aDisks - 1, aFrom, anOther, aTo); Disk disk = this.tower[aFrom].get();
this.tower[aTo].put(disk); this.printAll();
this.doHanoi(aDisks - 1, anOther, aTo, aFrom); }
} public class Hanoi
{
private Tower[] tower = new Tower[] {
new Tower(), new Tower(), new Tower() };
private int disks; }
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("-"); } System.out.print("¥t"); }else{ System.out.print("¥t|¥t"); } } System.out.println(""); } System.out.println("---"); System.out.println(""); }
通りがけ順の走査
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分を訪ねる
3. 自分の右部分木をたどる
4. 親の頂点に戻る
二分探索木を走査すると
横倒しの木を表示できる
29
31
21
19
7
48
30
24
14
32
20
29
20
32
48
30
24
14
7
19
21
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); } (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ)
再帰呼び出し版
木の根が左にある、
左から右へ生えている
木を表示するプログラム
(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); 右部分木探索中
this.printTreeRecursive((23, "マンゴー"), 4); 右部分木探索中
this.printTreeRecursive((17, "モモ"), 4);出力
this.printTreeRecursive((23, "マンゴー"), 4);出力
this.printTreeRecursive((23, “マンゴー”), 4); 左部分木探索中
this.printTreeRecursive((17, “モモ”), 4); 左部分木探索中
this.printTreeRecursive(( 7, "グレープフルーツ"), 3); 右部分木探索中
this.printTreeRecursive((21, "レモン"), 3); 右部分木探索中
this.printTreeRecursive((31, "スイカ"), 3); 右部分木探索中
this.printTreeRecursive((19, "ナシ"), 3); 右部分木探索中
this.printTreeRecursive((28, "ブドウ"), 3); 右部分木探索中
this.printTreeRecursive(( 7, "グレープフルーツ"), 3);出力
this.printTreeRecursive((21, "レモン"), 3);出力
this.printTreeRecursive((31, "スイカ"), 3);出力
this.printTreeRecursive((19, "ナシ"), 3);出力
this.printTreeRecursive((28, "ブドウ"), 3);出力
this.printTreeRecursive((31, “スイカ”), 3); 左部分木探索中
this.printTreeRecursive((28, “ブドウ”), 3); 左部分木探索中
this.printTreeRecursive((21, “レモン”), 3); 左部分木探索中
this.printTreeRecursive((19, “ナシ”), 3); 左部分木探索中
this.printTreeRecursive(( 7, “グレープフルーツ”), 3); 左部分木探索中
this.printTreeRecursive((14, "サクランボ"), 2); 右部分木探索中
this.printTreeRecursive((30, "イチゴ"), 2); 右部分木探索中
this.printTreeRecursive((24, "ブルーベリー"), 2); 右部分木探索中
this.printTreeRecursive((48, "メロン"), 2); 右部分木探索中
this.printTreeRecursive((14, "サクランボ"), 2);出力
this.printTreeRecursive((30, "イチゴ"), 2);出力
this.printTreeRecursive((24, "ブルーベリー"), 2);出力
this.printTreeRecursive((48, "メロン"), 2);出力
this.printTreeRecursive((48, “メロン”), 2); 左部分木探索中
this.printTreeRecursive((30, “イチゴ”), 2); 左部分木探索中
this.printTreeRecursive((24, “ブルーベリー”), 2); 左部分木探索中
this.printTreeRecursive((14, “サクランボ”), 2); 左部分木探索中
this.printTreeRecursive((32, "バナナ"), 1); 右部分木探索中
this.printTreeRecursive((20, "ミカン"), 1); 右部分木探索中
this.printTreeRecursive((32, “バナナ”), 1); 出力
this.printTreeRecursive((32, “バナナ”), 1); 左部分木探索中
this.printTreeRecursive((20, “ミカン”), 1); 出力
this.printTreeRecursive((20, “ミカン”), 1); 左部分木探索中
this.printTreeRecursive((29, "リンゴ"), 0); 右部分木探索中
this.printTreeRecursive((29, "リンゴ"), 0);出力
this.printTreeRecursive((29, “リンゴ”), 0); 左部分木探索中
再帰呼び出しの除去
¾再帰呼び出しでは同じ関数を呼ぶ
¾一時変数は、名前が同じだけで、実体は別
¾実体は関数エントリ時に確保される
¾関数から抜けるときに開放される
¾最も最後に呼ばれた関数が最初に抜ける
¾つまり
LIFO、スタック
¾一時変数や途中経過を退避する領域が
あればループにより実現できる
退避すべきデータ
•
部分木の根
•
今何をしているか？
–
再帰呼び出しでは、プログラムの流れとして
保持していた。つまり
CPUのプログラムカウンタ
1. 右部分木の訪問
2. 自分の値の表示
3. 左部分木の訪問
4. 親の頂点に戻る
•
ループに変換するにはこれをスタックに退避
•
探索中の頂点の深さは計算できるので退避不要
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; // 続く…
ループ版
木の根が左にある、
左から右へ生えている
木を表示するプログラム
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--; } } }
