ハノイの塔問題を実装するための PHP 再帰の書き方

今回は、PHPを使用してハノイの塔問題を実装する小さなケースをお届けします。

ハノイの塔 (ハノイの塔としても知られています) は、インドの古代伝説に由来する知育玩具です。ブラフマーが世界を創造したとき、1本の柱の上に64枚の金の円盤を下から上に大きさ順に積み重ねた3本のダイヤモンドの柱を作りました。ブラフマーはバラモンに、別の柱の上にある円盤を下から大きい順に並べ替えるよう命じました。また、小さな円盤では円盤を拡大することはできず、3本の柱の間で一度に移動できる円盤は1枚だけであると規定されています。つまり、A、B、C というラベルが付けられた 3 つの隣接する柱があります。柱 A には、サイズの異なる n 個のディスクが下から上にピラミッド状に積み重ねられています。すべてのディスクを 1 つずつ柱に移動する必要があります。 . B、同じ列を移動するたびに、大きなプレートが小さなプレートの上に表示されることはありません。少なくとも何回移動する必要がありますか?

再帰的な手順は次のとおりです:

1) n-1 個の円を A から C に移動

2) 残りの 1 つの円を A から B に移動
3) n-1 個の円を C から B に移動し、完了です

コードは次のとおりです:

<?php
//将所有圆盘从a移到b
function hanuota($n,$a,$b,$c){
  global $step;
  if($n==1){
    $step++;
    echo "将圆盘 $n 从 $a 柱子 到 $b 柱子 <br />";
  }else{
    hanuota($n-1,$a,$c,$b);
    $step++;
    echo "将圆盘 $n 从 $a 柱子 到 $b 柱子 <br />";
    hanuota($n-1,$c,$b,$a);
  }
}
//移动的次数
$step = 0;
hanuota(4, &#39;A&#39;, &#39;B&#39;, &#39;C&#39;);
echo "移动次数：" . $step;
?>

実行結果:

将圆盘 1 从 A 柱子 到 C 柱子
将圆盘 2 从 A 柱子 到 B 柱子
将圆盘 1 从 C 柱子 到 B 柱子
将圆盘 3 从 A 柱子 到 C 柱子
将圆盘 1 从 B 柱子 到 A 柱子
将圆盘 2 从 B 柱子 到 C 柱子
将圆盘 1 从 A 柱子 到 C 柱子
将圆盘 4 从 A 柱子 到 B 柱子
将圆盘 1 从 C 柱子 到 B 柱子
将圆盘 2 从 C 柱子 到 A 柱子
将圆盘 1 从 B 柱子 到 A 柱子
将圆盘 3 从 C 柱子 到 B 柱子
将圆盘 1 从 A 柱子 到 C 柱子
将圆盘 2 从 A 柱子 到 B 柱子
将圆盘 1 从 C 柱子 到 B 柱子
移动次数：15

これらの事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、PHP 中国語 Web サイトの他の関連記事に注目してください。 ！

関連書籍:

PHP の高トラフィックの最適化?

PHP は、Web サイトのトラフィック量と同時実行性の問題をどのように解決しますか

PHP 製品フラッシュセールのタイミングの実装 (大規模トラフィックの解決策)

以上がハノイの塔問題を実装するための PHP 再帰の書き方の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。