Recursive algorithm implementation and iterative algorithm implementation for the Tower of Hanoi problem in PHP

This article introduces the recursive algorithm implementation and iterative algorithm implementation of the Tower of Hanoi problem in PHP. It has a certain reference value. Now I share it with you. Friends in need can refer to it

implementation Code

Program code address: https://github.com/ParrySMS/Exp/tree/master/ProLang/hannota

Recursive methodhannoRec.php

";}

Iteration methodhannoIter

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, 
"; } **/

Execution time test script 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
 
 

Reference

Iterative method ideas:https://wenku.baidu.com/view/dce79165b0717fd5360cdcdb.html

Related recommendations:

php Recursive function example analysis

PHP recursive algorithm simplification

The above is the detailed content of Recursive algorithm implementation and iterative algorithm implementation for the Tower of Hanoi problem in PHP. For more information, please follow other related articles on the PHP Chinese website!