Implémentation d'un algorithme récursif et d'un 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

---

Référence

<?php/**
 * Created by PhpStorm.
 * User: L
 * Date: 2018-4-17
 * Time: 2:18
 */require "hannoRec.php";require "hannoIter.php";



define(&#39;TIMES&#39;, 100);
define(&#39;NUM&#39;, 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, &#39;A&#39;, &#39;B&#39;, &#39;C&#39;, $counter);    $etime = microtime(true);    $iterTime = 1000 * ($etime - $stime);//    echo "<br/>";
    $counter = 0;    $num = NUM;    $stime = microtime(true);
    hanRec($num, &#39;A&#39;, &#39;B&#39;, &#39;C&#39;, $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>

Idée de méthode itérative :

https://wenku.baidu.com/view/dce79165b0717fd5360cdcdb.html

Recommandations associées :

PHP récursif analyse d'exemple de fonction

Algorithme récursif PHP simplifié

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!