ハノイの塔 第５回

前回の続きです。どうやら４ペグのハノイの塔のアルゴリズムが見えてきました。

---

真ん中にある普通のハノイの塔の問題は、２枚のときに重なることがないので、これ以上改善の余地はないので、xの候補としては2～n-1まで考えれば十分ということになります。つまり、b(n)=min{x=2～n-1} (a(x)+2×b(n-x))と定式化できました。あとはxを考えるだけです。実際に計算してみます。

• n=3 : x=2, b(3)=5
• n=4 : x=2 or 3, b(4)=9
• n=5 : x=2 or 3, b(5)=13
• n=6 : x=3, b(6)=17
• n=7 : x=3 or 4, b(7)=25
• n=8 : x=3 or 4, b(8)=33
• n=9 : x=3 or 4, b(9)=41
• n=10 : x=4, b(10)=49
• n=11 : x=4 or 5, b(11)=65
• n=12 : x=4 or 5, b(12)=81
• n=13 : x=4 or 5, b(13)=97
• n=14 : x=4 or 5, b(14)=113
• n=15 : x=5, b(15)=129
• n=16 : x=5 or 6, b(16)=161
• n=17 : x=5 or 6, b(17)=193
• n=18 : x=5 or 6, b(18)=225
• n=19 : x=5 or 6, b(19)=257
• n=20 : x=5 or 6, b(20)=289
• n=21 : x=6, b(21)=321
• n=22 : x=6 or 7, b(22)=385
• n=23 : x=6 or 7, b(23)=449
• n=24 : x=6 or 7, b(24)=513
• n=25 : x=6 or 7, b(25)=577
• n=26 : x=6 or 7, b(26)=641
• n=27 : x=6 or 7, b(27)=705
• n=28 : x=7, b(28)=769
• n=29 : x=7 or 8, b(29)=897
• n=30 : x=7 or 8, b(30)=1025
• n=31 : x=7 or 8, b(31)=1153
• n=32 : x=7 or 8, b(32)=1281
• n=33 : x=7 or 8, b(33)=1409
• n=34 : x=7 or 8, b(34)=1537
• n=35 : x=7 or 8, b(35)=1665
• n=36 : x=8, b(36)=1793
• n=37 : x=8 or 9, b(37)=2049
• n=38 : x=8 or 9, b(38)=2305
• n=39 : x=8 or 9, b(39)=2561
• n=40 : x=8 or 9, b(40)=2817
• n=41 : x=8 or 9, b(41)=3073
• n=42 : x=8 or 9, b(42)=3329
• n=43 : x=8 or 9, b(43)=3585
• n=44 : x=8 or 9, b(44)=3841
• n=45 : x=9, b(45)=4097
• n=46 : x=9 or 10, b(46)=4609
• n=47 : x=9 or 10, b(47)=5121
• n=48 : x=9 or 10, b(48)=5633
• n=49 : x=9 or 10, b(49)=6145
• n=50 : x=9 or 10, b(50)=6657

気がつくことは、最適手が一つのものがところどころ存在するということです。これから、まず最適手がただ一つに定まる場合を考えてみます。

---

続きは次回に