ビット演算によるパズルなどの解法

　　ビット演算によるパズルなどの解法 山中和義 2007/07/23 15:58:12 
　　├!やっぱり再帰コールした方が・・ SECOND 2007/07/23 23:24:15  (修正3回)
　　└!すみません。思いっきりイジリました。 SECOND 2007/07/25 09:59:15  (修正1回)
　　　└新ネタを探しているとき、サイトを見つけま... 山中和義 2007/07/26 07:05:21  (修正2回)
　　　　└ありがとうございました。面白いカウンター... SECOND 2007/07/26 12:56:56 
　　　　　└!これを書いた本人も、よく分かっていない。... SECOND 2007/07/27 06:21:18  (修正1回)
　　　　　　├もっと簡単に記述できるようです。 山中和義 2007/07/27 14:45:00  (修正3回)
　　　　　　│└ありがとうございます。移動元、移動先の取... SECOND 2007/07/27 23:00:20 
　　　　　　└別解 山中和義 2007/09/17 20:15:11

　　ビット演算によるパズルなどの解法 山中和義 2007/07/23 15:58:12  ツリーへ

ビット演算によるパズルなどの解法 返事を書くノートメニュー

山中和義 <drdlxujciw> 2007/07/23 15:58:12

●ハノイの塔

!※Microsoft BASIC互換モードで実行すること

DEF XOR(x,y)=(NOT x AND y) OR (x AND NOT y) !排他的論理和
DEF GrayCode(x)=XOR(x,INT(x/2)) !グレイコード　※右シフトしてXOR
DEF Bit(x,m)=MOD(INT(x/2^m),2) !mビット目を得る

LET n=4 !円盤の数

a0=GrayCode(0)
FOR i=1 TO 2^n-1 !移動回数
a=GrayCode(i) !n-1からnへ移行したとき、変化したビットを検出する
b=XOR(a,a0)
FOR j=0 TO n-1
IF Bit(b,j)=1 THEN PRINT j+1;"番目の円盤を ";
NEXT j
a0=a !次へ

a=MOD(i AND (i-1),3) !各ビットの論理積、論理和をとる
b=MOD((i OR (i-1))+1,3)

PRINT mid$("ABC",a+1,1);" から ";mid$("ABC",b+1,1);" へ移動"
NEXT i

END

円盤を番号を算出する部分は、

FOR j=0 TO n-1 !各ビットの０→１（ポジティブトリガ）を検出する
IF Bit(i-1,j)=0 THEN
IF Bit(i,j)=1 THEN PRINT j+1;"番目の円盤を ";
END IF
NEXT j

としてもよい。

●三山崩し

!※Microsoft BASIC互換モードで実行すること

DEF XOR(x,y)=(NOT x AND y) OR (x AND NOT y) !排他的論理和
DEF ToBin$(x,m)=right$(REPEAT$("0",m-1)&BSTR$(MOD(x,2^m),2),m) !mビットの２進数に変換する

OPTION BASE 1
DIM a(3)
DATA 3,5,7
MAT READ a

LET st=0
DO
LET st=MOD(st+1,2) !次へ

FOR k=1 TO 3 !状態を表示する
PRINT k;"番目の山に";a(k);"個",ToBin$(a(k),8)
NEXT k
PRINT ,ToBin$(XOR(XOR(a(1),a(2)),a(3)),8); !パリティ
PRINT " パリティビット"

IF st=0 THEN PRINT "先手" ELSE PRINT "後手"
DO
INPUT PROMPT "どの山から取りますか（1～3）":p
LOOP UNTIL p>0 AND p<4 AND a(p)>0 !石がある山を選択したら
DO
INPUT PROMPT "いくつ取りますか（1～"&STR$(a(p))&"）":q
LOOP UNTIL q>0 AND q<=a(p) !１個以上

LET a(p)=a(p)-q !石を取り除く

LOOP UNTIL (a(1) OR a(2) OR a(3))=0 !すべてなくなったら

PRINT
IF st=0 THEN PRINT "先手の勝ちです。" ELSE PRINT "後手の勝ちです。"

END

　　├!やっぱり再帰コールした方が・・ SECOND 2007/07/23 23:24:15  (修正3回) ツリーへ

Re: ビット演算によるパズルなどの解法 返事を書くノートメニュー

SECOND <cszcthjjdj> 2007/07/23 23:24:15 ** この記事は3回修正されてます

!やっぱり再帰コールした方が・・
!1,3,5,7,,枚は、Ａ→Ｃで、一致しますが、
! 2,4,6,,,枚は、Ａ→Ｂになっていませんか。

!------------
! ハノイの塔：
!　上段にいく程、より小さい円盤が、積まれている山を、Ａ塔→Ｃ塔へ移す問題。
!　空のＢ塔を使い、小さい円盤の上に大きい円盤は、乗らない規則で１枚づつ運ぶ。
!------------

! 上からＫ番目の円盤を、Ｓから、Ｄへ動かす方法。

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

! １つ上の、
!（Ｋ－１）番目までの円盤の全部を、Ｓ、Ｄ、でない塔(6-S-D)へ移動し、
! Ｋ番目の円盤を、Ｓから、Ｄへ移動する。
! 先の（Ｋ－１）番目までの円盤の全部を、Ｄの上に積んで終了。
!
!（Ｋ－１）番目の上にも、円盤が有るため、
! 再帰的に同じ処理をコールし、Ｋ＝１になる毎に
! 再帰が止まって、リターンしてくる。
!１番下の最大の円盤から、最初のコールをする。

!１枚少ない実行回数を N(k-1) とすると、N(k)= N(k-1)+1+N(k-1)= 2*N(k-1)+1
! N(1)=1 であるので、この数列 N(K) は、1,3,7,15,31,,,(2^k)-1
!----------

LET K=5 !一番下の円盤番号から開始。塔の段数、として設定。
LET S=1 !　出発塔の番号１２３→ＡＢＣ
LET D=3 !　到着塔の番号１２３→ＡＢＣ
CALL MovK00( K, S, D)

SUB MovK00( K, S, D)
IF 1<K THEN CALL MovK00( K-1, S, 6-S-D) ! 移動要求 K-1,,1層 S→ 中継の塔
PRINT K;"番目の円盤を ";mid$("ABC",S,1);" から ";mid$("ABC",D,1);" へ移動" ! 表示 K層 S →D
IF 1<K THEN CALL MovK00( K-1, 6-S-D, D) ! 移動要求 K-1,,1層中継の塔 →D
END SUB

END

　　└!すみません。思いっきりイジリました。 SECOND 2007/07/25 09:59:15  (修正1回) ツリーへ

Re: ビット演算によるパズルなどの解法 返事を書くノートメニュー

SECOND <cszcthjjdj> 2007/07/25 09:59:15 ** この記事は1回修正されてます

!すみません。思いっきりイジリました。
!ハノイの塔が、ある種のカウンターだったとは、驚きです。
!どうやって、見つけたんですか。
!何とか全部一致するように、なりましたが、
!何故なのか、未だに、よく分かりません。

!※Microsoft BASIC互換モードで実行すること。
!　(オプション→ 文法→ Microsoft BASIC 互換)

LET n=4 !円盤の数

FOR i=1 TO 2^n-1 !　移動回数
PRINT right$("0000000"+BSTR$(i,2),8);" ";

pEdge=i AND (NOT i-1) !　各ビットの０→１（ポジティブ・エッジ）を検出する

K=1+LOG(pEdge)/LOG(2) !　log( 底2 )pEdge= 右から数えたビット番号。0,1,2,3,,,
S=1+MOD(i AND (i-1), 3)
D=1+MOD( (i OR (i-1))+1, 3)

IF MOD(n,2)=0 THEN !　枚数が、2,4,6,,,の時、2(B),3(C) を交換する。
IF S=2 OR S=3 THEN S=5-S
IF D=2 OR D=3 THEN D=5-D
END IF

PRINT K;"番目の円盤を ";mid$("ABC",S,1);" から ";mid$("ABC",D,1);" へ移動"
NEXT i
END

　　　└新ネタを探しているとき、サイトを見つけま... 山中和義 2007/07/26 07:05:21  (修正2回) ツリーへ

Re: !すみません。思いっきりイジリました。 返事を書くノートメニュー

山中和義 <drdlxujciw> 2007/07/26 07:05:21 ** この記事は2回修正されてます

新ネタを探しているとき、サイトを見つけました。

自分なりに考えてみると、、、
前提として
・円盤の移動回数が2^n-1手になる。
　各手を０～2^n-1の数で表現可能。2^n進カウンタか！？

・円盤とビットの対応
　１番小さい円盤と最下位ビット、…、一番大きい円盤と最上位ビットとを対応させると
　円盤の位置パターンとビットパターンとを対応できるか！？

どのように対応させるか。。。

n番の（１番大きい）円盤に着目すれば、前半と後半に分けられる。

たとえばn=3の場合、円盤の位置パターンは、
０手目と７手目
１｜｜　｜｜１
２｜｜　｜｜２
３｜｜　｜｜３

１手目と６手目
｜｜｜　｜｜｜
２｜｜　｜｜２
３｜１　１｜３

２手目と５手目
｜｜｜　｜｜｜
｜｜｜　｜｜｜
３２１　１２３

３手目と４手目
｜｜｜　｜｜｜
｜１｜　｜１｜
３２｜　｜２３

これは間に鏡を置いた「鏡面」や、各手を「前・うしろから見る」になっている。

前半は、n枚目の円盤を移動させる「準備」になっている。
再帰呼出しのプログラムの構造からもわかると思います。

次に、手を２進表記すると
０手目　000　前半
１手目　001
２手目　010
３手目　011
---------------
４手目　100　後半
５手目　101
６手目　110
７手目　111

ビットパターンは、
０手目000　と　７手目111
１手目001　と　６手目110
２手目010　と　５手目101
３手目011　と　４手目100

ビット反転すれば同じになる。

円盤の位置パターンには対称性があり、ビットパターンと一致し、対応付けが可能。

円盤の位置は、カウンタ（フリップフロップ）の「状態」を表していることになります。

プログラムはビットパターンから
・円盤の番号を算出する
・円盤の移動先を算出する
となっています。
番号の算出は、ビットパターンを眺めているとなんとなく思いつきますが、
移動先は、こちらは難しいです。

また、円盤の数（偶数、奇数）で移動先（Ｂ、Ｃ）がかわるのは、この対応付けにより
　n番の（１番大きい）円盤が、2^(n-1)手目でどこに移動するか
で決まります。

n=1の場合
０手目
１｜｜

１手目　※Ｃの位置
｜｜１

n=2の場合
０手目
１｜｜
２｜｜

１手目
１｜｜
２｜１

２手目　※Ｂの位置
｜｜｜
｜２１

n=3の場合
０手目
１｜｜
２｜｜
３｜｜

１手目
｜｜｜
２｜｜
３｜１

２手目
｜｜｜
｜｜｜
３２１

３手目
｜｜｜
｜１｜
３２｜

４手目　※Ｃの位置
｜｜｜
｜１｜
｜２３

　　　　└ありがとうございました。面白いカウンター... SECOND 2007/07/26 12:56:56  ツリーへ

Re: 新ネタを探しているとき、サイトを見つけま... 返事を書くノートメニュー

SECOND <cszcthjjdj> 2007/07/26 12:56:56

ありがとうございました。面白いカウンターです。
偶数枚で移動先ＣがＢになる問題が解決できると、
もっとコンパクトになれるのに、残念ですね。

　　　　　└!これを書いた本人も、よく分かっていない。... SECOND 2007/07/27 06:21:18  (修正1回) ツリーへ

Re: ありがとうございました。面白いカウンター... 返事を書くノートメニュー

SECOND <cszcthjjdj> 2007/07/27 06:21:18 ** この記事は1回修正されてます

!これを書いた本人も、よく分かっていない。(^^;

!以下の複雑な論理式は、
!先の、「すみません。思いっきりイジリました。」の項で
!書いたプログラムと、内容が、全く同一なものです。
!単に、ＩＦ～ＴＨＥＮ～　の式を除き、行数を減らす工夫を
!したもので、新しさは、残念ながら、何も有りません。

!コンパクトなハノイの塔・カウンター

!※Microsoft BASIC互換モードで実行すること。
!　(オプション→ 文法→ Microsoft BASIC 互換)

LET n=4 !　円盤の数 1,2,,,

FOR i=1 TO 2^n-1 !　移動回数

K0=LOG(i AND NOT i-1)/LOG(2) !　　　　　　　　　立ち上り０→１のビット番号 0,1,2,,
S0=MOD(3-MOD(i AND i-1, 3)*(-1)^(n AND 1), 3) !　　移動元の番号 0(A) 1(B) 2(C)
D0=MOD(3-MOD((i OR i-1)+1, 3)*(-1)^(n AND 1), 3) !　移動先の番号 0(A) 1(B) 2(C)

PRINT 1+K0;"番目の円盤を ";CHR$(ORD("A")+S0);" から ";CHR$(ORD("A")+D0);" へ移動"
NEXT i
END

　　　　　　├もっと簡単に記述できるようです。 山中和義 2007/07/27 14:45:00  (修正3回) ツリーへ

Re: !これを書いた本人も、よく分かっていない。... 返事を書くノートメニュー

山中和義 <drdlxujciw> 2007/07/27 14:45:00 ** この記事は3回修正されてます

もっと簡単に記述できるようです。

ビット演算は必要ありませんので、FULL BASICではこちらがよいと思います。

!ハノイの塔

LET n=4 !円盤の数

DIM D(n) !各円盤の位置　※D(1)は最も小さく、D(n)は最も大きい
MAT D=ZER !すべてＡに位置付ける　※A=0,B=1,C=2

FOR i=1 TO 2^n-1 !移動回数

FOR m=1 TO n-1 !最下位ビットから最初に１となる位置を検出する
IF MOD(INT(i/2^(m-1)),2)=1 THEN EXIT FOR
NEXT m !※1～n-1がすべて０なら、nは１のはず
PRINT m;"番目の円盤を ";

PRINT mid$("ABC",D(m)+1,1);" から ";
LET D(m)=MOD((-1)^(m+n-1)+D(m),3) !m+n-1が偶数なら右へ、奇数なら左へ。　※Aの左はC、Cの右はA
PRINT mid$("ABC",D(m)+1,1);" へ移動"

NEXT i

END

既にご存知だと思いますが、

!ハノイの塔の数列による表現（Ａ→Ｂ）
!参考　http://bal4u.dip.jp/mt/program/archives/2005/08/nmc_1.html
!

LET n=4 !円盤の数

DIM x(n+1),b(n+1)

MAT x=ZER !円盤の位置はすべてＡの位置

LET x(n+1)=0
LET b(n+1)=0

FOR m=0 TO 2^n-1 !移動回数

LET m2$=right$(REPEAT$("0",n-1)&BSTR$(m,2),n) !mをn桁の２進数へ
FOR i=n TO 1 STEP -1
LET b(n-i+1)=VAL(mid$(m2$,i,1)) !2進数表示 b(n)b(n-1) ... b(1)
NEXT i
PRINT
PRINT m;"手目"

FOR i=n TO 1 STEP -1
LET x(i)=MOD(x(i+1)+(-1)^(n-i)*(b(i)-b(i+1)),3)
NEXT i
FOR i=1 TO n
!PRINT i;"番の円盤の位置";mid$("ABC",x(i)+1,1) !円盤iの位置
PRINT TAB(x(i)*5);i
NEXT i
NEXT m

END

　　　　　　│└ありがとうございます。移動元、移動先の取... SECOND 2007/07/27 23:00:20  ツリーへ

Re: もっと簡単に記述できるようです。 返事を書くノートメニュー

SECOND <cszcthjjdj> 2007/07/27 23:00:20

ありがとうございます。移動元、移動先の取り出しに
新しいものが、ありますね。勉強になります。

　　　　　　└別解 山中和義 2007/09/17 20:15:11  ツリーへ

Re: !これを書いた本人も、よく分かっていない。... 返事を書くノートメニュー

山中和義 <drdlxujciw> 2007/09/17 20:15:11

別解

!ハノイの塔

!※Microsoft BASIC互換モードで実行すること。
!　(オプション→ 文法→ Microsoft BASIC 互換)

LET n=4 !円盤の数

DIM D(n) !各円盤の位置　※D(1)は最も小さく、D(n)は最も大きい
MAT D=ZER !すべてＡに位置付ける　※A=0,B=1,C=2

FOR i=1 TO 2^n-1 !移動回数

x=i AND (-i) !最下位ビットから最初に１となる位置を検出する
m=LOG(x)/LOG(2)+1 !x=2^(m-1)
PRINT m;"番目の円盤を ";

PRINT mid$("ABC",D(m)+1,1);" から ";
LET D(m)=MOD((-1)^(m+n-1)+D(m),3) !m+n-1が偶数なら右へ、奇数なら左へ。　※Aの左はC、Cの右はA
PRINT mid$("ABC",D(m)+1,1);" へ移動"

NEXT i

END

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

ビット演算によるパズルなどの解法	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/23 15:58:12
●ハノイの塔 !※Microsoft BASIC互換モードで実行すること DEF XOR(x,y)=(NOT x AND y) OR (x AND NOT y) !排他的論理和 DEF GrayCode(x)=XOR(x,INT(x/2)) !グレイコード　※右シフトしてXOR DEF Bit(x,m)=MOD(INT(x/2^m),2) !mビット目を得る LET n=4 !円盤の数 a0=GrayCode(0) FOR i=1 TO 2^n-1 !移動回数 a=GrayCode(i) !n-1からnへ移行したとき、変化したビットを検出する b=XOR(a,a0) FOR j=0 TO n-1 IF Bit(b,j)=1 THEN PRINT j+1;"番目の円盤を "; NEXT j a0=a !次へ a=MOD(i AND (i-1),3) !各ビットの論理積、論理和をとる b=MOD((i OR (i-1))+1,3) PRINT mid$("ABC",a+1,1);" から ";mid$("ABC",b+1,1);" へ移動" NEXT i END 円盤を番号を算出する部分は、 FOR j=0 TO n-1 !各ビットの０→１（ポジティブトリガ）を検出する IF Bit(i-1,j)=0 THEN IF Bit(i,j)=1 THEN PRINT j+1;"番目の円盤を "; END IF NEXT j としてもよい。 ●三山崩し !※Microsoft BASIC互換モードで実行すること DEF XOR(x,y)=(NOT x AND y) OR (x AND NOT y) !排他的論理和 DEF ToBin$(x,m)=right$(REPEAT$("0",m-1)&BSTR$(MOD(x,2^m),2),m) !mビットの２進数に変換する OPTION BASE 1 DIM a(3) DATA 3,5,7 MAT READ a LET st=0 DO LET st=MOD(st+1,2) !次へ FOR k=1 TO 3 !状態を表示する PRINT k;"番目の山に";a(k);"個",ToBin$(a(k),8) NEXT k PRINT ,ToBin$(XOR(XOR(a(1),a(2)),a(3)),8); !パリティ PRINT " パリティビット" IF st=0 THEN PRINT "先手" ELSE PRINT "後手" DO INPUT PROMPT "どの山から取りますか（1～3）":p LOOP UNTIL p>0 AND p<4 AND a(p)>0 !石がある山を選択したら DO INPUT PROMPT "いくつ取りますか（1～"&STR$(a(p))&"）":q LOOP UNTIL q>0 AND q<=a(p) !１個以上 LET a(p)=a(p)-q !石を取り除く LOOP UNTIL (a(1) OR a(2) OR a(3))=0 !すべてなくなったら PRINT IF st=0 THEN PRINT "先手の勝ちです。" ELSE PRINT "後手の勝ちです。" END

Re: ビット演算によるパズルなどの解法	返事を書くノートメニュー
SECOND <cszcthjjdj> 2007/07/23 23:24:15 ** この記事は3回修正されてます
!やっぱり再帰コールした方が・・ !1,3,5,7,,枚は、Ａ→Ｃで、一致しますが、 ! 2,4,6,,,枚は、Ａ→Ｂになっていませんか。 !------------ ! ハノイの塔： !　上段にいく程、より小さい円盤が、積まれている山を、Ａ塔→Ｃ塔へ移す問題。 !　空のＢ塔を使い、小さい円盤の上に大きい円盤は、乗らない規則で１枚づつ運ぶ。 !------------ ! 上からＫ番目の円盤を、Ｓから、Ｄへ動かす方法。 ! 円盤は、上から、1,2,3,,,の番号で識別。K に代入して使用。 ! A,B,C の塔は、左から、1,2,3 で識別。S,D に代入して使用。 ! 中継する塔の番号は、(1+2+3)-S-D= 6-S-D で計算される。 ! １つ上の、 !（Ｋ－１）番目までの円盤の全部を、Ｓ、Ｄ、でない塔(6-S-D)へ移動し、 ! Ｋ番目の円盤を、Ｓから、Ｄへ移動する。 ! 先の（Ｋ－１）番目までの円盤の全部を、Ｄの上に積んで終了。 ! !（Ｋ－１）番目の上にも、円盤が有るため、 ! 再帰的に同じ処理をコールし、Ｋ＝１になる毎に ! 再帰が止まって、リターンしてくる。 !１番下の最大の円盤から、最初のコールをする。 !１枚少ない実行回数を N(k-1) とすると、N(k)= N(k-1)+1+N(k-1)= 2*N(k-1)+1 ! N(1)=1 であるので、この数列 N(K) は、1,3,7,15,31,,,(2^k)-1 !---------- LET K=5 !一番下の円盤番号から開始。塔の段数、として設定。 LET S=1 !　出発塔の番号１２３→ＡＢＣ LET D=3 !　到着塔の番号１２３→ＡＢＣ CALL MovK00( K, S, D) SUB MovK00( K, S, D) IF 1<K THEN CALL MovK00( K-1, S, 6-S-D) ! 移動要求 K-1,,1層 S→ 中継の塔 PRINT K;"番目の円盤を ";mid$("ABC",S,1);" から ";mid$("ABC",D,1);" へ移動" ! 表示 K層 S →D IF 1<K THEN CALL MovK00( K-1, 6-S-D, D) ! 移動要求 K-1,,1層中継の塔 →D END SUB END

Re: ビット演算によるパズルなどの解法	返事を書くノートメニュー
SECOND <cszcthjjdj> 2007/07/25 09:59:15 ** この記事は1回修正されてます
!すみません。思いっきりイジリました。 !ハノイの塔が、ある種のカウンターだったとは、驚きです。 !どうやって、見つけたんですか。 !何とか全部一致するように、なりましたが、 !何故なのか、未だに、よく分かりません。 !※Microsoft BASIC互換モードで実行すること。 !　(オプション→ 文法→ Microsoft BASIC 互換) LET n=4 !円盤の数 FOR i=1 TO 2^n-1 !　移動回数 PRINT right$("0000000"+BSTR$(i,2),8);" "; pEdge=i AND (NOT i-1) !　各ビットの０→１（ポジティブ・エッジ）を検出する K=1+LOG(pEdge)/LOG(2) !　log( 底2 )pEdge= 右から数えたビット番号。0,1,2,3,,, S=1+MOD(i AND (i-1), 3) D=1+MOD( (i OR (i-1))+1, 3) IF MOD(n,2)=0 THEN !　枚数が、2,4,6,,,の時、2(B),3(C) を交換する。 IF S=2 OR S=3 THEN S=5-S IF D=2 OR D=3 THEN D=5-D END IF PRINT K;"番目の円盤を ";mid$("ABC",S,1);" から ";mid$("ABC",D,1);" へ移動" NEXT i END

Re: !すみません。思いっきりイジリました。	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/26 07:05:21 ** この記事は2回修正されてます
新ネタを探しているとき、サイトを見つけました。自分なりに考えてみると、、、前提として・円盤の移動回数が2^n-1手になる。　各手を０～2^n-1の数で表現可能。2^n進カウンタか！？・円盤とビットの対応　１番小さい円盤と最下位ビット、…、一番大きい円盤と最上位ビットとを対応させると　円盤の位置パターンとビットパターンとを対応できるか！？どのように対応させるか。。。 n番の（１番大きい）円盤に着目すれば、前半と後半に分けられる。たとえばn=3の場合、円盤の位置パターンは、０手目と７手目１｜｜　｜｜１２｜｜　｜｜２３｜｜　｜｜３１手目と６手目｜｜｜　｜｜｜２｜｜　｜｜２３｜１　１｜３２手目と５手目｜｜｜　｜｜｜｜｜｜　｜｜｜３２１　１２３３手目と４手目｜｜｜　｜｜｜｜１｜　｜１｜３２｜　｜２３これは間に鏡を置いた「鏡面」や、各手を「前・うしろから見る」になっている。前半は、n枚目の円盤を移動させる「準備」になっている。再帰呼出しのプログラムの構造からもわかると思います。次に、手を２進表記すると０手目　000　前半１手目　001 ２手目　010 ３手目　011 --------------- ４手目　100　後半５手目　101 ６手目　110 ７手目　111 ビットパターンは、０手目000　と　７手目111 １手目001　と　６手目110 ２手目010　と　５手目101 ３手目011　と　４手目100 ビット反転すれば同じになる。円盤の位置パターンには対称性があり、ビットパターンと一致し、対応付けが可能。円盤の位置は、カウンタ（フリップフロップ）の「状態」を表していることになります。プログラムはビットパターンから・円盤の番号を算出する・円盤の移動先を算出するとなっています。番号の算出は、ビットパターンを眺めているとなんとなく思いつきますが、移動先は、こちらは難しいです。また、円盤の数（偶数、奇数）で移動先（Ｂ、Ｃ）がかわるのは、この対応付けにより　n番の（１番大きい）円盤が、2^(n-1)手目でどこに移動するかで決まります。 n=1の場合０手目１｜｜１手目　※Ｃの位置｜｜１ n=2の場合０手目１｜｜２｜｜１手目１｜｜２｜１２手目　※Ｂの位置｜｜｜｜２１ n=3の場合０手目１｜｜２｜｜３｜｜１手目｜｜｜２｜｜３｜１２手目｜｜｜｜｜｜３２１３手目｜｜｜｜１｜３２｜４手目　※Ｃの位置｜｜｜｜１｜｜２３

Re: 新ネタを探しているとき、サイトを見つけま...	返事を書くノートメニュー
SECOND <cszcthjjdj> 2007/07/26 12:56:56
ありがとうございました。面白いカウンターです。偶数枚で移動先ＣがＢになる問題が解決できると、もっとコンパクトになれるのに、残念ですね。

Re: ありがとうございました。面白いカウンター...	返事を書くノートメニュー
SECOND <cszcthjjdj> 2007/07/27 06:21:18 ** この記事は1回修正されてます
!これを書いた本人も、よく分かっていない。(^^; !以下の複雑な論理式は、 !先の、「すみません。思いっきりイジリました。」の項で !書いたプログラムと、内容が、全く同一なものです。 !単に、ＩＦ～ＴＨＥＮ～　の式を除き、行数を減らす工夫を !したもので、新しさは、残念ながら、何も有りません。 !コンパクトなハノイの塔・カウンター !※Microsoft BASIC互換モードで実行すること。 !　(オプション→ 文法→ Microsoft BASIC 互換) LET n=4 !　円盤の数 1,2,,, FOR i=1 TO 2^n-1 !　移動回数 K0=LOG(i AND NOT i-1)/LOG(2) !　　　　　　　　　立ち上り０→１のビット番号 0,1,2,, S0=MOD(3-MOD(i AND i-1, 3)(-1)^(n AND 1), 3) !　　移動元の番号 0(A) 1(B) 2(C) D0=MOD(3-MOD((i OR i-1)+1, 3)(-1)^(n AND 1), 3) !　移動先の番号 0(A) 1(B) 2(C) PRINT 1+K0;"番目の円盤を ";CHR$(ORD("A")+S0);" から ";CHR$(ORD("A")+D0);" へ移動" NEXT i END

Re: !これを書いた本人も、よく分かっていない。...	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/27 14:45:00 ** この記事は3回修正されてます
もっと簡単に記述できるようです。ビット演算は必要ありませんので、FULL BASICではこちらがよいと思います。 !ハノイの塔 LET n=4 !円盤の数 DIM D(n) !各円盤の位置　※D(1)は最も小さく、D(n)は最も大きい MAT D=ZER !すべてＡに位置付ける　※A=0,B=1,C=2 FOR i=1 TO 2^n-1 !移動回数 FOR m=1 TO n-1 !最下位ビットから最初に１となる位置を検出する IF MOD(INT(i/2^(m-1)),2)=1 THEN EXIT FOR NEXT m !※1～n-1がすべて０なら、nは１のはず PRINT m;"番目の円盤を "; PRINT mid$("ABC",D(m)+1,1);" から "; LET D(m)=MOD((-1)^(m+n-1)+D(m),3) !m+n-1が偶数なら右へ、奇数なら左へ。　※Aの左はC、Cの右はA PRINT mid$("ABC",D(m)+1,1);" へ移動" NEXT i END 既にご存知だと思いますが、 !ハノイの塔の数列による表現（Ａ→Ｂ） !参考　http://bal4u.dip.jp/mt/program/archives/2005/08/nmc_1.html ! LET n=4 !円盤の数 DIM x(n+1),b(n+1) MAT x=ZER !円盤の位置はすべてＡの位置 LET x(n+1)=0 LET b(n+1)=0 FOR m=0 TO 2^n-1 !移動回数 LET m2$=right$(REPEAT$("0",n-1)&BSTR$(m,2),n) !mをn桁の２進数へ FOR i=n TO 1 STEP -1 LET b(n-i+1)=VAL(mid$(m2$,i,1)) !2進数表示 b(n)b(n-1) ... b(1) NEXT i PRINT PRINT m;"手目" FOR i=n TO 1 STEP -1 LET x(i)=MOD(x(i+1)+(-1)^(n-i)(b(i)-b(i+1)),3) NEXT i FOR i=1 TO n !PRINT i;"番の円盤の位置";mid$("ABC",x(i)+1,1) !円盤iの位置 PRINT TAB(x(i)5);i NEXT i NEXT m END

Re: もっと簡単に記述できるようです。	返事を書くノートメニュー
SECOND <cszcthjjdj> 2007/07/27 23:00:20
ありがとうございます。移動元、移動先の取り出しに新しいものが、ありますね。勉強になります。

Re: !これを書いた本人も、よく分かっていない。...	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/09/17 20:15:11
別解 !ハノイの塔 !※Microsoft BASIC互換モードで実行すること。 !　(オプション→ 文法→ Microsoft BASIC 互換) LET n=4 !円盤の数 DIM D(n) !各円盤の位置　※D(1)は最も小さく、D(n)は最も大きい MAT D=ZER !すべてＡに位置付ける　※A=0,B=1,C=2 FOR i=1 TO 2^n-1 !移動回数 x=i AND (-i) !最下位ビットから最初に１となる位置を検出する m=LOG(x)/LOG(2)+1 !x=2^(m-1) PRINT m;"番目の円盤を "; PRINT mid$("ABC",D(m)+1,1);" から "; LET D(m)=MOD((-1)^(m+n-1)+D(m),3) !m+n-1が偶数なら右へ、奇数なら左へ。　※Aの左はC、Cの右はA PRINT mid$("ABC",D(m)+1,1);" へ移動" NEXT i END