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代码实现:
/** * 汉诺塔(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程序设计有所帮助。