这篇文章介绍的内容是关于PHP汉诺塔问题的递归算法实现和迭代算法实现，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
实现代码
程序代码地址：https://github.com/parrysms/exp/tree/master/prolang/hannota
递归法 hannoRec.php
<?php/**
* Created by PhpStorm.
* User: L
* Date: 2018-4-15
* Time: 2:07
*//** 递归实现
* @param $id //盘子编号
* @param $first //起点柱子
* @param $middle //中介柱子
* @param $end //终点柱子
*/function hanRec($id, $first, $middle, $end,$counter){
if ($id == 1) {
move(1,$first,$end,$counter);
} else {
hanRec($id-1,$first,$end,$middle,$counter);
move($id,$first,$end,$counter); $counter++;
hanRec($id-1,$middle,$first,$end,$counter);
}
}function move($id,$from,$to,$counter){
global $counter; $counter++; // echo "step: $counter, level $id from $from move to $to, <br/>";}迭代法 hannoIter
<?php/**
* Created by PhpStorm.
* User: L
* Date: 2018-4-17
* Time: 2:38
*/class Params{ //定义一个对象来保存参数状态
public $id; public $num; public $first; public $middle; public $end; public $counter; /**
* Params constructor.
* @param $num
* @param $first
* @param $middle
* @param $end
* @param $counter
*/
public function __construct($id,$num, $first, $middle, $end, $counter)
{
$this->id = $id; $this->num = $num; $this->first = $first; $this->middle = $middle; $this->end = $end; $this->counter = $counter;
}
}function hanIter($id,$num, $first, $middle, $end, $counter){
$stack =init($id,$num, $first, $middle, $end, $counter); while($stack){ //出栈
$action = array_pop($stack); // var_dump($action);
if($action->num ==1){
move($action->id,$action->first,$action->end,$action->counter);
}else{ //入栈
$next_stack = init($action->id,$action->num,$action->first, $action->middle, $action->end, $action->counter); $stack=array_merge($stack,$next_stack);
}
}
}/** 入栈操作
* @param $id //需要移动的盘子
* @param $num //移动该盘子需要挪动的总盘子数量
* @param $first
* @param $middle
* @param $end
* @param $counter
* @return array
*/function init($id,$num,$first, $middle, $end, $counter){
unset($stack); //注意入站出站顺序
$stack = array(); //第一次回调
$stack[] =new Params($id-1,$num-1,$middle,$first,$end,$counter); //第二次回调
$stack[] =new Params($id,1,$first, $middle, $end, $counter); //第三次回调
$stack[] =new Params($id-1,$num-1,$first,$end,$middle,$counter); return $stack;
}/** 若在测试用例中，由于两个文件都有此 move函数，函数重名，注释掉其中一个即可
function move($id,$from,$to,$counter){
global $counter;
$counter++;
// echo "step: $counter, level $id from $from move to $to, <br/>";
}
**/执行时间测试脚本 test.php
<?php/**
* Created by PhpStorm.
* User: L
* Date: 2018-4-17
* Time: 2:18
*/require "hannoRec.php";require "hannoIter.php";
define('TIMES', 100);
define('NUM', 10);function rowTable(){
unset($row); $row = array(); for ($i = 0; $i < TIMES; $i++) { $row = getSortRow($row);
} foreach ($row as $r) { print <<< TR
<tr>
<td>$r->iter</td>
<td>$r->rec</td>
</tr>
TR;
}
}function getSortRow(array $row){
$num = NUM; $counter= 0; $stime = microtime(true);
hanIter($num, $num, 'A', 'B', 'C', $counter); $etime = microtime(true); $iterTime = 1000 * ($etime - $stime);// echo "<br/>";
$counter = 0; $num = NUM; $stime = microtime(true);
hanRec($num, 'A', 'B', 'C', $counter); $etime = microtime(true); $recTime = 1000 * ($etime - $stime); $row[] = (object)["iter" => $iterTime, "rec" => $recTime]; return $row;
}?><table border="1">
<tr>
<th>迭代 Iter/ms</th>
<th>递归 Rec/ms</th>
</tr> <?php rowTable(); ?></table>参考
迭代法思路：https://wenku.baidu.com/view/dce79165b0717fd5360cdcdb.html
相关推荐：
立即学习“PHP免费学习笔记（深入）”；
