CASIO pocket computer
PB-100の宇宙

ハノイの塔 on PB-100
NUAO 氏

公開日 2022/10/14
RUN DEG
 1> 3

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

ハノイの塔のルール

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

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

使い方

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

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

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

プログラムリスト

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

P1
G(F)=A:H(F)=B:I(F)=C:J(F)=D
IF J(F)>1;A=G(F):B=I(F):C=H(F):D=J(F)-1:F=F+4:GOSUB #1
PRINT CSR 0;G(F);">";H(F)
IF J(F)>1;A=I(F):B=H(F):C=G(F):D=J(F)-1:F=F+4:GOSUB #1
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

変数アサイン

変数説明
A移動する元の棒 No.
B移動する先の棒 No.
C移動に無関係の棒 No.
Dディスク枚数
Fスタックポインタ
G(*)スタックメモリ

行番号マップ

P0 メインルーチン

行番号解説
1
2
3棒 No.1 から棒 No.2 へ D 枚のディスクを移動する

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

行番号解説
1引数をスタックメモリに格納
21枚少ないディスクを G(F) から G(F+2) へ移動
3G(F) から G(F+1) へのディスク移動を表示
41枚少ないディスクを G(F+2) から G(F+1) へ移動
5スタックポインタを浅くしてリターン

注意

実プログラムは、ステップ数削減の為、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日にリリースされました.

更新履歴

日付ノート
2022/10/14公開.
2022/10/17

NUAO 氏によって「プログラムについて」「注意」「基本的な考え方」の各セクションが追記されました.「基本的な考え方」の図も NUAO 氏の制作です.「行番号マップ」の解説が「プログラムリスト」と異なる問題について修正しました.「変数アサイン」が微修正されました.

「後に続いた作品」に門真なむ氏によるバージョンを追記しました.