中瑞祥解析河內(nèi)塔背景由來以及算法
背景由來
法國數(shù)學(xué)家愛德華·盧卡斯曾編寫過一個印度的古老傳說:在世界中心貝拿勒斯(在印度北部)的圣廟里,,一塊黃銅板上插著三根寶石針,。印度教的主神梵天在創(chuàng)造世界的時候,,在其中一根針上從下到上地穿好了由大到小的64片金片,,這就是所謂的漢諾塔。不論白天黑夜,,總有一個僧侶在按照下面的法則移動這些金片:一次只移動一片,,不管在哪根針上,小片必須在大片上面,。僧侶們預(yù)言,,當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時,世界就將在一聲霹靂中消滅,,而梵塔,、廟宇和眾生也都將同歸于盡。
不管這個傳說的可信度有多大,,如果考慮一下把64片金片,,由一根針上移到另一根針上,并且始終保持上小下大的順序,。這需要多少次移動呢?這里需要遞歸的方法,。假設(shè)有n片,移動次數(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時,,
算法介紹
其實算法非常簡單,,當(dāng)盤子的個數(shù)為n時,移動的次數(shù)應(yīng)等于2^n – 1(有興趣的可以自己證明試試看),。后來一位美國學(xué)者發(fā)現(xiàn)一種出人意料的簡單方法,,只要輪流進(jìn)行兩步操作就可以了。首先把三根柱子按順序排成品字型,,把所有的圓盤按從大到小的順序放在柱子A上,,根據(jù)圓盤的數(shù)量確定柱子的排放順序:若n為偶數(shù),按順時針方向依次擺放 A B C,;
若n為奇數(shù),,按順時針方向依次擺放 A C B。
⑴按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子,,即當(dāng)n為偶數(shù)時,,若圓盤1在柱子A,則把它移動到B,;若圓盤1在柱子B,,則把它移動到C;若圓盤1在柱子C,,則把它移動到A,。
⑵接著,把另外兩根柱子上可以移動的圓盤移動到新的柱子上,。即把非空柱子上的圓盤移動到空柱子上,,當(dāng)兩根柱子都非空時,移動較小的圓盤,。這一步?jīng)]有明確規(guī)定移動哪個圓盤,,你可能以為會有多種可能性,其實不然,,,。
⑶反復(fù)進(jìn)行⑴⑵操作,最后就能按規(guī)定完成漢諾塔的移動,。
所以結(jié)果非常簡單,,就是按照移動規(guī)則向一個方向移動金片:
如3階漢諾塔的移動:A→C,A→B,C→B,A→C,B→A,B→C,A→C
漢諾塔問題也是程序設(shè)計中的經(jīng)典遞歸問題,下面我們將給出遞歸和非遞歸的不同實現(xiàn)源代碼,。