新しく発言する EXIT インデックスへ
ハノイの塔訂正版

  ハノイの塔 訂正版 諏訪 雄治 2006/07/17 07:23:51 
  すっきりした良いプログラムですね。 荒田浩二 2006/07/17 19:33:10 
  │└6−S−Dが、空きの塔になるなど、UBASIC... 諏訪 雄治 2006/07/18 00:13:43 
  !補足。 諏訪 雄治 2006/07/20 12:35:43 

  ハノイの塔 訂正版 諏訪 雄治 2006/07/17 07:23:51  ツリーへ

ハノイの塔 訂正版 返事を書く
諏訪 雄治 2006/07/17 07:23:51
! UBASIC のサンプルを、変形したもの。
!
! K番目の円盤を、Sから、Dへ動かす方法。
! 1つ上の、
!(K−1)番目の円盤を、S、D、でない塔へ移動し、
! K番目の円盤を、Sから、Dへ移動する。
! 先の(K−1)番目の円盤を、Dの上に積んで終了。
!
! 以上の処理を、再帰的にコールし、
! K=1になる毎にリターンしてくる。
!-----------------------
! ハノイの塔 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

  すっきりした良いプログラムですね。 荒田浩二 2006/07/17 19:33:10  ツリーへ

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

  │└6−S−Dが、空きの塔になるなど、UBASIC... 諏訪 雄治 2006/07/18 00:13:43  ツリーへ

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

  !補足。 諏訪 雄治 2006/07/20 12:35:43  ツリーへ

Re: ハノイの塔 訂正版 返事を書く
諏訪 雄治 2006/07/20 12:35:43
! 補足。
! 次の5行の文は、問題を解くアルゴリズムの全て。
! 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層 を2回、K層を1回で、能率が良い。

!----------能率の悪かった初回版( 似てないが、同じもの)
!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層 を3回、K層を2回で、能率が悪い。

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


インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。