Home > Article > Backend Development > How to write PHP recursion to implement the Tower of Hanoi problem
How to write PHP recursion to implement the Tower of Hanoi problem
- php中世界最好的语言Original
- 2017-12-20 16:08:311170browse
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, 'A', 'B', 'C');
echo "移动次数：" . $step;
?>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
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!