Home>Article>Backend Development> Implementation of recursive algorithm and iterative algorithm for Tower of Hanoi problem in PHP

Implementation of recursive algorithm and iterative algorithm for Tower of Hanoi problem in PHP

不言
不言 Original
2018-04-17 14:07:57 1620browse

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 Implementation of recursive algorithm and iterative algorithm for Tower of Hanoi problem in PHP. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn