php递归算法经典实例_汉诺塔问题递归算法c语言

全栈程序员-站长 • 2022年8月11日下午3:46 • 未分类 • 阅读 7

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

利用PHP实现汉诺塔

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。简而言之，有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动？

逻辑分析以及代码实现

<?php // 汉诺塔算法 // 实现逻辑 --> 递归 （关系可以由 n=2 比较容易想出） // 把 第 n-1 个由 A 移动到C // 把 第 n 个 由 A 移动到 B // 把 第 n-1 个由 C移动到 B function hanuota($n, $a, $b, $c) { 
     global $step; if ($n == 1) { $step++; echo " 把第 " . $n . " 个由" . $a . " 移动到 ". $b. "<br />"; } else { // 把n-1 由 A 移动到 C hanuota($n-1, $a, $c, $b); $step++; echo " 把第 " . $n . " 个由" . $a . " 移动到 ". $b. "<br />"; // 把n-1 由C 移动到 B hanuota($n-1, $c, $b, $a); } } $step = 0; hanuota(4, 'A', 'B', 'C'); 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 次