iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 21
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 21

【從面試題學邏輯-21】如何邊吃甜甜圈邊理解河內塔程式的遞迴概念?(CTCI 8.6 河內塔)

「今天不寫扣(Code)」/images/emoticon/emoticon06.gif

但為什麼?
其實個人一直覺得理解河內塔的情況分兩種:

  1. 一點就通
  2. 十點沒通

還是那句:為什麼?

因為遞迴本身其實就有點抽象了,套用到河內塔上,而沒有玩過河內塔(或是玩不起來),就會超級抽象。而河內塔的程式個人覺得不會太難,主要是「理解」要怎麼寫出來的邏輯比較困難,所以今天會專注在講邏輯上。

當然能不能講解得清楚也的確讓自己很擔心就是……大挑戰捏/images/emoticon/emoticon10.gif

認識河內塔

河內塔規則基本上是這樣:

  1. 有三根柱子,其中一根柱子上套了n個中間有洞的圓盤(下面叫他甜甜圈吧!)
  2. 甜甜圈上至下依序由小到大
  3. 大的甜甜圈不可以放在小的甜甜圈之上
  4. 一次只能拿一個甜甜圈,放下後才可以拿另一個
  5. 目標是把所有甜甜圈搬到另一根柱子上


所以理論上不會出現上面這種情況

解析河內塔


下面我們用原柱、其他柱、目標柱來代稱這三根柱子

  • 原柱:原本放甜甜圈的柱子
  • 目標柱:甜甜圈要移過去的柱子
  • 其他柱:暫時放甜甜圈用的柱子,因為他不是原柱也不是目標柱

接著我們一一從最底層開始吧!

n=1

我們先假設n=1(1個甜甜圈)的情況,這個情況下,原柱的甜甜圈只有1個,沒有任何阻礙,我們就直接把它拿到目標柱就解決了。

夠直覺吧?那這個就是遞迴中的終止條件了,因為它完全不用做其他事,直接拿過去就好了。

n=2

好,問題來了,我們要把2個甜甜圈從原柱搬到目標柱,但我們不能直接把大的甜甜圈拿起來放到目標柱,這時該怎麼辦?

依照河內塔的規則,我們應該要先把上面那個甜甜圈暫時拿到其他柱,接著就能把大甜甜圈拿去目標柱了對吧?接著再把暫時放到其他柱的甜甜圈放到大甜甜圈上

順序就是:

  1. 把上面的小甜甜圈拿到其他柱
  2. 把下面的大甜甜圈拿到目標柱
  3. 把其他柱上的小甜甜圈拿到目標柱

嗯~聽起來好像很合理,好像就是把上面的甜甜圈暫時移走,把下面的甜甜圈拿到目標,再把原本的甜甜圈拿到目標去對吧?

讓我們再往下看一個例子

n=3

我們從最下面開始看吧,甜甜圈有大、中、小,如果要搬大甜甜圈到目標柱怎麼辦?
是不是要先把上面的中、小甜甜圈先搬到其他柱,再把大甜甜圈移到目標柱,對吧?
而中、小甜甜圈不能暫時放在目標柱上,不然大甜甜圈無法移動到目標柱上(聽起來是廢話,但記得要想到這點)

所以理論上要先像上面這樣,把大甜甜圈上面的東西搬到其他柱對吧?

好,我們問題往下走,暫時不看大甜甜圈,要怎麼把中、小甜甜圈搬到其他柱?

好像……有點眼熟诶?那不就是n=2的情況嗎?只是目標柱在中間而已!

所以n=3會包含n=2的情況,而n=2搬動甜甜圈其實也包含n=1的情況,這邊就有遞迴的邏輯了!

所以說:

  1. n=1直接搬,上面沒甜甜圈(終止條件)
  2. n=2之中要做n=1的情況,只是柱子順序不同
  3. n=3之中要做n=2的情況,只是柱子順序不同
  4. 以此類推

程式邏輯

用pseudo code來簡單帶一下吧:

我們應該要有個搬河內塔的方法,他應該要收這些東西:

搬河內塔(層數, 原柱, 目標柱, 其他柱);

會長這樣子

搬河內塔(層數, A, B, C){
    if(層數==1){
        搬甜甜圈(A, B);
    } else {
        搬河內塔(層數-1, A, C, B);
        // 暫時把上面的東西搬到其他柱的C
        搬甜甜圈(A, B);
        // 把大甜甜圈搬到目標柱的B
        搬河內塔(層數-1, C, B, A);
        // 注意:因為東西先暫時搬到C,所以要把C上的東西搬到B
    }
}

然後他應該要照上面的邏輯進行

還是不懂怎麼辦?

個人建議是找一個河內塔的遊戲,照著我們上面的範例,一步一步走,慢慢去了解這個概念。

當然上面並不是最完整、有效率的pseudo code,只是示範起見。但了解概念之後,實際去實作就相對沒那麼困難了。


上一篇
【從面試題學邏輯-20】你玩過小朋友下樓梯,那有玩過小朋友上樓梯嗎?(CTCI 8.1 小朋友上樓梯)
下一篇
【從面試題學邏輯-22】如何邊拉著狗狗跑步邊刪Node?(leetcode 19. Remove Nth Node From End of List )
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言