ハノイの塔 on PB-100
NUAO 氏

RUN DEG
 1> 3

ハノイの塔を解くプログラムです．(ゲームではありません)

ハノイの塔のルール

左から No.1,2,3 の三本の棒が立っており、大きさが異なる何枚かのディスクが重なって、No.1 の棒に重なっています．

一度に一枚ずつディスクを動かし、全てのディスクを No.1 から No.2 に移動させます．但し、小さいディスクの上に大きいディスクを重ねることはできません．

使い方

プログラムを入力し、shift0 を RUN します．

ディスク数を入力します．最大5枚までです．

移動するディスクの棒番号を表示します．

プログラムリスト

P0
1 VAC
2 INPUT "DISKS=",D:IF D>5 THEN 2
3 A=1:B=2:C=3:GOSUB #1:END

P1
1 G(F)=A:H(F)=B:I(F)=C:J(F)=D
2 IF J(F)>1;A=G(F):B=I(F):C=H(F):D=J(F)-1:F=F+4:GOSUB #1
3 PRINT CSR 0;G(F);">";H(F)
4 IF J(F)>1;A=I(F):B=H(F):C=G(F):D=J(F)-1:F=F+4:GOSUB #1
5 F=F-4:RETURN

プログラムについて

BASIC は構造化言語ではありませんが、G(*) メモリとポインタを規定してスタックメモリを模擬することにより、再帰呼び出し風のアルゴリズムでハノイの塔の課題を解いています． 基本的な考え方を末尾に示します．

Pocket BASIC Simulator形式プログラムリスト

[P0]
1 VAC
2 INPUT "DISKS=",D:IF D>5 THEN 2
3 A=1:B=2:C=3:GOSUB #1:END

[P1]
1 G(F)=A:H(F)=B:I(F)=C:J(F)=D
2 IF J(F)>1;A=G(F):B=I(F):C=H(F):D=J(F)-1:F=F+4:GOSUB #1
3 PRINT CSR 0;G(F);">";H(F)
4 IF J(F)>1;A=I(F):B=H(F):C=G(F):D=J(F)-1:F=F+4:GOSUB #1
5 F=F-4:RETURN

変数アサイン

行番号マップ

P0 メインルーチン

P1 G(F) から G(F+1) へ D-1 枚のディスクを移動する

注意

実プログラムは、ステップ数削減の為、G(F+1) → H(F), G(F+2) → I(F), G(F+3) → J(F) に置き換えています．

基本的な考え方

「1から2へ、4枚のディスクを移動する」というメインプロセスは…

①「1から3へ、3枚のディスクを移動する」と、

②「1から2へ、1枚のディスクを移動する」と、

③「3から2へ、3枚のディスクを移動する」という、

①+②+③のサブプロセスに分解できる．

①と③で「3枚のディスクを動かす」際は、更にこのメインプロセス自身を(一枚減らして)呼び出せばよい．

但し、移動するディスクが1枚になった場合は呼び出しせず、ディスクを1枚動かすだけでよい．(その際に表示する)

以下同文．

PBロッキーより

『ハノイの塔 on PB-100』は NUAO 氏が当ホームページに寄稿されたプログラム作品です．HTML 化はPBロッキーが行い、その際に、他の掲載作とスタイルを統一するための変更を行いました．

本作も NUAO 氏の厚意によって本作品は Public Domain で提供されます．

後に続いた作品

本作品に触発された、門真なむ氏によるバージョンが10月16日にリリースされました．

更新履歴