中瑞祥解析河內(nèi)塔背景由來(lái)以及算法

背景由來(lái)

法國(guó)數(shù)學(xué)家愛(ài)德華·盧卡斯曾編寫過(guò)一個(gè)印度的古老傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

不管這個(gè)傳說(shuō)的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動(dòng)呢?這里需要遞歸的方法。假設(shè)有n片，移動(dòng)次數(shù)是f(n).顯然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不難證明f(n)=2^n-1。n=64時(shí)，

算法介紹

其實(shí)算法非常簡(jiǎn)單，當(dāng)盤子的個(gè)數(shù)為n時(shí)，移動(dòng)的次數(shù)應(yīng)等于2^n – 1（有興趣的可以自己證明試試看）。后來(lái)一位美國(guó)學(xué)者發(fā)現(xiàn)一種出人意料的簡(jiǎn)單方法，只要輪流進(jìn)行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據(jù)圓盤的數(shù)量確定柱子的排放順序：若n為偶數(shù)，按順時(shí)針?lè)较蛞来螖[放 A B C；

若n為奇數(shù)，按順時(shí)針?lè)较蛞来螖[放 A C B。

⑴按順時(shí)針?lè)较虬褕A盤1從現(xiàn)在的柱子移動(dòng)到下一根柱子，即當(dāng)n為偶數(shù)時(shí)，若圓盤1在柱子A，則把它移動(dòng)到B；若圓盤1在柱子B，則把它移動(dòng)到C；若圓盤1在柱子C，則把它移動(dòng)到A。

⑵接著，把另外兩根柱子上可以移動(dòng)的圓盤移動(dòng)到新的柱子上。即把非空柱子上的圓盤移動(dòng)到空柱子上，當(dāng)兩根柱子都非空時(shí)，移動(dòng)較小的圓盤。這一步?jīng)]有明確規(guī)定移動(dòng)哪個(gè)圓盤，你可能以為會(huì)有多種可能性，其實(shí)不然，。

⑶反復(fù)進(jìn)行⑴⑵操作，最后就能按規(guī)定完成漢諾塔的移動(dòng)。

所以結(jié)果非常簡(jiǎn)單，就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片：

如3階漢諾塔的移動(dòng)：A→C,A→B,C→B,A→C,B→A,B→C,A→C

漢諾塔問(wèn)題也是程序設(shè)計(jì)中的經(jīng)典遞歸問(wèn)題，下面我們將給出遞歸和非遞歸的不同實(shí)現(xiàn)源代碼。