| −→ |
今回は、ハノイの塔を取り上げます。ハノイの塔は、A の棒に積んである大きさの違う何枚かの円盤を棒 C に移動するパズルです。 比較的有名なパズルですので、皆さんもご存知のことと思います。ルールは、次の２つだけです。
| −→ |
ハノイの塔は、再帰呼び出しの好例としてよく取り上げられます。 インターネット上でも、C や JavaScript のプログラム例を見ることができます。次は、Perl での再帰呼び出しプログラムです。棒の名前は A, B, C に、円盤の名前は小さい順から a, b, c, ... のように付けています。円盤の数は $n に指定することができ、最大で 20 枚です。
再帰版プログラム
use strict;
my $n = 4;
my $no_width = length 2 ** $n;
my @pole = ('A', 'B', 'C');
my @ring = ('a' .. 't')[0 .. $n - 1];
my @board = (join('', @ring), '', '');
my $cnt = 0;
printf "%${no_width}s %${n}s %${n}s %${n}s\n%s\n", '', 'A', 'B', 'C', '-' x ($no_width + $n * 3 + 20);
printf "%${no_width}d: %${n}s %${n}s %${n}s\n", $cnt++, map { $_ ? $_ : '-'} @board;
hanoi($#ring, 0, 1, 2);
sub hanoi {
my ($ring_no, $from, $other, $dest) = @_;
hanoi($ring_no - 1, $from, $dest, $other) if $ring_no;
substr $board[$dest], 0, 0, substr($board[$from], 0, 1, '');
printf "%${no_width}d: %${n}s %${n}s %${n}s ", $cnt++, map { $_ ? $_ : '-'} @board;
print "($ring[$ring_no]: $pole[$from] --> $pole[$dest])\n";
hanoi($ring_no - 1, $other, $from, $dest) if $ring_no;
}上のプログラムを実行すると、コンソールには下記のような表示がされます。 １番左に手数を、その次に各棒における円盤の状態を示しています。末尾には丸括弧に囲んで、 直前の行から移動した円盤とその移動元と移動先を示しています。
A B C
----------------------------------
0: abcd - -
1: bcd a - (a: A --> B)
2: cd a b (b: A --> C)
3: cd - ab (a: B --> C)
4: d c ab (c: A --> B)
5: ad c b (a: C --> A)
6: ad bc - (b: C --> B)
7: d abc - (a: A --> B)
8: - abc d (d: A --> C)
9: - bc ad (a: B --> C)
10: b c ad (b: B --> A)
11: ab c d (a: C --> A)
12: ab - cd (c: B --> C)
13: b a cd (a: A --> B)
14: - a bcd (b: A --> C)
15: - - abcd (a: B --> C)
プログラムの理解には、再帰呼び出しの知識が必要です。 サブルーチンの中から自分自身を呼び出す再帰呼び出しは、最初のうちは理解が難しいものです。 特に今回のプログラムでは、サブルーチン内で２回呼び出しているので余計にわかりずらくなっています。 ハノイの塔とともに再帰呼び出しの例とされる階乗は、解法アルゴリズムとして再帰呼び出しは最善ではありませんが、 再帰呼び出しを説明するには最適です。次は、簡単な階乗のプログラムと実行の様子です。
print fact(4), "\n";
sub fact { $_[0] > 1 ? $_[0] * fact($_[0] - 1) : 1; }
fact(4)
4 * fact(3)-->fact(3)
<--3 * fact(2)-->fact(2)
<--2 * fact(1)-->fact(1)
<--1
fact(n) で呼び出されたサブルーチンは、n が１よりも大きい場合は n x (n - 1)! に相当する n * fact(n-1) の式の中で引数を１減らして自分自身を呼び出します。 呼び出されたサブルーチンも引数を同様に評価し、実行の様子の --> が示すように次々に自分自身を呼び出します。 そして、再帰呼び出しの停止条件である引数が１になった時点で、連鎖呼び出しは停止します。１を受け取った fact(1) は、呼び出し元に１をそのまま返します。受け取った fact(2) は、2 * 1 (2! の階乗) を計算して呼び出し元の fact(3) に返します。実行の様子の <-- が示すように、計算した結果を次々に呼び出し元に返していって最終的に fact(n) で n の階乗の計算結果が得られることになります。
どうでしょうか、階乗の例は理解できたでしょうか。再帰呼び出しを書くポイントは、 少し異なる自分自身を呼び出すことと停止条件を設けておくという、２つの点です。本題のハノイの塔では、 円盤の移動を挟んで２つの再帰呼び出しが使われています。２つの呼び出しでは、引数の渡し方が違っていています。 なお、どちらの呼び出しでも、最小の円盤 a が停止条件になります。
最初の呼び出し hanoi($#ring, 0, 1, 2);
プログラムでは円盤を配列 @ring (円盤４個の場合: a, b, c, d) に、各棒は配列 @pole (A, B, C)
に、各棒の円盤の状態は @board (円盤４個の場合: 'abcd', '', '') 入れてあります。
サブルーチンを起動する最初の呼び出しの引数 ($#ring, 0, 1, 2)
は、呼び出されたサブルーチンでは my ($ring_no, $from, $other, $dest) = @_; で受け取ります。
引数はすべて数値化されていますが、下の図の場合は１番大きな円盤 d を棒 A から棒 C
に移動せよ、という意味になります。
円盤移動前の呼び出し haoni($ring_no - 1, $from, $dest, $other)
if $ring_no;
サブルーチンが呼び出されたときに $ring_no が１(円盤 b) 以上の場合は、$ring_no
の円盤の上に $ring_no - 1 から 0 までの円盤が積まれています。$ring_no の円盤を $from から $dest
に移動するには、上に積んである円盤を $other に移動しておく必要があるため、$ring_no を１減らし、$dest
と $other を入れ換えて再帰呼び出しします。この呼び出しは、$dest と $other を入れ換えながら $ring_no が
0 になるまで続きます。$ring_no が 0 になると連鎖呼び出しは停止し、a の円盤を移動できるようになります。a
より大きな円盤は、サブルーチンから戻ってきたときに移動されます。
円盤移動後の呼び出し haoni($ring_no - 1, $other, $from,
$dest) if $ring_no;
$ring_no が１(円盤 b) 以上の円盤を移動した場合は、$ring_no - 1 から 0
までの円盤は移動元と移動先以外の $other の棒に積まれています。下の図は、円盤 c を A から B
に移動したところです。次に行わなければならないのは、C に積まれている円盤 a, b を今移動したばかりの円盤
c の上に積むことです。円盤移動後の再帰呼び出しでは、$ring_no を１減らし、$from と $other
を入れ換えた引数を渡します。
ハノイの塔の解法には、もちろん再帰を使わない方法もあります。 これから紹介する方法は、円盤追加型というべき方法です。実は、円盤 N 個の手順から円盤 N + 1 個の手順を生成することができるのです。例として、円盤３個の手順から円盤４個の手順を生成してみましょう。 円盤３個の手順は、次のようになります。
円盤３個の手順:
A B C
------------------
0: abc - -
1: bc - a
2: c b a
3: c ab -
4: - ab c
5: a b c
6: a - bc
7: - - abc
円盤 3 個の手順から円盤 4 個の手順の生成は、前半と後半に分けて行います。 まずは前半の手順を生成しますが、これは簡単です。円盤 3 個の手順のすべてに、単に棒 A の末尾に d の円盤を追加するだけですみます。ここで 7 手目を見てみると、棒 C に a, b, c が移動していて、棒 A の円盤 d を棒 B に移動できることがわかります。残る後半の手順は、まず円盤 d を棒 B に移動して、次に棒 C にある円盤 a, b, c を棒 B に移動することです。
円盤４個の前半手順: 後半手順を追加(全手順):
A B C A B C
------------------- -----------------------
0: abcd - - 0: abcd - -
1: bcd - a 1: bcd - a
2: cd b a 2: cd b a
3: cd ab - 3: cd ab -
4: d ab c 4: d ab c
5: ad b c 5: ad b c
6: ad - bc 6: ad - bc
7: d - abc 7: d - abc
8: - d abc
9: - ad bc
10: b ad c
11: ab d c
12: ab cd -
13: b cd a
14: - bcd a
15: - abcd -
後半手順の生成は、生成済みの前半の手順を利用することができます。 前半の手順をそのまま逆順に実行すると、当然ですが元に戻ってしまいます。それでは困るので、棒 A と棒 B の配置を入れ換えて逆順に実行します。そうすると、棒 B に円盤 a, b, c, d を移動することができ、 これを前半手順の後に追加すると、上の表の右側のように円盤 4 個の手順が生成できたことになります。
円盤追加型のプログラムでは、円盤１個の手順を与えると任意の N 個の手順を生成することができます。円盤１個の手順から円盤 2 個の手順を、円盤 2 個の手順から円盤 3 個の手順を、というように次々に生成できるからです。また、ハノイの塔では棒 A から棒 B に移動するのも棒 C に移動するのもプログラム的には同じなのですが、すべての任意の N 個で棒 C に移動するには、N が奇数の場合は１枚目を棒 C に、N が偶数の場合は１枚目を棒 B に移動することでできます。
次が、非再帰版のハノイの塔のプログラムです。非再帰版のプログラムの出力も、 再帰版のプログラムに合わせて同じになるようにしています。
非再帰版プログラム
use strict;
my $n = 4;
my @hanoi = (['a', '', ''], ['', $n % 2 ? ('', 'a') : ('a', '')]);
foreach my $char (('b' .. 't')[0 .. $n - 2]) {
$_->[0] =~ s/$/$char/ foreach @hanoi;
my @idx = $hanoi[-1]->[1] ? (2, 1, 0) : (1, 0, 2);
push @hanoi, map { [@$_[@idx]] } reverse @hanoi;
}
my $no_width = length $#hanoi; my @pole = ('A', 'B', 'C');
printf "%${no_width}s %${n}s %${n}s %${n}s\n%s\n", '', 'A', 'B', 'C', '-' x ($no_width + $n * 3 + 20);
printf "%${no_width}d: %${n}s %${n}s %${n}s\n", 0, map { $_ ? $_ : '-' } @{$hanoi[0]};
foreach my $idx (1 .. $#hanoi) {
my $from = length($hanoi[$idx]->[0]) < length($hanoi[$idx - 1]->[0]) ? 0 :
length($hanoi[$idx]->[1]) < length($hanoi[$idx - 1]->[1]) ? 1 : 2;
my $dest = length($hanoi[$idx]->[0]) > length($hanoi[$idx - 1]->[0]) ? 0 :
length($hanoi[$idx]->[1]) > length($hanoi[$idx - 1]->[1]) ? 1 : 2;
printf "%${no_width}d: %${n}s %${n}s %${n}s ", $idx, map { $_ ? $_ : '-' } @{$hanoi[$idx]};
print "(", substr($hanoi[$idx]->[$dest], 0, 1), ": $pole[$from] --> $pole[$dest])\n";
}(2010/07/01)