Maison >développement back-end >tutoriel php >Implémentation d'algorithme récursif et implémentation d'algorithme itératif pour le problème de la Tour de Hanoï en PHP
Le contenu de cet article concerne l'implémentation d'un algorithme récursif et d'un algorithme itératif pour le problème de la Tour de Hanoï en PHP. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer. 🎜>Code d'implémentation
Adresse du code du programme : https://github.com/ParrySMS/Exp/tree/master/ProLang/hannota
Méthode récursive
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/>";}Méthode itérative
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/>"; } **/Script de test de temps d'exécution 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>
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!