(published: May. 10, 2001)
Active Basicのバージョンアップにより、 プロシージャ定義が出来る様になりました。 という訳で、再帰処理の定番中の定番である、 ハノイの塔の解答プログラムを作成してみました。
垂直に立てられた3本の棒のうち、1本に、 それぞれ大きさの異なる円盤が、小さいほうを上に、 大きいほうを下にして刺さっています。
このゲームの目的は、円盤の山を別の棒にそのまま移すことです。 但し、
実行すると、塔の高さをたずねてきます。 z、x、c、vキーで高さを指定し、スペースバーを押すと、解法を出力します。
解法は、F(最初に円盤が乗っている柱)、 T(最終的に円盤を移すべき目的地の柱)、 V(円盤を移すために経由される柱)の3種類の文字から成る、 2文字の文字列の組み合わせで示されます。
1文字目がどの柱から円盤を動かすか、 そして2文字目がどの柱に円盤を移すかを表します。 例えば、FVとあった場合は、 柱Fに刺さっている円盤の山の中から、一番上の1枚を、 柱Vに移すことを表します。
1 g=0 5 while g=0 10 cls 100 sub hanoi(h,f$,t$,v$) 110 i=h 120 if i=1 then mad(f$,t$) else hanoi(i-1,f$,v$,t$):mad(f$,t$):hanoi(i-1,v$,t$,f$) 130 endsub 200 sub mad(f$,v$) 210 print f$+v$+","; 220 endsub 300 f=0:h=1 305 locate 0,2:print "[z]:-10, [x]:-1, [c]:+1, [v]:+10, [space]:solve" 310 while f=0 320 locate 0,0:print "height";h;" "; 330 k$=inkey$ 340 if k$="z" then h=h-10 350 if k$="x" then h=h-1 360 if k$="c" then h=h+1 370 if k$="v" then h=h+10 380 if h<1 then h=1 390 if h>63 then h=63 400 if k$=" " then f=1 410 wend 420 locate 0,2:print " " 430 locate 0,1:hanoi(h,"F","T","V") 440 print "[q.e.d.]" 442 print "retr[y]/e[n]d"; 445 f=0 450 while f=0 460 k$=inkey$ 470 if k$="y" then f=1 480 if k$="n" then f=-1:g=1 490 wend 500 wend 510 end