ハノイの塔１ページ

　　ハノイの塔　１ページ 諏訪　雄治 2006/07/16 03:39:47 
　　├!前のページとつなぐ 諏訪　雄治 2006/07/16 03:40:51 
　　├!page-2の修正。取り替える。 諏訪　雄治 2006/07/16 11:19:26 
　　└ハノイの塔の最少移動手順はすでに知られて... 荒田浩二 2006/07/16 19:47:48 
　　　└修正 荒田浩二 2006/07/16 19:54:34 
　　　　└分かってます。どこかが、おかしい。できれ... 諏訪　雄治 2006/07/16 22:05:17

　　ハノイの塔　１ページ 諏訪　雄治 2006/07/16 03:39:47  ツリーへ

ハノイの塔　１ページ 返事を書く

諏訪　雄治 2006/07/16 03:39:47

!円盤は、上に乗る方が小さくなければならないルールで、
!全ての円盤を、移す問題。我流のアルゴリズムの為か
!UBASIC のサンプルより、何倍も移動回数が多く劣っている。
!LOCAL 変数も使われていません。書き直し歓迎。
!
!"HANOI.BAS"
!-----------------------
! ハノイの塔　2006.7.15
!-----------------------
SET WINDOW 0,639,479,0

DIM KK(200),X(3),Y(3)
LET SP=201
LET K=5 ! 塔の段数(1~12)
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 N9=1
FOR w=2 TO K
LET N9=3*N9+2
NEXT w ! final times

LET YT=INT(150/K)
LET XT=INT( YT/2 )
IF 10<YT THEN LET YT=10
LET S=1
LET D=3
GOSUB 600 ! *PAT00S
WAIT DELAY 0.5
GOSUB 100 ! *MOVK00
STOP

!----------
100 ! *MOVK00
IF K=<1 THEN 200 ! *MOVSD
LET SP=SP-1
LET KK(SP)=K
LET SP=SP-1
LET KK(SP)=D
LET SP=SP-1
LET KK(SP)=S ! push K,D,S
LET K=K-1
GOSUB 100 ! *MOVK00
GOSUB 300 ! *MOVS2
SWAP S,D
GOSUB 100 ! *MOVK00
SWAP S,D
GOSUB 400 ! *MOV2D
GOSUB 100 ! *MOVK00
LET S=KK(SP)
LET SP=SP+1
LET D=KK(SP)
LET SP=SP+1
LET K=KK(SP)
LET SP=SP+1 ! pop S,D,K
RETURN

!----------
200 ! *MOVSD
IF S<D THEN
PRINT "A->";K;"--------->C"
ELSE
PRINT "A<---------";K;"<-C"
END IF
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
GOTO 500 ! *PRTIME

!次のページとつなぐ

　　├!前のページとつなぐ 諏訪　雄治 2006/07/16 03:40:51  ツリーへ

Re: ハノイの塔　１ページ 返事を書く

諏訪　雄治 2006/07/16 03:40:51

!前のページとつなぐ

300 ! *MOVS2
IF S<2 THEN
PRINT "A->";K+1;"->B "
ELSE
PRINT " B<-";K+1;"<-C"
END IF
WAIT DELAY DL
LET W=K+1
SET LINE COLOR 0
LET x1=X(S)-W*XT
LET y1=Y(S)
LET x2=X(S)+W*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(2)=Y(2)-YT
SET LINE COLOR 1
LET x1=X(2)-W*XT
LET y1=Y(2)
LET x2=X(2)+W*XT
LET y2=Y(2)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
GOTO 500 ! *PRTIME

400 ! *MOV2D
IF 2<D THEN
PRINT " B->";K+1;"->C"
ELSE
PRINT "A<-";K+1;"<-B "
END IF
WAIT DELAY DL
LET W=K+1
SET LINE COLOR 0
LET x1=X(2)-W*XT
LET y1=Y(2)
LET x2=X(2)+W*XT
LET y2=Y(2)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
LET Y(2)=Y(2)+YT
LET Y(D)=Y(D)-YT
SET LINE COLOR 1
LET x1=X(D)-W*XT
LET y1=Y(D)
LET x2=X(D)+W*XT
LET y2=Y(D)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1

500 ! *PRTIME
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
RETURN

!----------
600 ! *PAT00S
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=%%%%%%%":N9
! LOCATE 0,0
LET R9=1
RETURN

END

　　├!page-2の修正。取り替える。 諏訪　雄治 2006/07/16 11:19:26  ツリーへ

Re: ハノイの塔　１ページ 返事を書く

諏訪　雄治 2006/07/16 11:19:26

!page-2 の修正。取り替える。

300 ! *MOVS2
IF S<2 THEN
PRINT "A->";K+1;"->B "
ELSE
PRINT TAB(9);"B<-";K+1;"<-C" ! tab(9)に変更。copyで" "抜ける
END IF
WAIT DELAY DL
LET W=K+1
SET LINE COLOR 0
LET x1=X(S)-W*XT
LET y1=Y(S)
LET x2=X(S)+W*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(2)=Y(2)-YT
SET LINE COLOR 1
LET x1=X(2)-W*XT
LET y1=Y(2)
LET x2=X(2)+W*XT
LET y2=Y(2)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
GOTO 500 ! *PRTIME

400 ! *MOV2D
IF 2<D THEN
PRINT TAB(9);"B->";K+1;"->C" ! tab(9)に変更。copyで" "抜ける
ELSE
PRINT "A<-";K+1;"<-B "
END IF
WAIT DELAY DL
LET W=K+1
SET LINE COLOR 0
LET x1=X(2)-W*XT
LET y1=Y(2)
LET x2=X(2)+W*XT
LET y2=Y(2)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1
LET Y(2)=Y(2)+YT
LET Y(D)=Y(D)-YT
SET LINE COLOR 1
LET x1=X(D)-W*XT
LET y1=Y(D)
LET x2=X(D)+W*XT
LET y2=Y(D)+YT-1
PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1

500 ! *PRTIME
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
RETURN

!----------
600 ! *PAT00S
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=%%%%%%%":N9
LET R9=1
RETURN

END

　　└ハノイの塔の最少移動手順はすでに知られて... 荒田浩二 2006/07/16 19:47:48  ツリーへ

Re: ハノイの塔　１ページ 返事を書く

荒田浩二 2006/07/16 19:47:48

ハノイの塔の最少移動手順はすでに知られていることで、
円盤がK枚の場合、最少移動回数は(K^2-1)回になります。
移動の判断となる基準は次のとおりです。
A軸の上からN枚をC軸に移動するとき、
N が奇数ならば最上段の円盤はC軸に移動する。
N が偶数ならば最上段の円盤はB軸に移動する。
これを利用すれば上手くできるのでは？

　　　└修正 荒田浩二 2006/07/16 19:54:34  ツリーへ

Re: ハノイの塔の最少移動手順はすでに知られて... 返事を書く

荒田浩二 2006/07/16 19:54:34

修正
最少移動回数は(2^K-1)回です。

　　　　└分かってます。どこかが、おかしい。できれ... 諏訪　雄治 2006/07/16 22:05:17  ツリーへ

Re: 修正 返事を書く

諏訪　雄治 2006/07/16 22:05:17

分かってます。どこかが、おかしい。できれば、
思いっきり書き直して下さい。！貴方なら出来そう。
私も、やってみます。
１５年も前に、私が、N88BASIC 上で、我流でかいたものを、
練習にと、バタバタと書き直してみましたが、再帰呼び出し部分が、
我ながら読めなくなってしまって！

Ｎ番目の円盤を、Ｓから、Ｄへ動かすには、
１つ上の、

（Ｎ－１）番目の円盤を、ＳＤでない塔へ移動すると、
Ｎ番目の円盤を、Ｓから、Ｄへ移動できる。

たったこれだけの再帰コールをするだけですが、
現状は、なぜもっともらしく、動いているのか？
もし、ご迷惑でなければ・・・

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

ハノイの塔　１ページ	返事を書く
諏訪　雄治 2006/07/16 03:39:47
!円盤は、上に乗る方が小さくなければならないルールで、 !全ての円盤を、移す問題。我流のアルゴリズムの為か !UBASIC のサンプルより、何倍も移動回数が多く劣っている。 !LOCAL 変数も使われていません。書き直し歓迎。 ! !"HANOI.BAS" !----------------------- ! ハノイの塔　2006.7.15 !----------------------- SET WINDOW 0,639,479,0 DIM KK(200),X(3),Y(3) LET SP=201 LET K=5 ! 塔の段数(1~12) 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 N9=1 FOR w=2 TO K LET N9=3N9+2 NEXT w ! final times LET YT=INT(150/K) LET XT=INT( YT/2 ) IF 10<YT THEN LET YT=10 LET S=1 LET D=3 GOSUB 600 ! PAT00S WAIT DELAY 0.5 GOSUB 100 ! MOVK00 STOP !---------- 100 ! MOVK00 IF K=<1 THEN 200 ! MOVSD LET SP=SP-1 LET KK(SP)=K LET SP=SP-1 LET KK(SP)=D LET SP=SP-1 LET KK(SP)=S ! push K,D,S LET K=K-1 GOSUB 100 ! MOVK00 GOSUB 300 ! MOVS2 SWAP S,D GOSUB 100 ! MOVK00 SWAP S,D GOSUB 400 ! MOV2D GOSUB 100 ! MOVK00 LET S=KK(SP) LET SP=SP+1 LET D=KK(SP) LET SP=SP+1 LET K=KK(SP) LET SP=SP+1 ! pop S,D,K RETURN !---------- 200 ! MOVSD IF S<D THEN PRINT "A->";K;"--------->C" ELSE PRINT "A<---------";K;"<-C" END IF 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 GOTO 500 ! PRTIME !次のページとつなぐ

Re: ハノイの塔　１ページ	返事を書く
諏訪　雄治 2006/07/16 03:40:51
!前のページとつなぐ 300 ! MOVS2 IF S<2 THEN PRINT "A->";K+1;"->B " ELSE PRINT " B<-";K+1;"<-C" END IF WAIT DELAY DL LET W=K+1 SET LINE COLOR 0 LET x1=X(S)-WXT LET y1=Y(S) LET x2=X(S)+WXT 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(2)=Y(2)-YT SET LINE COLOR 1 LET x1=X(2)-WXT LET y1=Y(2) LET x2=X(2)+WXT LET y2=Y(2)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 GOTO 500 ! PRTIME 400 ! MOV2D IF 2<D THEN PRINT " B->";K+1;"->C" ELSE PRINT "A<-";K+1;"<-B " END IF WAIT DELAY DL LET W=K+1 SET LINE COLOR 0 LET x1=X(2)-WXT LET y1=Y(2) LET x2=X(2)+WXT LET y2=Y(2)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 LET Y(2)=Y(2)+YT LET Y(D)=Y(D)-YT SET LINE COLOR 1 LET x1=X(D)-WXT LET y1=Y(D) LET x2=X(D)+WXT LET y2=Y(D)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 500 ! PRTIME 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 RETURN !---------- 600 ! PAT00S 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=%%%%%%%":N9 ! LOCATE 0,0 LET R9=1 RETURN END

Re: ハノイの塔　１ページ	返事を書く
諏訪　雄治 2006/07/16 11:19:26
!page-2 の修正。取り替える。 300 ! MOVS2 IF S<2 THEN PRINT "A->";K+1;"->B " ELSE PRINT TAB(9);"B<-";K+1;"<-C" ! tab(9)に変更。copyで" "抜ける END IF WAIT DELAY DL LET W=K+1 SET LINE COLOR 0 LET x1=X(S)-WXT LET y1=Y(S) LET x2=X(S)+WXT 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(2)=Y(2)-YT SET LINE COLOR 1 LET x1=X(2)-WXT LET y1=Y(2) LET x2=X(2)+WXT LET y2=Y(2)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 GOTO 500 ! PRTIME 400 ! MOV2D IF 2<D THEN PRINT TAB(9);"B->";K+1;"->C" ! tab(9)に変更。copyで" "抜ける ELSE PRINT "A<-";K+1;"<-B " END IF WAIT DELAY DL LET W=K+1 SET LINE COLOR 0 LET x1=X(2)-WXT LET y1=Y(2) LET x2=X(2)+WXT LET y2=Y(2)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 LET Y(2)=Y(2)+YT LET Y(D)=Y(D)-YT SET LINE COLOR 1 LET x1=X(D)-WXT LET y1=Y(D) LET x2=X(D)+WXT LET y2=Y(D)+YT-1 PLOT LINES: x1,y1;x2,y1;x2,y2;x1,y2;x1,y1 500 ! PRTIME 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 RETURN !---------- 600 ! PAT00S 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=%%%%%%%":N9 LET R9=1 RETURN END

Re: ハノイの塔　１ページ	返事を書く
荒田浩二 2006/07/16 19:47:48
ハノイの塔の最少移動手順はすでに知られていることで、円盤がK枚の場合、最少移動回数は(K^2-1)回になります。移動の判断となる基準は次のとおりです。 A軸の上からN枚をC軸に移動するとき、 N が奇数ならば最上段の円盤はC軸に移動する。 N が偶数ならば最上段の円盤はB軸に移動する。これを利用すれば上手くできるのでは？

Re: ハノイの塔の最少移動手順はすでに知られて...	返事を書く
荒田浩二 2006/07/16 19:54:34
修正最少移動回数は(2^K-1)回です。

Re: 修正	返事を書く
諏訪　雄治 2006/07/16 22:05:17
分かってます。どこかが、おかしい。できれば、思いっきり書き直して下さい。！貴方なら出来そう。私も、やってみます。１５年も前に、私が、N88BASIC 上で、我流でかいたものを、練習にと、バタバタと書き直してみましたが、再帰呼び出し部分が、我ながら読めなくなってしまって！Ｎ番目の円盤を、Ｓから、Ｄへ動かすには、１つ上の、（Ｎ－１）番目の円盤を、ＳＤでない塔へ移動すると、Ｎ番目の円盤を、Ｓから、Ｄへ移動できる。たったこれだけの再帰コールをするだけですが、現状は、なぜもっともらしく、動いているのか？もし、ご迷惑でなければ・・・