這次帶給大家一個小案列,用PHP來實作漢諾塔問題。
漢諾塔(又稱河內塔)問題是源自印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根鑽石柱子,在一根柱子上從下往上依照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。簡而言之,有三根相鄰的柱子,標號為A,B,C,A柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤,要把所有盤子一個一個移動到柱子B上,而且每次移動同一根柱子上都不能出現大盤子在小盤子上方,請問至少需要多少次移動?
遞迴過程式如下:
1)把n-1個圓從A移到C
2)把剩下一個由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, '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
相信看了這些案例你已經掌握了方法,更多精彩請關注php中文網其它相關文章!
相關閱讀:
#以上是實作漢諾塔問題的PHP遞迴怎麼寫的詳細內容。更多資訊請關注PHP中文網其他相關文章!