|
|
4本の棒のハノイの塔 最小手数
考察
初期状態を、
▲
△△ ┴ ┴ ┴
とする。
これを、△△ ▲ ┴ ┴ と移動することを考える。
上からm個の▲の移動は4-hanoi[m]となる。
続いて、
┴ ▲ ┴ △△
残り(n-m)個の△△の移動は3-hanoi[n-m]となる。
最後に、
▲
┴ ┴ ┴ △△
▲の移動は4-hanoi[m]となる。
（終わり）
参考サイト http://mathworld.wolfram.com/TowerofHanoi.html
OPTION ARITHMETIC RATIONAL
DECLARE EXTERNAL FUNCTION HANOI.H
FOR N=1 TO 50
PRINT N; H(N,4)
NEXT N
END
MODULE HANOI !n枚の板、k本の棒のハノイの塔をH(n,k)と表す
OPTION ARITHMETIC RATIONAL
SHARE NUMERIC F(1000,10)
MAT F=ZER
PUBLIC FUNCTION H
EXTERNAL FUNCTION H(N,K)
OPTION ARITHMETIC RATIONAL
IF F(N,K)>0 THEN !算出している場合
LET H=F(N,K) !restore it
ELSE
IF K=3 THEN !3本の場合、(2^n-1)回
IF N=1 THEN
LET T=1
ELSE
LET T=2*H(N-1,3)+1 !漸化式
END IF
ELSE !4本以上
IF N=1 THEN
LET T=1
ELSE
LET T=2*H(1,K)+H(N-1,K-1) !最小のもの
FOR M=2 TO N-1
LET W=2*H(M,K)+H(N-M,K-1) !m本はk-hanoi、(n-m)本は(k-1)-hanoi
IF W<T THEN LET T=W
NEXT M
END IF
END IF
LET H=T
LET F(N,K)=T !save it
END IF
END FUNCTION
END MODULE
実行結果
1 1
2 3
3 5
4 9
5 13
6 17
7 25
8 33
9 41
10 49
11 65
12 81
13 97
14 113
15 129
16 161
17 193
18 225
19 257
20 289
21 321
22 385
23 449
24 513
25 577
26 641
27 705
28 769
29 897
30 1025
31 1153
32 1281
33 1409
34 1537
35 1665
36 1793
37 2049
38 2305
39 2561
40 2817
41 3073
42 3329
43 3585
44 3841
45 4097
46 4609
47 5121
48 5633
49 6145
50 6657
|
|