|
漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。 其實(shí)算法非常簡單，當(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）按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子，即當(dāng)n為偶數(shù)時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。 ?。?）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當(dāng)兩根柱子都非空時，移動較小的圓盤。這一步?jīng)]有明確規(guī)定移動哪個圓盤，你可能以為會有多種可能性，其實(shí)不然，可實(shí)施的行動是唯一的。 ?。?）反復(fù)進(jìn)行（1）（2）操作，最后就能按規(guī)定完成漢諾塔的移動。 所以結(jié)果非常簡單，就是按照移動規(guī)則向一個方向移動金片： 如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C我用的是遞歸，代碼如下：
|
|
|
