|
漢諾塔：漢諾塔（又稱河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。 其實(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í)不然，可實(shí)施的行動(dòng)是唯一的。 ?。?）反復(fù)進(jìn)行（1）（2）操作，最后就能按規(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我用的是遞歸，代碼如下：
|
|
|
