JAPLA 2005/10/22 hanoiw0.txt (9/08)
ハノイ の 塔 の 初等解
繰り返しループ と 再帰法
中野嘉弘 82 西川利男 JAPLA会長 山下紀幸 80
FAX 専 011-588-3354 T・ F 047-163-0364 T・F 045-851- 3721
0. は し が き
先日('05.8.22)の山下 FAX は「ハノイの塔の APL 版のプログラムは西川著に
あるが、そのJ言語版を作りたい。 協力を乞う」を伝えて来た。 (文献1、2)
その1時間後、西川から、早くも反応があった。 Iverson か Hui の再帰プログラム
が、既に公開されていると云うものだ。 (文献3、−a,−b)
山下、中野は早速トライして見て、旨く動くものだと、感心、ひとしきり。
しかし、プログラムの論理の理解は今一つ。 山下は「小学生にも判るように改造を
したい」と希望を述べた。 (文献4) 西川から直に反応「判り難いのは、Tacit な
プログラム形式の為であろう。 Explicit 形式の例を!」の FAX があった(文献5)。
例は、元来は APLでの西川のもの(文献2)であるから再帰プログラムであること
には変わりはない。
山下、中野にとっては、その再帰性が何とも理解し難いのだ。
小学生ではなくて、大人いや、むしろJ言語のプロ級レベルの話は、末尾のほうで論議
したい。 普通の論文ならば、西川の再帰法から語るべきかも知れないが、それが難儀
なのだから、この順序となる事を御理解下さい。
「ハノイの塔 Hanoi's Tower」 いわゆる Chinese Puzzle と呼ばれる中の一つ。
場所(例えば柱)A に大きさの順に(刺し)重ねた nケ の円盤がある。
これを、別な柱 B に移動させたい。 移動は1ケづつ。 作業場所として第3の柱 C
を利用してよい。 ただし、各柱に刺さっている円盤の大きさの順番は替わっては不可である(つまり、大きな円盤が小さな円盤の上位には来ないように)。
最終的に、場所Bに、nケの円盤全部が、場所 A に於ける最初と同じ大きさの順に、
移っていれば良い。 円盤数 n が 、例として、 8 ならば、2^n -1 = 255 回の操作
で完了する(文献6)。 柱 B と C の役割を入れ換えて、B の方をを作業用として
解答する例も、同様に可能である。 本質的には同じ事だ。
より具体的には、後尾 5.節 辺りの説明を見よ。
1. 中野 の 論理
一松・竹之内先生の教育的名著「新数学事典」(文献6)に「パズル、ハノイの塔」の論理が解説されている。 西川 FAX とその解説を読んで、数日後、中野は下記の
如きプランを FAX した。 (文献7)
1)円盤 1ケ の場合
A: 0 1 操作は、柱 A から 円盤 1 を柱 B へ だから、最初は | A |
B: 0 0 は 単に円盤を刺す柱の台座とする。 移動後は | B |
と表示出来る。 これを 解1(A,B)と名付る。 one step だ。
2)円盤 2ケ の場合
A: 0 2 1 操作は A: 0 2 1 故、 解は | A A C |
B: 0 B: 0 2 1 | C B B |
C: 0 C: 0 1 で b軸へ 移動する
これを 解2(A,B) と名付ける。 three steps である。
これは、先ず、A 軸から C 軸へ、解1(A,C)を行い、円盤1を 柱 C に移す。
次ぎに、A 軸から B 軸に、解1(A,B)で、円盤2を柱 B に移す。
最後に、C 軸から B 軸に、解1(C,B)で、円盤1を柱 B の円盤2の上に移す。
この最初と最後の移動は、つまりは、往復移動的なものである。
3)円盤 3ケ の場合
A: 0 3 2 1 解は先ず、 円盤 2 と 1 を 柱 C に移す。 その解は、
B: 0 前例2)の解2(A,C)であるので B<−>C と交換して
C: 0 | A A B |
| B C C | である。
次ぎに、 残った円盤 3 を 柱 B に移す。 解1(A,B) である。
最後に、柱 C の円盤を、柱 B の 円盤 3 の上に移す。 解は 解2(C,B)
であるから、前例2)で A <−> C と交換して | C C A |
| A B B | である。
全体を纏めると | A A B A C C A |
| B C C B A B B | の seven steps となる。
4)円盤 4ケの場合
A: 0 4 3 2 1 解は先ず、柱 A の円盤 3 2 1 を 柱 C に移す。
B: 0 その解は、前の 3)節の 解3(A,C)である。
C: 0 次ぎに、柱 A 上の最大円盤 4 を 柱 B に移す。
最後に、柱 C上の円盤 3 2 1 を 柱 B に移す。
その方法は 解3(C,B) である。 纏めて
| A A C A B B A A C C B C A A C |
| C B B C A C C B B A A B C B B |
これが、 解4(A,B) であり、 step 数は 7+1+7=15 である。
5)円盤数が 5 の場合
解5(A,B)は 解4(A,C),解1(A,B),解4(C,B) の結合。
step数は 15 + 1 + 15 = 31 である。
6)それ以上は、同好の事を推進すればよい。
一般に ステップ数は 円盤の個数を n として ( 2^n − 1)である。
2. 中野流 ループ解 hand
小学生でも判るようにとなれば 、先ずは BASIC 的にならざるを得ない。
また、J言語の TACITなプログラミングは、80才以上のシニアには無理だ。
その範囲内で、J言語での、比較的簡潔な解答(handy hanoi) hand を作って見た。
hand =: 3 : 0
:
h=. h1=. 2 1 $ (0{.y.), 1{y.
k=. 2
label_2.
h=. (((1{y.),(2{y.)) chg h),"1 h1,1 ((0{y.),(2{y.)) chg h
k=. k+1
if. k > x. do. h return. end.
goto_2.
)
関数 chg は文字の入れ換え change をする。 前節1.で、解1(A, B)を
解1(A,C) や 解1(C, B) などと、引数を換える 事を行う。
下例の chg は、当面のもので、改良が期待される。 小学生にも判るように、との
条件が付けれれたので、初等教育的に、やむなく導入したものだ。
エレガントさ優先なら、そもそも、無くても良い。
chg =:
:
abc =. x =. x.
x0 =. 0{ x
x1 =. 1{ x
x2 =. ( -. abc e. (x0, x1)) # abc
y0 =. ,y.
n =. $ y0
n2 =. n % 2
i =. 0
z0 =. ' '
while. n > i do.
y0i =. i{ y0
if. y0i = x0 do. y0i =. x1
goto_0. end.
if. y0i = x1 do. yi1 =. y0i
y0i =. x0 end.
label_0.
z0 =. z0, y0i
i =. i+1
end.
z0 =. }. z0
z =. (2, n2) $ z0
)
NB. 関数 chg の上例は取りあえずのもので、改良が期待される。
例解 (デイスク枚数 1 は問題外に付き省く)
2 hand y =. 'ABC'
AAC
CBB
3 hand y
AABACCA
BCCBABB
4 hand y
AACABBAACCBCAAC
CBBCACCBBAABCBB
5 hand y
AABACCAABBCBAABACCACBBCCAABACCA
BCCBABBCCAACBCCBABBACAABBCCBABB
3. 中野流 再帰解 hr
西川 FAX の意見「ハノイの塔問題の本質は再帰プログラムだ。 ループ不要!」
(文献9、12)に従い、中野は再帰法でもトライして見た(文献10)。
例題によく出て來る Factorial や Fibonacci に比して、遥かに難しい問題である。
勿論、中野流の初等論理を用いた場合の話であって、もっとエレガントな論理では、
そうでは無いのかもしれぬ。
以下のプログラムは、確かにループは使っていない。 下の例解から見て、再帰法
であると云えよう。 「もっとエレガントな再帰法を」と云われれば、先人の真似に
近くなりそうだ。 後節 6.の末尾で再論する。
hr =: 3 : 0
hy < y.
)
hy =: 3 : 0
h1 =. 2 1 $ 'AB'
(('B','C') chg fh y.),"1 h1,"1 ('A','C') chg fh y.
)
fh =: >&{:
例解
]y0 =. 2 1 $ 'AB'
A h1 (円盤1ケ)
B 1 step
hr ^:(1) y0
AAC h2 (円盤2ケ)
CBB 3 steps
hr ^:(2) y0
AABACCA h3 (円盤3ケ))
BCCBABB 7 steps
hr ^:(3) y0
AACABBAACCBCAAC h4 (円盤4ケ)
CBBCACCBBAABCBB 15 steps
hr ^:(4) y0
AABACCAABBCBAABACCACBBCCAABACCA h5 (円盤5ケ)
BCCBABBCCAACBCCBABBACAABBCCBABB 31 steps
ここで考える。 J言語での POWER (演算子の反復)は、再帰法の内なのかな?
某書にあった「再帰法は漸化式だ。」と? 「再帰呼出し」の定義は?
4. ハノイの塔(再帰)・大人のプログラム (APL と J-Explicit)
1) 西川のAPL(再帰)プログラム
ここで、「はしがき」に述べた、西川の「ハノイの塔(再帰プログラム)」に
戻る。
元来は、西川著のAPL言語のテキスト(文献2、pp.129-132)に発する。 なお、
後述のJに合わせるため、テキストのプログラムで、変数の一部の入れ換えを行った。
再録するには、例の特殊APL記号のフォントが障害になるので、不十分の点は御寛恕
頂きたい。 例えば、コメント(ä Cap null 帽子小丸)や書式化関数(® Top null
屋根小丸)など、多数のAPL特殊フォントは、一般のワープロには無いので。
▽ HANOI[□] ▽
[0] D HANOI N;X;Y;Z
[1] ä TOWER OF HANOI
[2] X ← D[1]
[3] Y ← D[2]
[4] Z ← D[3]
[5] IF: → (0=N)/0
[6] ELSE: (X, Z, Y) HANOI N-1
[7] 'MOVE ', ( ® N) ,' FROM ',X,' TO ',Y
[8] (Z, Y, X) HANOI N-1
▽
【註】 行[5],[6] 中の IF: や ELSE: は 行ラベル。
行[5]の意味は、(0=N) が成立すれば([0]行へ)終了する。
APL例解 'ABC' HANOI 3
MOVE 1 FROM A TO B
MOVE 2 FROM A TO C
MOVE 1 FROM B TO C
MOVE 3 FROM A TO B
MOVE 1 FROM C TO A
MOVE 2 FROM C TO B
MOVE 1 FROM A TO B
( APL フォントの問題があるので、実際の西川プログラムは、末尾の付録に再録
)
【註】 再帰演算を許さないAPLシステムもある。 中野が20年来、愛用している
Dyna APL (DYNAX社、第1.0 版 1992年 2月)は、同じプログラムで、
RUN
には入るが、文番号[2] か [3] で WS full エラーを起こす。 再帰法の原点を発見
出来ずに、到達出来ない「堂々巡り」をやっているらしい。
また、再帰演算を許すならば、APL以外の言語、例えば TURBO Pascal の
入門書でも、上と同巧の再帰法プログラムが例示されている。 (文献2−a)
下例は、柱 A から柱 C へ移す場合であるが、良く似たプログラムである。
procedure move_disk (n, a, b c : integer);
begin if n>0 then begin
move_disk(n-1, a, b, c);
writeln(n: 3, ':', a ' -> ' ,c');
move_disk(n-1, b, a, c);
end; end;
2)西川のJ言語(再帰、Explicit的)プログラム
次に、J言語による西川プログラム(文献5)を以下に示す。
これは、いわゆる J の Explicit な構文であり、APLプログラムと殆ど同じである。
Tacit な構文は、難物であるので、次節に述べる。
NB. Tower of Hanoi
NB. by T. Nishikawa, 2005/8/23
wr=: 1!:2&2
hanoi =: 3 : 0
:
if. x. = 0
do. y.
else.
p =. (x. - 1) hanoi (0 2 1 { y.)
wr 'Move ', (": x.),' from ', (0{ y.), ' to ', (1{ y.)
r =. (x. - 1) hanoi (2 1 0 { y.)
end.
'*** end ***'
)
J例解 3 hanoi 'ABC'
Move 1 from A to B
Move 2 from A to C
Move 1 from B to C
Move 3 from A to B
Move 1 from C to A
Move 2 from C to B
Move 1 from A to B
*** end ***
【註】 J のこの例は、前例と比較すれば、3本柱の内、BとCとが入れ換わった
場合が示されているかも知れぬ。 (0.節の末尾の説明を参照。)
3) 中野の 大人の仲間入り的プログラム
前節2,3.の中野流プログラム hand や h1 rから、先に予言した如く、文字交換の
関数 chg を使わんでも良いと云うもの。
NB. by Y. NAKANO 2005.8.30
hanoin =: 3 : 0
hz =: 2 1 $ ' '
:
if. x. = 0 do. (2, x.) $ y.
else. (x. - 1) hanoin (0 2 1 { y.)
wr hz =: hz, "1 (2 1 $ (0{ y.), (1 {y.))
(x. - 1) hanoin (2 1 0 { y.) end.
)
直前の西川流とソックリであるが、出力は異なり、先の中野例の如く簡潔となる。
小学生向けに「再帰法」の説明は難儀であるから、文字交換(関数 chg)を利用したの
であった。
5. ハノイの塔(再帰法)の別解
1) 竹内流プログラム hn
この原稿が殆ど出来て、摺り合わせのチェック段階に来た後に、山下 FAX は、慶応
大学、竹内先生の旧報告を再発見と伝えて来た(文献14)。
hn =: 3 : 0
if. y. = 1
do. 1 3 $ _1 0 1
else. ( 0 2 1 {"1 hn <: y.), ((-y.),0,y.), 1 0 2 {"1 hn <: y.
end.
)
例解 hn 3 NB. (円盤 3ケ の場合)
_1 0 1
_2 2 0 説明 「数字 _n は、 n 番目のチップ(円盤)を
0 1 _1 を取り、数字 n のところ に置く」
_3 0 3 と云う意味だそうです。
1 _1 0
0 _2 2
_1 0 1
この竹内プログラムは仲々、秀逸である。
しかし、小学生にも判るように、との条件からすれば、判り難い。
そこで中野は、今までの例の如く、柱名 A B C との対応をも、出力するように、
小さな改良を加えた。 柱 C を作業用 としての プログラム hnacb である。
これによる、小学生教育の原稿を試作した(関数 hnacb は簡単だから表示は省略)。
hnacb 2 最初、柱 A に円盤 1(小) と 2 (大)が刺さっている。
A C B 1(上)、2(下)とする。
_1 1 0 円盤 1 を柱 A から取って柱 C へ移す。 _記号は除去を意味する。
_2 0 2 2 A B 0は何もしないを示す。
0 _1 1 1 C B へ。 単なる数字は置く事を示す。
結局、柱 B には円盤 1(上)と 2(下)が移て来た。 3手で完了。
hnacb 3 最初、柱 A に、円盤 1(小)、 2(中)、3(大)が、この順序で
A C B 刺さっている。
_1 0 1 円盤 1 を柱 A から取って柱 B へ移す。 _記号は除去を意味する。
_2 2 0 2 A C 0は何もしないを示す。
0 1 _1 1 B C 単なる数字は置く事を示す。
_3 0 3 3 A B
1 _1 0 1 C A
0 _2 2 2 C B
_1 0 1 1 A B
結局、柱 B には円盤 1(上)、2(中)、 3(下)が移て来た。 7手で完了。
【注意】 今回の手順3手までを、円盤数が2つの前例と比べると、柱名 B と C とが
交換されている事がわかる。 つまり、前の手順で (B, C) 交換したものを、
利用すれば、円盤枚数で次の場合の手順の前半は済む事が判る。
同じ様に、第5手から7手目までは、柱名の交換(A,C)をしたものを利用すれ
ば良い。 中央の(今は第4手目)は、最大円盤を、柱 A から柱 B へ移動する だけであるらしい。
直前の手順を少々変えて、次の手順を得る方法を、数学では、再帰法と呼ぶ。
英語では リカージョン RECURSION と呼ぶ。
次の円盤枚数 4 の場合の手の予想は:
前半の7手は、枚数3の手順で、柱名交換(B,C)したものを利用する。
第8手目(中央)は、最大円盤4を直接、柱 A から B へ。
後半の7手は、枚数3の手順で、柱名交換(A,C)したものを利用する。
全部で15手と予想される。
では、大人の実際のプログラムの結果はどうか?
hnacb 4 最初、柱 A に、円盤 1、2、3、4 が、この小大順で刺してある。
A C B
_1 1 0 円盤 1 を柱 A から取って柱 C へ移す。
_2 0 2 2 A B
0 _1 1 1 C B
-3 3 0 3 A C
1 0 _1 1 B A
0 2 _2 2 B C
_1 1 0 1 A C
_4 0 4 4 A B
0 _1 1 1 C B
2 _2 0 2 C A
1 0 _1 1 B A
0 _3 3 3 C B
_1 1 0 1 A C
_2 0 2 2 A B
0 _1 1 1 C B
結局、柱 B には円盤 1(上)、2(中の小)、 3(中の大)4(下)が移て来た。
15手で完了。 どうでしたか? 予想と合っていましたか?
2) 表示 の 改良
前項の操作、及び4.節の西川のAPLプログラムに例「円盤1を柱あからCへ
移す」等は、記号的に 1AC 等と表示したら、簡潔で良いと思われる。
中野の1.、2.、3.節の例および 次の 6.節の Iverson あるいは Hui の例は
簡潔ではあるが、移動対象の円盤の番号は示してはいない。
そこで、表示の改良に意味がある。
そこで中野は、その為の関数 pkupw (意味は pickup writing) を 考えた。
例1)中野流 これはタテ書き 例3) Iverson or Hui 流 (6節参照)
'ACB' pkupw (hn 2) 2 h y =.'ABC'
121
AAC AAC
CBB CBB
例2)中野流 これはヨコ書き 例4)竹内流 ヨコ書き
hnacb 2 hn 2
A C B
_1 1 0 _1 1 0
_2 0 2 _2 0 2
0 _1 1 0 _1 1
関数 pkupw =: 3 : 0
:
yn =. 0{ $ y.
pz =. 3 1 $ ' '
i =. 0
while. yn > i do.
iy =. ,(i{y.)
im =. mx iy
pk =. (":im) ,"1 (x. pkup iy)
pz =. pz, "1 pk
i=. i+1
end.
pz =. }. "1 pz
|: (yn, 3) $ pw =. 0 { pz
)
mx =: >./
pkup =: 3 : 0
:
(xy # x.) /: (xy =. (-.(y. = 0))) # y.
)
例3)中野流 最簡ヨコ書き
'A C B' hn012 2 関数の左引き数を柱の文字表示と兼用にしたもの。
_1 1 0 小さな工夫に付き、関数 hn012 の表示は省略。
_2 0
2
先の関数 hnacb などでも同様。
0 _1 1 この様な工夫も面白い。
【注意】竹内流ハノイで、円盤移動を「負数、例えば -1 を取って、正数 1 に移す」
とあるのは、例えば「0 1 2」の「最小数 0 を取って、最大数 2 に移す」と
しても、同じ事である。 上記のプログラムの幾つかは、それを利用している。 次節6.の中野関数 hc などに於いても同じ。
6.J言語・プロ級のプログラム(J の Tacit 構文)
西川 によれば、Jの「ハノイの塔」の Tacit プログラムは、すでに Iverson あるい
は Hui によって、J Introduction and Dictionary の中で、与えられていた。
(文献3−a,b)
1)Iverson and/or Hui 流
NB. Original version
NB. J Introduction and Dictionary J2 (1995) p.23
NB. J Introduction and Dictionary J3 (1996) p.47
h =. b ` (p,. q,. r) @. c tacit な条件分岐構文 (・・・`・・・ @.・・・)
c =. 1: < [ c の条件で 0 (<1 の事)なら b の部分へ。
前節 Explicit構文の do. 文 (2, x.) $ y. 相当。
b =. 2 &, @[ $ ] b は結果を 2行で表示するのみ。
c の条件で 1 (>0 の事)なら (p,. q,. r,.) の部分へ。
前節 Explicit構文の do. 文 相当。
p =. <:@[ h 1: A. ] 1: A. 'ABC' は 前節の (0 2 1) { y. 相当。
<:@ は、その時の左引数から 1 を引いた値。
前節 Explicit構文の (x. - 1 ) 部分に 相当。
q =. 1: h ] 2 1 $ 'AB' の文字列を採る意味。
r =. <:@[ h 5: A. ] 5: A. 'ABC' は 前節の (2 1 0) { y. 相当。
前節 Explicit構文の (x. - 1 ) で始まる第2式に相当。
Tacit 例解
NB. 3 h x =. 'ABC'
NB. AABACCA
NB. BCCBABB
NB. 0 1 2 3 4 <@h "0 1 x <@h"0 1 は box 化して纏める為。 NB. ++-+---+-------+---------------+
NB. ||A|AAC|AABACCA|AACABBAACCBCAAC|
NB. ||B|CBB|BCCBABB|CBBCACCBBAABCBB|
NB. ++-+---+-------+---------------+
慣れるのは大変であろうか?
2) 中野流 Tacit関数 hc
これぞ、大人の内の大人のプログラムか?と思われる。 竹内関数 hn の Tacit化
である。 竹内先生も元来は、同じ事を狙ったが、Explicit に止めたのかも知れぬ。
hc =: bc ` (pc ,. qc ,. rc) @. cc NB. or omit ,. rc
cc =: 1: <[
bc =: 3 &, @[ $ ] NB. 3 (or 2行 at h )
pc =: <:@[ hc 1: A.]
qc =: 1: hc]
rc =: <:@[ hc 2: A.] NB. 2 (or 順列 5 番 at h )
例1) 1 hc 'ACB' 1 hc '021' 対照 1 h 'ABC' 1 h '012'
A 0 A 0
C 2 (左の中央行欠、関数 bcで 3→2も可) B 1 B 1
例2) 2 hc 'ACB' 2 hc '021' 対照 2 h 'ABC' 2 h '012'
AAC 002 AAC 002
BCA 120 (左の中央行欠)
CBB 211 CBB 211
例3) 3 hc 'ACB' 3 hc '021' 対照 3 h 'ABC' 3 h '012'
AABACCA 0010220 AABACCA 0010220
CBACBAC 2102102 (左の中央行欠)
BCCBABB 1221011 BCCBABB 1221011
例4) 4 hc 'ACB' 4 hc '021' 対照 4 h 'ABC' 4 h '012'
AACABBAACCBCAAC 002011002212002 AACABBAACCBCAAC 002011002212002
BCABCABCABCABCA 120120120120120 (左の中央行欠)
CBBCACCBBAABCBB 211202211001211 CBBCACCBBAABCBB 211202211001211
結局、竹内流関数 hn は「負数を利用、3字ヨコ書」、中野流 hc は「最小、最大数
を利用、3字タテ書」だけの違いで、ほぼ同じものである。
そして、前者 hn は Explicit 的に対し、後者 hc は Iverson らと同じく、Tacit 的で
ある。 かくて、目的は達成された。
ただし、 Iverson らのそれとは、上例で見る如く、「中央行の有無」だけの違いである。
かくて、前節3.の冒頭で述べた如く「余りエレガントな事をやれば、先人の真似事に
近くなる。」を痛感させられる。
3) 「中野流」 左右の引数を交換した tacit プロ
柱の記号 ’ACB’等を左引数にして置くと、操作の表示が何かと見易くなる。
先行の諸節の例示から推察出来よう。 関数 hd である。
hd =: bd ` (pd ,. qd ,. rd) @. cd
cd =: 1: < ]
bd =: ] &, @ 3: $ [
pd =: 1: A.[hd <: @ ]
qd =: (_1, 0, 1) & * @ ]
rd =: 2: A.[ hd <: @ ]
理屈は, 前項2)の 関数 hc と比較すれば、理解出来よう。
首尾は如何に? 5.節 1)の竹内関数(Explicit) hn の例と比較すれば
ピッタリである(結果は、行列転置して比べているが)。
この 中野関数 hd は勿論 (Tacit) である。
竹内 中野 比 較
hn 3 |: (_1 0 1 hd 3 ) (hn 3) = (|: _1 0 1 hd 3 )
_1 0 1 _1 0 1 1 1 1
_2 2 0 _2 2 0 1 1 1
0 1 _1 0 1 _1 1 1 1
_3 0 3 _3 0 3 1 1 1
1 _1 0 1 _1 0 1 1 1
0 _2 2 0 _2 2 1 1 1
_1 0 1 _1 0 1 1 1 1 確かに合致!
4) 「中野流 1行 プログラム」 he
プログラム作成の「美学」として、最後にたった1行の tacit プロを
お目に掛けよう。 h は hanoii、e は ドイツ語の ein(1) の意味。
he=: (]&,@3:$[)`((1:A.[he<:@]),.((_1,0,1)&*@]),.(2:A.[he<:@]))@.(1:<])
結果は、直前の例と同じ。 しかし、この関数入力は、間違い易くて注意が要る!
7. ま と め
様々な工夫で Chinese Puzzle ' Tower of HANOI ' が楽しめた。
「小学生にも判るように」との条件付けは意味があった。
初等解から発展して、 大人の仲間入り的プログラムが多く試みられた。
しかし、「エレガント」にやれば、先人の真似事に陥るかも?!
大人向けよりは、真の意味で「小学生向け」に今後の発展が欲しいものだ。
文 献
1)山下 FAX ('05.8.22.16:00) 「ハノイの塔」のJ版を
2)西川利男・日本IBM 共著:「基礎からのAPL」pp.130-132
サイエンスハウス 初版1986、 新装第1版 1991.01.09
−a)永野・長島「Pascal入門・TURBO Pascal演習」東京大学出版会、1988 初版
1996 第2版 p.84
3)西川 FAX ('05.8.22.17:00) Jによる「ハノイの塔」のプログラム
−a)" J Introduction and Dictionary " 1995 (J2) p.23 RECURSION −b)" J Introduction and Dictionary " 1996 (J3) p.47 22.Recursion
4)山下 FAX ('05.8.23.11:15) 「ハノイの塔J版を小学生に判らせたい」
5)西川 FAX ('05.8.23.13:15) 「ハノイの塔J版」Tacit版
から Explicit版へ
6)一松信・竹之内修 編「改訂増補 新数学事典」 pp.935-936
大阪書籍 1979 初版、 1991.11.20 改訂増補
7)中野 FAX ('05.8.25) 「ハノイの塔」への「中野」論理
8)中野 FAX ('05.8.28.) 「ハノイの塔・中野論理」Jプロ hand
9)西川 FAX ('05.8.28 ) 「ハノイ塔問題の本質は再帰法にある」
10)山下 FAX ('05.8.28.19:24) 「再帰法の利点は? 小学生に判るかな?」
11)中野 FAX ('05.8.29.7:30) 「hr 中野流再帰プログラム」発信
12)西川 FAX ('05.8.29.7:40) Tacit 構文例の解説を加えよ!
13)西川 FAX ('05.8.29.10:40)「再帰呼出法」の資料 11頁
14)山下 FAX ('05.9.03. 9:53)竹内先生作「ハノイの塔」JAPLA-97 p.22 発見
15)中野 FAX ('05.9.21.12:30)「ハノイの塔」Tacit で
1行
プログラム完成!
[付録] 西川の APL プログラム (貼り付け)