河內塔?這不是入門級的演算法嗎?當然,這幾乎是每個程式人接觸遞迴時的必練之題,當初你是自行解出河內塔的嗎?如果不是的話,現在先別在網路搜尋解法,試著自行解解看,然後再來看看各種河內塔,你是否也解得出來呢?

雙色、三色河內塔

基本的河內塔,只有盤子大小之別,現在加點料,若有三種尺寸盤子,而每種尺寸的盤子有兩種顏色,例如藍與黃,現在於左柱上,依尺寸從下到上,依大藍、大黃、中藍、中黃、小藍、小黃堆疊,搬運盤子的目標,是讓黃色盤子全部位於中柱,而藍色盤子位於右柱,而且,搬運過程必須遵守大盤在小盤之下的規則,顏色順序則無限制。

如果你能自行解出單色河內塔,之後,面對雙色河內塔的第一個想法就是,先處理一種尺寸、兩色盤子時的狀況,這時,從左到中移動盤子,然後,從左到右移動另一盤,不過,接下來才是陷阱,你以為n種尺寸時,只要以n-1來遞迴呼叫同一函式,就可以解決問題,結果,卻會發生大盤開始凌駕於小盤之上的情況。

其實,真正要先解決的是,如何把左柱的盤子全部移到右柱。只有一種尺寸、兩色盤子時,移動順序是左至中、左至右、中至右(跟上頭相比,多了一次移動),而有n種尺寸時,只要以n-1及不同的來源、目標柱,遞迴呼叫同一函式,也就是解決n-1種尺寸移動後,移動最底層盤子,由於是雙色,遞迴與底盤處理會必須進行四次,才能將盤子全數移至右柱。

前面的過程會是一個函式,接下來,才是處理真正的雙色河內塔問題,這會是另一個函式。如果處理n種尺寸,那就用之前的函式,將n-1個盤子全部搬到右柱,將底盤從左柱搬至中柱,接著,將n-1個盤子又全部搬到中柱,將底盤從左柱搬至右柱,然後,將n-1個盤子全部搬到左柱,這時底盤處理完成,狀態就如同處理n-1種尺寸的雙色河內塔了,放心地呼叫目前的同一遞迴函式吧!

如果是三色河內塔呢?

同樣地,可以有一個函式,負責將左柱的盤子全部移到右柱,這時才能在另一個函式中,專心地處理最底層盤子的移動,雙色河內塔與三色河內塔非常適合用來體會遞迴威力,只要正確識別出同性質的子任務,告訴電腦子任務是什麼,剩下的處理細節就讓電腦去傷腦筋吧!(雙色與三色河內塔的實際程式碼,可參考https://goo.gl/l48wg5

不遞迴的河內塔

如果我告訴你,遞迴是個很可愛的東西,你多半會不同意,遞迴只應天上有嘛!

但如果不覺得遞迴可愛,那多半是把自己當成電腦在想問題了,既然如此,那就當徹底一點,完全不使用遞迴來解河內塔如何?

先試著不使用遞迴來處理單色河內塔,如果是n個盤,可以直接把最上面的盤搬到右柱,就當成是最上層的盤處理完畢了嗎?

不行!因為這必然造成之後大盤凌駕於小盤之上。因此,你需要暫時將目前狀態放到一個袋子,並在上頭標號,然後變換目標柱,該動作必須持續到能把最下面的盤搬到目標柱為止,這時會有n-1有編號的袋子,從最後一個袋子中取出盤子狀態,將盤子移至目標柱,接下來,又得將盤子狀態放到另一個袋子裏了……

知道嗎?袋子就是在模擬電腦進行遞迴呼叫時,函式的狀態堆疊,如果函式中只遞迴呼叫自身一次,使用堆疊來模擬遞迴過程的話,基本上需要一個堆疊,單色河內塔遞迴解會在函式中,呼叫自身兩次,這需要兩個堆疊,把自己當成電腦來思考的話,就得小心堆疊中狀態的儲存與取出順序,才能正確地解決問題,無疑地,這是個繁瑣的過程(解題程式碼可參考https://goo.gl/buV8zZ)。

使用遞迴思考時的一個重要原則是,在子任務進行時,不該去思考父任務的狀態。

也就是,單看子任務本身時,每次都要是個全新任務,不會覺得有父任務的存在,這時,遞迴就會單純而可愛,如果實作遞迴時,開始感到複雜,那會是一個訊號,因為,你會不會是又開始在想著父任務狀態為何了呢?

那麼,有興趣挑戰非遞迴、使用堆疊模擬,來解出雙色或多色河內塔嗎?

如果想知道函式呼叫的堆疊是怎麼動作的話,儘管去試試看吧!不過,我完全不想挑戰,單色河內塔的堆疊模擬版本,已經足夠讓我知道電腦是怎麼處理函式堆疊了。

不堆疊的河內塔

當然,有些情況下,遞迴處理不是萬靈丹,通常相對來說,耗費的資源比較多,像是堆疊本身就需耗費記憶體,許多語言也會限制遞迴次數;有時為了效率,也必須試著找出其他方式來解題,或者試著記錄任務之間的狀態。例如,動態規畫演算時,為了避免子任務的重複計算,必須記錄子任務的最佳解,以便有效率地解決問題(記錄子任務狀態會比較適合,可以的話,儘量避免記錄父任務狀態,以免程式變得更複雜)。

以河內塔來說,存在不遞迴亦不使用堆疊模擬的解法,這來自於觀察遞迴版本的兩次遞迴呼叫間,會有一次將盤子從當次的左柱移至右柱的動作,這是一個節點,而前後兩次遞迴,會分別是個可展開的子樹,或者無法展開時,各是一個末端節點。簡單來說,將整個遞迴過程依此繪出,會是一棵二元樹,而搬運過程,就是走訪左樹、印出目前節點、走訪右樹的過程。

依上所述,若在每個節點記錄盤子編號、從幾號柱移至幾號柱,然後建出二元樹並走訪,就可獲得解答。

不過,談到二元樹的建立與走訪,使用遞迴來實作,還是比較方便的,若不想使用遞迴,程式實作的複雜度就又會加深了,有沒有辦法觀察到進一步的規律以簡化實作呢?

如果試著畫出二元樹並觀察走訪順序,當n為4時,移動的盤子編號順序,會是:1、2、1、3、1、2、1、4、1、2、1、3、1、2、1,數字左右對稱,感覺具有規律性,就結論而言,如果用二進位寫出這些數字,會發現相鄰數字間只有一個位元不同,這符合格雷碼(Gray code)的定義,只要能實作出產生這種格雷碼的產生(格雷碼不只一種),就能得到盤子的移動順序。

接著,我們觀察來源與目標柱。如果將柱子編號為1、2、3,並逆時針依序排列柱子,會發現如果某末端節點移動盤子時,是逆時針往下個柱子的話,該某層也都會是逆時針,而父節點該層,就都會是順時針往下個柱子,n個盤子就會有n層,n為偶數時,就是逆時針,奇數就是順時針。再接下來,就是將這些規律都實作出來了(可以參考https://goo.gl/bF4rDB)。

逐步觀察子任務

必須誠實地說,移動的盤子編號規律,讓我想破了頭,而它會是一種格雷碼,是從《名題精選百則/使用C語言》中得知的。因此,有時還是得從他人經驗中學習,對吧!

無論如何,程式的複雜性是增加了,不過因為子任務明確,相對於使用堆疊模擬的版本,還是很容易理解。這是因為,我們仍是基於有規則的遞迴版本,來進一步發掘出更細部的子任務,然而,如果是從電腦的角度來出發,那麼,大概很難察覺到這種可能性。

試著逐步觀察子任務,減少用電腦的角度來思考(儘管某些場合仍是必要的)。如果需要思考效率問題,可能性往往存在於已觀察到的規律中,就算最後某個子任務還是會用到遞迴,也沒關係,那也只是最後的實作形式罷了!

作者簡介


Advertisement

更多 iThome相關內容