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