PHP实现的解汉诺塔问题算法示例

本文实例讲述了php实现的解汉诺塔问题算法。分享给大家供大家参考，具体如下：

问题描述：

相传在古印度圣庙中，有一种被称为汉诺塔(hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号a、b、c)，在a杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把a杆上的金盘全部移到c杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于a、b、c任一杆上。

解决思路：

(1)以c盘为中介，从a杆将1至n-1号盘移至b杆；
(2)将a杆中剩下的第n号盘移至c杆；
(3)以a杆为中介；从b杆将1至n-1号盘移至c杆。

php代码实现：

/**
 * 汉诺塔（3根柱子）
 * @param unknown $n
 * @param string $a        // 当前位置
 * @param string $b        // 中转位置
 * @param string $c        // 目标位置
 */
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')

运行结果：

a->c
a->b
c->b
a->c
b->a
b->c
a->c

思考：假如是4根柱子的汉诺塔，怎么移动效率最高？

更多关于php相关内容感兴趣的读者可查看本站专题：《php数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《php数组(array)操作技巧大全》、《php常用遍历算法与技巧总结》及《php数学运算技巧总结》

希望本文所述对大家php程序设计有所帮助。