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

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

相关文章

PHP return语句的另一个作用

一直以为,return只能出现在函数中,直到看了bbPress的代码: <?php require_once('./bb-load.php'); bb_reperm...

MyEclipse常用配置图文教程

MyEclipse常用配置图文教程

  MyEclipse有很多功能,但是我们经常用到的功能其实并不是特别多,在这里将一些有用的小技巧记录下来,作为备忘录,同时也希望能够对他人有些许帮助吧。 一 工作组(working s...

dedecms防止FCK乱格式化你的代码的修改方法

默认的情况下,FCK开启了XHTML格式化的选项,因此,有些人用可视化编辑更改完整的HTML文件的时候,Head部份可能会被改得不像人样,解决办法如下: 打开 include/...

PHP的Yii框架中View视图的使用进阶

视图名 渲染视图时,可指定一个视图名或视图文件路径/别名,大多数情况下使用前者因为前者简洁灵活, 我们称用名字的视图为 视图名. 视图名可以依据以下规则到对应的视图文件路径: 视图名可省...

PHP读取XML值的代码(推荐)

用Php读取XML最简单的情况: XML文件(cy.xml)如下: 复制代码 代码如下: <?xml version=”1.0″ encoding=”gb2312″?> &l...