这篇文章介绍的内容是关于PHP汉诺塔问题的递归算法实现和迭代算法实现，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
实现代码
程序代码地址：https://github.com/parrysms/exp/tree/master/prolang/hannota
递归法 hannoRec.php
";}
迭代法 hannoIter
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,
";
}
**/执行时间测试脚本 test.php
$r->iter
$r->rec
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 "
";
$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;
}?>| 迭代 Iter/ms | 递归 Rec/ms |
|---|
参考
迭代法思路：https://wenku.baidu.com/view/dce79165b0717fd5360cdcdb.html
相关推荐：
立即学习“PHP免费学习笔记（深入）”；
