PHP實現(xiàn)的解漢諾塔問題算法示例

本文實例講述了PHP實現(xiàn)的解漢諾塔問題算法。分享給大家供大家參考，具體如下：

問題描述：

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤(如下圖)。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

解決思路：

(1)以C盤為中介，從A桿將1至n-1號盤移至B桿；
(2)將A桿中剩下的第n號盤移至C桿；
(3)以A桿為中介；從B桿將1至n-1號盤移至C桿。

PHP代碼實現(xiàn)：

/**
 * 漢諾塔（3根柱子）
 * @param unknown $n
 * @param string $a        // 當(dāng)前位置
 * @param string $b        // 中轉(zhuǎn)位置
 * @param string $c        // 目標(biāo)位置
 */
function hanoi($n,$a='A',$b='B',$c='C'){
  if( $n==1 ){
    echo "{$a}->{$c} br/>";
  }else{
    hanoi($n-1,$a,$c,$b);    // 將最大盤上的盤子，借助C柱，全部移動到B柱上
    echo "{$a}->{$c} br/>";  // 將最大盤直接從A柱移到C柱
    hanoi($n-1,$b,$a,$c);    // 再將B柱上的盤子，借助A柱，全部移到C柱
  }
}
//測試：
hanoi(3,$a='A',$b='B',$c='C')

運行結(jié)果：

A->C
A->B
C->B
A->C
B->A
B->C
A->C

思考：假如是4根柱子的漢諾塔，怎么移動效率最高？

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運算技巧總結(jié)》

希望本文所述對大家PHP程序設(shè)計有所幫助。