アルゴリズムとデータ構造
2012
年6
月28
日酒居敬一
([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html
1
基準値を決定
10 8 3 15 5 32 12 1 6 24
10
8 3 5 1 6
＜10
＜15 32 12 24
整列済み
基準値を決定 基準値を決定
5
＜15
3 1
＜8 6 10 12
＜ ＜32 24
基準値を決定 基準値を決定 基準値を決定 基準値を決定
5
＜15
3
1
＜6 8 10 12 24
＜32
10
1 3 5 6 8 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兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 79
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());
}
4
32 24 15 12 10 8 6 5 3 1
＜
32
10
1 3 5 6 8 12 15 24 32
クイック ソート
（最悪の 場合）
5
24 15 12 10 8 6 3 1
5
12 10 8 6 3 1
5
15 12 10 8 6 3 1
1
5
10 8 6 3 1
5
8 6 3 1
5
6 3 1
5 3 1 3 1
＜
3 5 6 8 10 12 15 24 32
＜
6 8 10 12 15 24 32
＜
10 12 15 24 32
＜
12 15 24 32
＜
5 6 8 10 12 15 24 32
＜
8 10 12 15 24 32
＜
24 32
＜
15 24 32
5
再帰的アルゴリズム
•
再帰は重要なアルゴリズムの概念である．•
とくに参照型を用いた柔軟なデータ構造を 扱う場合には，基本的に再帰的アルゴリ ズムを用いるしかない．•
ここでは，再帰的アルゴリズムを詳細に検 討し，その動作の理解をする6
漸化式からの計算
•
階乗•
フィボナッチ数列•
いずれも再帰的に関数を呼ぶ形に書ける 再帰呼び出しの場合f(0)
やf(1)
といった数列の最初の値のところで停止
) 1 (
! )
( ,
1 )
0
( = f x = x = x × f x − f
) 1 (
) 2 (
) ( ,
1 )
1 ( ,
1 )
0
( = f = f x = f x − + f x −
f
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;
}
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
つ追加すれば 足るフィボナッチ数を求めるプログラム
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(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]$
10二分木を次のルールで走査
1.
自分の左部分木をたどる2.
自分を訪ねる3.
自分の右部分木をたどる4.
親の頂点に戻る二分探索木を走査すると 横倒しの木を表示できる
通りがけ順の走査
29
21 31 19
7
48 30
24 14
32 20
29
20 32
48 30
24 14
7 19 21 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);
}
(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, "
ブドウ")
再帰呼び出し
12
this.printTreeRecursive((29, "
リンゴ"), 0);
右部分木探索中this.printTreeRecursive((32, "
バナナ"), 1);
右部分木探索中this.printTreeRecursive((20, "
ミカン"), 1);
右部分木探索中this.printTreeRecursive((14, "
サクランボ"), 2);
右部分木探索中this.printTreeRecursive((30, "
イチゴ"), 2);
右部分木探索中this.printTreeRecursive((24, "
ブルーベリー"), 2);
右部分木探索中this.printTreeRecursive((48, "
メロン"), 2);
右部分木探索中this.printTreeRecursive(( 7, " this.printTreeRecursive((21, "
グレープフルーツレモン"), 3);
右部分木探索中"), 3);
右部分木探索中this.printTreeRecursive((31, "
スイカ"), 3);
右部分木探索中this.printTreeRecursive((19, "
ナシ"), 3);
右部分木探索中this.printTreeRecursive((28, "
ブドウ"), 3);
右部分木探索中this.printTreeRecursive((17, "
モモ"), 4);
右部分木探索中this.printTreeRecursive((23, "
マンゴー"), 4);
右部分木探索中this.printTreeRecursive((29, "
リンゴ"), 0);
出力this.printTreeRecursive((32, “バナナ” ), 1);
出力this.printTreeRecursive((14, "
サクランボ"), 2);
出力this.printTreeRecursive((30, "
イチゴ"), 2);
出力this.printTreeRecursive((24, "
ブルーベリー"), 2);
出力this.printTreeRecursive((48, "
メロン"), 2);
出力this.printTreeRecursive(( 7, " this.printTreeRecursive((21, "
グレープフルーツレモン"), 3);
出力"), 3);
出力this.printTreeRecursive((31, "
スイカ"), 3);
出力this.printTreeRecursive((19, "
ナシ"), 3);
出力this.printTreeRecursive((28, "
ブドウ"), 3);
出力this.printTreeRecursive((17, "
モモ"), 4);
出力this.printTreeRecursive((23, "
マンゴー"), 4);
出力this.printTreeRecursive((48, “
メロン”), 2);
左部分木探索中this.printTreeRecursive((32, “バナナ” ), 1);
左部分木探索中this.printTreeRecursive((31, “
スイカ”), 3);
左部分木探索中this.printTreeRecursive((30, “
イチゴ”), 2);
左部分木探索中this.printTreeRecursive((29, “
リンゴ”), 0);
左部分木探索中this.printTreeRecursive((28, “
ブドウ”), 3);
左部分木探索中this.printTreeRecursive((24, “
ブルーベリー”), 2);
左部分木探索中this.printTreeRecursive((23, “
マンゴー”), 4);
左部分木探索中this.printTreeRecursive((21, “
レモン”), 3);
左部分木探索中(48'
メロン) (32'
バナナ)
(31'
スイカ) (30'
イチゴ)
(29'
リンゴ)
(28'
ブドウ) (24'
ブルーベリー)
(23'
マンゴー) (21'
レモン)
(20'
ミカン)
(19'
ナシ)
(17'
モモ) (14'
サクランボ)
(7'
グレープフルーツ)
this.printTreeRecursive((20, “ミカン” ), 1);
出力this.printTreeRecursive((20, “ミカン” ), 1);
左部分木探索中this.printTreeRecursive((19, “
ナシ”), 3);
左部分木探索中this.printTreeRecursive((17, “
モモ”), 4);
左部分木探索中this.printTreeRecursive((14, “
サクランボ”), 2);
左部分木探索中this.printTreeRecursive(( 7, “
グレープフルーツ”), 3);
左部分木探索中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.
親の頂点に戻る 17JDK5
での拡張for
ループ•
配列・リスト・Set
といった集合を楽に扱うための拡張• http://java.sun.com/j2se/1.5.0/ja/docs/ja/guide/language/index.html
18
