递归和迭代_用递归与迭代实现汉诺塔问题（PHP实现）

汉诺塔问题

汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置N个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

实现代码

点击即可即可跳转到Github程序代码

递归法 hannoRec.php

递归法的本质，就是找到最简单的小规模解，以及一个递推关系式，然后每一次更大规模的问题就去递归到小问题上来解决。

迭代法 hannoIter

迭代法，则是将问题中，求解的一系列行为动作封装起来，使用一个循环来不停的调用这个行为，并且保存好行为前后的参数状态，使之成为一个可以连续迭代的操作，进而逐步求出最后的解。

执行时间测试脚本 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>

作者：Petrick

链接：https://www.imooc.com/article/257761

来源：慕课网

本文首次发布于慕课网，转载请注明出处，谢谢合作

原文链接：https://blog.csdn.net/weixin_29384861/article/details/112712519