欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-28 22:56:42
本文实例讲述了php实现的解汉诺塔问题算法。分享给大家供大家参考,具体如下: 问题描述: 相传在古印度圣庙中,有一种被称为汉诺塔(hanoi)的游戏。该游戏是在一块铜板...

本文实例讲述了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实现的解汉诺塔问题算法示例

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程序设计有所帮助。