|
|
ハノイの塔の最少移動回数を求める
! Frame-Stewart algorithm
PUBLIC NUMERIC S(64,15) !'表引き
FOR PEG=3 TO 10
PRINT "棒";PEG;"本"
FOR N=1 TO 10
PRINT N;"枚";HANOI(N,PEG);"回"
NEXT N
PRINT
NEXT PEG
!'''PRINT HANOI(64,4)
END
EXTERNAL FUNCTION LMIN(ABC(),N)
LET AMIN = ABC(0)
FOR I=1 TO N-1
IF ABC(I)<AMIN THEN
LET AMIN = ABC(I)
END IF
NEXT I
LET LMIN=AMIN
END FUNCTION
EXTERNAL FUNCTION HANOI(N,PEG)
DIM MOVES(0 TO N-1)
IF PEG<3 OR N=0 THEN
LET HANOI=0
EXIT FUNCTION
END IF
IF N=1 THEN
LET HANOI=1
EXIT FUNCTION
END IF
IF PEG=3 THEN
LET HANOI=2^N-1
EXIT FUNCTION
END IF
IF PEG>3 THEN
FOR I=1 TO N-1
IF S(N-I,PEG)=0 THEN LET L=HANOI(N-I,PEG) ELSE LET L=S(N-I,PEG)
IF S(I,PEG-1)=0 THEN LET P=HANOI(I,PEG-1) ELSE LET P=S(I,PEG-1)
LET MOVES(I-1)=2 * L + P
NEXT I
LET K=LMIN(MOVES, N-1)
LET S(N,PEG)=K
LET HANOI=K
EXIT FUNCTION
END IF
END FUNCTION
インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、3本のダイヤモンドの柱が立てられている。
そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている。
そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。
以上はフランスの数学者エドゥアール・リュカによる作り話です。
https://ja.wikipedia.org/wiki/ハノイの塔
64枚の円盤を移動させるには、最低でも
2^64-1回 = 18446744073709551615回
かかり、1枚移動させるのに1秒かかったとすると、約5845億年かかる
もし、これが棒4本だったら?
円盤64枚でも4本だと移動回数は18433回となり、世界はわずか5時間程で終焉を迎えてしまう。
※英語圏ではハノイの塔は棒ではなく、peg(杭)というようだ。
|
|