主題

ZeroJudge - a227: 三龍杯 -> 河內之塔 解題心得

Not In My Back Yard | 2021-01-21 00:00:08

題目連結:


題目大意:
典型的河內塔(Hanoi Tower,參見維基頁面)。

已知三個柱子從左到右為 'A' 、 'B' 、 'C' ,所有的環一開始都在 'A' 柱上。現在輸入有多列,每列給定一正整數 N (N ≦ 15),代表環的個數,試問所有 'A' 柱上的環移到 'C' 的最佳步驟為何?輸出格式參見範例輸出。



範例輸入:
1
2
3


範例輸出:
Move ring 1 from A to C

Move ring 1 from A to B
Move ring 2 from A to C
Move ring 1 from B to C

Move ring 1 from A to C
Move ring 2 from A to B
Move ring 1 from C to B
Move ring 3 from A to C
Move ring 1 from B to A
Move ring 2 from B to C
Move ring 1 from A to C


解題思維:
遞迴解就不贅述了,參見題目大意給定的維基頁面之說明或是這題的前半部分。



比較少人提及的是,河內塔是有迭代解法的,作法如下:
一:計算 N 個環的河內塔最少步驟數為 K = 2 ^ N - 1;

二:如果 N 為偶數,則將 'B' 、 'C' 兩柱的角色交換(即 'B' 柱變成 'C' 柱、 'C' 柱變 'B' 柱)

三:接著用一迴圈從 0 跑到 K - 1(索引值為 i):
  1.對於 i % 3 (即 i 除以 3 取餘數)為 0 之情況,看 'A' 、 'C' 兩柱
    誰可以移動到對方就移動(保證恰好只會有一個柱的頂端環可以動);
  2.對於 i % 3 為 1 之情況,看 'A' 、 'B' 兩柱誰可以動就動;
  3.對於 i % 3 為 2 之情況,看 'B' 、 'C' 兩柱誰可以動則動。


這個想法之正確性可以從 3Blue1Brown 這個數學科普頻道的這兩部影片略見一二:




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
68 巴幣: 0

創作回應

相關創作

更多創作