How to write PHP recursion to implement the Tower of Hanoi problem

php中世界最好的语言
Release: 2023-03-18 07:18:02
Original
1184 people have browsed it

This time I will bring you a small case, using PHP to implement the Tower of Hanoi problem.

The Tower of Hanoi (also known as the Tower of Hanoi) is an educational toy derived from an ancient legend in India. When Brahma created the world, he made three diamond pillars. On one pillar, 64 gold discs were stacked in order of size from bottom to top. Brahma ordered the Brahmin to rearrange the disks on another pillar in order of size from the bottom. It is also stipulated that the disk cannot be enlarged on the small disk, and only one disk can be moved between the three pillars at a time. In short, there are three adjacent pillars, labeled A, B, and C. On pillar A, n discs of different sizes are stacked in a pyramid shape from bottom to top. All the discs need to be moved to the pillar one by one. B, and every time you move the same column, the big plate cannot appear above the small plate. How many moves are needed at least?

RecursionThe procedure is as follows:

1) Move n-1 circles from A to C
2) Move the remaining one from A to B
3) Move n-1 items from C to B, and complete the

code as follows:

<?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;
?>
Copy after login


Run result:

将圆盘 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
Copy after login


I believe you have mastered the methods after reading these cases. For more exciting information, please pay attention to other related articles on the php Chinese website!

Related reading:

PHP large traffic optimization?

How does PHP solve the problem of large website traffic and high concurrency

PHP product flash sale timing implementation (solution to large traffic)

The above is the detailed content of How to write PHP recursion to implement the Tower of Hanoi problem. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template