Heim >Backend-Entwicklung >PHP-Tutorial >Rekursive Algorithmusimplementierung und iterative Algorithmusimplementierung für das Tower of Hanoi-Problem in PHP
Der Inhalt dieses Artikels befasst sich mit der Implementierung des rekursiven Algorithmus und des iterativen Algorithmus für das Tower of Hanoi-Problem. Jetzt kann ich ihn mit Ihnen teilen
Programmcode-Adresse: 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/>"; } **/
<?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>
Idee für iterative Methoden: https://wenku.baidu.com/view/dce79165b0717fd5360cdcdb.html
Verwandte Empfehlungen:
PHP rekursiv Funktionsbeispielanalyse
Vereinfachter rekursiver PHP-Algorithmus
Das obige ist der detaillierte Inhalt vonRekursive Algorithmusimplementierung und iterative Algorithmusimplementierung für das Tower of Hanoi-Problem in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!