ハノイの塔訂正版

! UBASIC のサンプルを、変形したもの。
!
! Ｋ番目の円盤を、Ｓから、Ｄへ動かす方法。
! １つ上の、
!（Ｋ－１）番目の円盤を、Ｓ、Ｄ、でない塔へ移動し、
! Ｋ番目の円盤を、Ｓから、Ｄへ移動する。
! 先の（Ｋ－１）番目の円盤を、Ｄの上に積んで終了。
!
! 以上の処理を、再帰的にコールし、
! Ｋ＝１になる毎にリターンしてくる。
!-----------------------
! ハノイの塔 2006.7.17
!-----------------------
SET WINDOW 0,639,479,0

DIM X(3),Y(3)
LET K=7 ! 塔の段数(1~16)
LET DL=0.02 ! 毎回の間（秒数）

PRINT "塔の段数(1~30)=";K
PRINT "毎回の間(0~10秒)=";DL

LET X(1)=170
LET Y(1)=270
LET X(2)=X(1)+168
LET Y(2)=Y(1)
LET X(3)=X(2)+168
LET Y(3)=Y(2)

!----------
LET YT=INT(150/K)
LET XT=INT( YT/2 )
IF 10<YT THEN LET YT=10
LET S=1
LET D=3
LET all=1+2+3 ! 空いている塔の番号を、all-S-D で算出。
CALL init00
WAIT DELAY 0.5
CALL MovK00( K, S, D)
STOP

!----------
SUB MovK00( K, S, D )
IF 1<K THEN CALL MovK00( K-1, S, all-S-D )
CALL MovSD( K, S, D )
IF 1<K THEN CALL MovK00( K-1, all-S-D, D )
END SUB

!----------経過画面
SUB MovSD( K, S, D )
SELECT CASE S*10+D
CASE 12
PRINT "A->";K;"->B "
CASE 13
PRINT "A->";K;"--------->C"
CASE 21
PRINT "A<-";K;"<-B "
CASE 23
PRINT TAB(9);"B->";K;"->C"
CASE 31
PRINT "A<---------";K;"<-C"
CASE 32
PRINT TAB(9);"B<-";K;"<-C"
END SELECT
WAIT DELAY DL
!----------
SET LINE COLOR 0
LET x1=X(S)-K*XT
LET y1=Y(S)
LET x2=X(S)+K*XT
LET y2=Y(S)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
!----------
LET Y(S)=Y(S)+YT
LET Y(D)=Y(D)-YT
!----------
SET LINE COLOR 1
LET x1=X(D)-K*XT
LET y1=Y(D)
LET x2=X(D)+K*XT
LET y2=Y(D)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
!----------
SET TEXT COLOR 0
PLOT TEXT,AT 36*8,23*16,USING "real times=%%%%%":R9-1
SET TEXT COLOR 1
PLOT TEXT,AT 36*8,23*16,USING "real times=%%%%%":R9
LET R9=R9+1
END SUB

!----------初期画面
SUB init00
CLEAR
SET TEXT COLOR 2
PLOT TEXT,AT 8*30,16*6:"ハノイの塔"
LET w=K
IF w<10 THEN LET w=10
FOR w1=1 TO 3
FOR w2=Y(w1)-YT*w+2 TO Y(w1)+2 STEP YT
PLOT TEXT,AT X(w1)-3,w2:"*"
NEXT w2
NEXT w1
FOR w=X(1)-8*10 TO X(3)+8*10 STEP 10
PLOT TEXT,AT w,Y(1)+10+2:"*"
NEXT w
PLOT TEXT,AT X(1),Y(1)+30:"A"
PLOT TEXT,AT X(2),Y(1)+30:"B"
PLOT TEXT,AT X(3),Y(1)+30:"C"
SET LINE COLOR 1
FOR w=K*XT TO XT STEP -XT
LET Y(S)=Y(S)-YT
LET x1=X(S)-w
LET y1=Y(S)
LET x2=X(S)+w
LET y2=Y(S)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
NEXT w
SET TEXT COLOR 1
PLOT TEXT,AT 28*8,23*16,USING "N=%%":K
PLOT TEXT,AT 36*8,23*16,USING "real times=%%%%%":0
PLOT TEXT,AT 35*8,24*16,USING"final times=%%%%%":2^K-1
LET R9=1
END SUB

END

すっきりした良いプログラムですね。
移動先を 6-S-D にすることは私も気づいたのですが、完成には至りませんでした。
のんびりと取り組んでみます。

６－Ｓ－Ｄが、空きの塔になるなど、UBASIC のサンプルに、
アルゴリズムを、依存しています。変形に過ぎません。
最初は、６が、何の数か判らず、
６＝１＋２＋３＝Ｓ＋空き＋Ｄで、意味が解りました。

! 補足。
! 次の５行の文は、問題を解くアルゴリズムの全て。
! UBASIC のサンプルに習っています。
! 解り難いので、展開します。
!----------
!SUB MovK00( K, S, D)
! IF 1<K THEN CALL MovK00( K-1, S, 6-S-D)
! CALL movSD( K, S, D)
! IF 1<K THEN CALL MovK00( K-1, 6-S-D, D)
!END SUB

!----------上と全く同じもの。
SUB MovK00( K, S, D)
IF 1<K THEN
CALL MovK00( K-1, S, 6-S-D) ! 移動要求 K-1,,1層 S→ 中継の塔
CALL movSD( K, S, D) ! 実行 K層 S →D
CALL MovK00( K-1, 6-S-D, D) ! 移動要求 K-1,,1層中継の塔 →D
ELSE
CALL movSD( 1, S, D) ! 実行 (K=1)層 S →D
END IF
END SUB

! A,B,C の塔は、左から、1,2,3 で識別。S,D で使用。
! 中継する塔の番号は、(1+2+3)-S-D= 6-S-D で計算される。

! 円盤は、上から、1,2,3,,,K 層の、層の番号で、識別。
! プログラム上の円盤は、水平移動だけで、上下移動は無し。
! 画面表示上だけ、空中に浮かないように、上下を付加。

! K-1,,1層の実行回数を N(k-1) とすると、N(k) は、
! 1<K の時、 N(k)= N(k-1)+1+N(k-1)= 2*N(k-1)+1
! K=1 の時、 N(1)=1

! K-1,,1層を２回、K層を１回で、能率が良い。

!----------能率の悪かった初回版( 似てないが、同じもの)
!SUB MOVK00( K,S,D)
! IF 1<K THEN
! CALL MOVK00( K-1,S,D) ! 移動要求 K-1,,1層 S→ D
! CALL movSD( K,S,2) ! 実行 K層 S →2(B 塔)
! CALL MOVK00( K-1,D,S) ! 移動要求 K-1,,1層 D→ S
! CALL movSD( K,2,D) ! 実行 K層 2(B 塔) →D
! CALL MOVK00( K-1,S,D) ! 移動要求 K-1,,1層 S→ D
! ELSE
! CALL movSD( 1,S,D) ! 実行 (K=1)層 S →D
! END IF
!END SUB

! K-1,,1層の実行回数を N(k-1) とすると、N(k) は、
! 1<K の時、 N(k)= N(k-1)+1+N(k-1)+1+N(k-1)= 3*N(k-1)+2
! K=1 の時、 N(1)=1

! K-1,,1層を３回、K層を２回で、能率が悪い。

!----------
!再帰型は、非常に解りにくい。
!しかし、小さな文が、巨大を扱える魅力があります。
!失ってはならない先輩たちの、遺産です。
!K=2 ぐらいで、最初から最後までの、その動きを、
!追跡してみられる事を、お勧めします。
!
!ツリー構造まで、書きたかったが・・力が無い。

ハノイの塔　訂正版	返事を書く
諏訪　雄治 2006/07/17 07:23:51
! UBASIC のサンプルを、変形したもの。 ! ! Ｋ番目の円盤を、Ｓから、Ｄへ動かす方法。 ! １つ上の、 !（Ｋ－１）番目の円盤を、Ｓ、Ｄ、でない塔へ移動し、 ! Ｋ番目の円盤を、Ｓから、Ｄへ移動する。 ! 先の（Ｋ－１）番目の円盤を、Ｄの上に積んで終了。 ! ! 以上の処理を、再帰的にコールし、 ! Ｋ＝１になる毎にリターンしてくる。 !----------------------- ! ハノイの塔 2006.7.17 !----------------------- SET WINDOW 0,639,479,0 DIM X(3),Y(3) LET K=7 ! 塔の段数(1~16) LET DL=0.02 ! 毎回の間（秒数） PRINT "塔の段数(1~30)=";K PRINT "毎回の間(0~10秒)=";DL LET X(1)=170 LET Y(1)=270 LET X(2)=X(1)+168 LET Y(2)=Y(1) LET X(3)=X(2)+168 LET Y(3)=Y(2) !---------- LET YT=INT(150/K) LET XT=INT( YT/2 ) IF 10<YT THEN LET YT=10 LET S=1 LET D=3 LET all=1+2+3 ! 空いている塔の番号を、all-S-D で算出。 CALL init00 WAIT DELAY 0.5 CALL MovK00( K, S, D) STOP !---------- SUB MovK00( K, S, D ) IF 1<K THEN CALL MovK00( K-1, S, all-S-D ) CALL MovSD( K, S, D ) IF 1<K THEN CALL MovK00( K-1, all-S-D, D ) END SUB !----------経過画面 SUB MovSD( K, S, D ) SELECT CASE S10+D CASE 12 PRINT "A->";K;"->B " CASE 13 PRINT "A->";K;"--------->C" CASE 21 PRINT "A<-";K;"<-B " CASE 23 PRINT TAB(9);"B->";K;"->C" CASE 31 PRINT "A<---------";K;"<-C" CASE 32 PRINT TAB(9);"B<-";K;"<-C" END SELECT WAIT DELAY DL !---------- SET LINE COLOR 0 LET x1=X(S)-KXT LET y1=Y(S) LET x2=X(S)+KXT LET y2=Y(S)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 !---------- LET Y(S)=Y(S)+YT LET Y(D)=Y(D)-YT !---------- SET LINE COLOR 1 LET x1=X(D)-KXT LET y1=Y(D) LET x2=X(D)+KXT LET y2=Y(D)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 !---------- SET TEXT COLOR 0 PLOT TEXT,AT 368,2316,USING "real times=%%%%%":R9-1 SET TEXT COLOR 1 PLOT TEXT,AT 368,2316,USING "real times=%%%%%":R9 LET R9=R9+1 END SUB !----------初期画面 SUB init00 CLEAR SET TEXT COLOR 2 PLOT TEXT,AT 830,166:"ハノイの塔" LET w=K IF w<10 THEN LET w=10 FOR w1=1 TO 3 FOR w2=Y(w1)-YTw+2 TO Y(w1)+2 STEP YT PLOT TEXT,AT X(w1)-3,w2:"" NEXT w2 NEXT w1 FOR w=X(1)-810 TO X(3)+810 STEP 10 PLOT TEXT,AT w,Y(1)+10+2:"" NEXT w PLOT TEXT,AT X(1),Y(1)+30:"A" PLOT TEXT,AT X(2),Y(1)+30:"B" PLOT TEXT,AT X(3),Y(1)+30:"C" SET LINE COLOR 1 FOR w=KXT TO XT STEP -XT LET Y(S)=Y(S)-YT LET x1=X(S)-w LET y1=Y(S) LET x2=X(S)+w LET y2=Y(S)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 NEXT w SET TEXT COLOR 1 PLOT TEXT,AT 288,2316,USING "N=%%":K PLOT TEXT,AT 368,2316,USING "real times=%%%%%":0 PLOT TEXT,AT 358,24*16,USING"final times=%%%%%":2^K-1 LET R9=1 END SUB END

Re: ハノイの塔　訂正版	返事を書く
荒田浩二 2006/07/17 19:33:10
すっきりした良いプログラムですね。移動先を 6-S-D にすることは私も気づいたのですが、完成には至りませんでした。のんびりと取り組んでみます。

Re: すっきりした良いプログラムですね。	返事を書く
諏訪　雄治 2006/07/18 00:13:43
６－Ｓ－Ｄが、空きの塔になるなど、UBASIC のサンプルに、アルゴリズムを、依存しています。変形に過ぎません。最初は、６が、何の数か判らず、６＝１＋２＋３＝Ｓ＋空き＋Ｄで、意味が解りました。

Re: ハノイの塔　訂正版	返事を書く
諏訪　雄治 2006/07/20 12:35:43
! 補足。 ! 次の５行の文は、問題を解くアルゴリズムの全て。 ! UBASIC のサンプルに習っています。 ! 解り難いので、展開します。 !---------- !SUB MovK00( K, S, D) ! IF 1<K THEN CALL MovK00( K-1, S, 6-S-D) ! CALL movSD( K, S, D) ! IF 1<K THEN CALL MovK00( K-1, 6-S-D, D) !END SUB !----------上と全く同じもの。 SUB MovK00( K, S, D) IF 1<K THEN CALL MovK00( K-1, S, 6-S-D) ! 移動要求 K-1,,1層 S→ 中継の塔 CALL movSD( K, S, D) ! 実行 K層 S →D CALL MovK00( K-1, 6-S-D, D) ! 移動要求 K-1,,1層中継の塔 →D ELSE CALL movSD( 1, S, D) ! 実行 (K=1)層 S →D END IF END SUB ! A,B,C の塔は、左から、1,2,3 で識別。S,D で使用。 ! 中継する塔の番号は、(1+2+3)-S-D= 6-S-D で計算される。 ! 円盤は、上から、1,2,3,,,K 層の、層の番号で、識別。 ! プログラム上の円盤は、水平移動だけで、上下移動は無し。 ! 画面表示上だけ、空中に浮かないように、上下を付加。 ! K-1,,1層の実行回数を N(k-1) とすると、N(k) は、 ! 1<K の時、 N(k)= N(k-1)+1+N(k-1)= 2N(k-1)+1 ! K=1 の時、 N(1)=1 ! K-1,,1層を２回、K層を１回で、能率が良い。 !----------能率の悪かった初回版( 似てないが、同じもの) !SUB MOVK00( K,S,D) ! IF 1<K THEN ! CALL MOVK00( K-1,S,D) ! 移動要求 K-1,,1層 S→ D ! CALL movSD( K,S,2) ! 実行 K層 S →2(B 塔) ! CALL MOVK00( K-1,D,S) ! 移動要求 K-1,,1層 D→ S ! CALL movSD( K,2,D) ! 実行 K層 2(B 塔) →D ! CALL MOVK00( K-1,S,D) ! 移動要求 K-1,,1層 S→ D ! ELSE ! CALL movSD( 1,S,D) ! 実行 (K=1)層 S →D ! END IF !END SUB ! K-1,,1層の実行回数を N(k-1) とすると、N(k) は、 ! 1<K の時、 N(k)= N(k-1)+1+N(k-1)+1+N(k-1)= 3N(k-1)+2 ! K=1 の時、 N(1)=1 ! K-1,,1層を３回、K層を２回で、能率が悪い。 !---------- !再帰型は、非常に解りにくい。 !しかし、小さな文が、巨大を扱える魅力があります。 !失ってはならない先輩たちの、遺産です。 !K=2 ぐらいで、最初から最後までの、その動きを、 !追跡してみられる事を、お勧めします。 ! !ツリー構造まで、書きたかったが・・力が無い。