アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2005年7月22日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html
再帰的アルゴリズム
• 再帰は重要なアルゴリズムの概念である．
とくに参照型を用いた柔軟なデータ構造を
扱う場合には，基本的に再帰的アルゴリ
ズムを用いるしかない．ここでは，再帰的
アルゴリズムを詳細に検討し，その動作の
理解をする
漸化式からの計算
• 階乗
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)){
f(0)から順にたどれば
return 1;
結果を求めることがで
}
int old1 = 1, old2 = 1, total = 0;
きる
for(int count = 2; count <= aTarget; count++){
total = old1 + old2;
f(x)に必要とされるの
old2 = old1;
はf(x-1)とf(x-2)なので
old1 = total;
}
変数を2つ追加すれば
return total;
足る
}
[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
[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){
this.stack.push(aDisk);
return true;
}
return false;
}
private Stack stack;
public class Hanoi
{
private Tower[] tower =
new Tower[] {
new Tower(),
new 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);
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);
}
}
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
20
二分探索木を走査すると
横倒しの木を表示できる
14
7
24
19 21
32
30
48
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, "リンゴ")
(48'メロン)
(20, "ミカン")
(32'バナナ)
再帰呼び出し版
(14, "サクランボ")
(31'スイカ)
(32, "バナナ")
(30'イチゴ)
木の根が左にある、
(30, "イチゴ")
(29'リンゴ)
(24, "ブルーベリー")
(28'ブドウ)
左から右へ生えている
( 7, "グレープフルーツ")
(24'ブルーベリー)
木を表示するプログラム
(21, "レモン")
(23'マンゴー)
(48, "メロン")
(21'レモン)
(31, "スイカ")
(20'ミカン)
(19, "ナシ")
(19'ナシ)
(17, "モモ")
(17'モモ)
(23, "マンゴー")
(14'サクランボ)
(28, "ブドウ")
(7'グレープフルーツ)
(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);出力
左部分木探索中
右部分木探索中
再帰呼び出しの除去
再帰呼び出しでは同じ関数を呼ぶ
一時変数は、名前が同じだけで、実体は別
実体は関数エントリ時に確保される
関数から抜けるときに開放される
最も最後に呼ばれた関数が最初に抜ける
つまり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--;
一時退避場所にはスタックを使っている
次にすべきこと、部分木の根、を保持する
1. 右部分木の訪問
2. 自分の値の表示
3. 左部分木の訪問
4. 親の頂点に戻る

Download Report