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

汉诺塔问题

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

实现代码

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

递归法 hannoRec.php

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

";
}

---

迭代法 hannoIter

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

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);
 }
    }

}


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;

}

---

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

---

参考

迭代法思路