over 2 years ago

0 緣起

在 Knuth 大師所編著的《具體數學》(Concrete Math,別名:水泥數學)時,第一章探討遞迴問題的時候就以河內塔的移動步數作為例子。河內塔的問題算是理解遞迴解題非常重要的一個基礎,大多數的 C/C++ 程式語言書籍講到遞迴函式的時候第一個就是提到河內塔問題(題目參考:TIOJ1355):

有三根柱子分別為 ,其中 柱上頭有 個圓盤,由上至下其大小分別為 ,現在我們每一步都可以把一個盤子從某一根柱子搬到另一根上頭,但是大盤子永遠不能疊在小盤子上頭。請問至少要多少步,才能讓所有盤子都搬到 柱上?

遞迴的概念也相當純粹:先把前 個盤子搬到 ,然後把第 個盤子搬到 ,再把前 個盤子從 搬到 。由於三根柱子除了編號不同以外,其餘功能都是等價的,我們便可以寫成以下遞迴:

void hanoi(int n, char From, char To, char Temp) {
    if (n > 1) hanoi(n-1, From, Temp, To);
    printf("Move disk %d from %c to %c\n", n, From, To);
    if (n > 1) hanoi(n-1, Temp, To, From);
}

今天讓我們來找出河內塔的一些性質,以及討論一些延伸的類似題。

1 順時針或逆時針

讓我們考慮以下的樣子:我們把三根柱子依照順時針排成三角形放在一個圓形的基座上,如果我們依照上面描述的方法,每次「順時針」或「逆時針」移動盤子,我們以 表示逆時針、並以 表示順時針,那麼對於 的情形,我們可以得到以下的序列:

類似地,我們對於每一個 ,我們可以從上面的遞迴式推得最佳解的序列

這個跟摺紙序列雖然有點不一樣,但是遞迴長相很像吧~
也就是說,掌握了這個點,我們就可以知道該怎麼遞迴直接求出第 步到底盤子是要順時針還是逆時針移動了!

2 直接找出第 步該做什麼

此外,我們也想知道到底在第 步的時候,該移動哪一個盤子。這點我們也可以透過以下表格觀察:

Step A B C 備註
0 (000) 初始狀態
1 (001)
2 (010)
3 (011)
4 (100)
5 (101)
6 (110)
7 (111)

我們可以毫無意外地發現:第 步要移動的盤子編號,恰好就是 ,也就是把 寫成二進位以後的最低有效位的 index!(我們可以利用 1+__lg(i&-i) 直接算出這個編號哈~)

練習題

後記

哈哈,實在是後記無力啊,真的很對不起,拖稿拖成這樣。我們下次見吧~

← 分而治之法(六):摺紙條問題
 
comments powered by Disqus