3.3 汉诺塔问题
3.3.1 “Hanoi 塔”问题
有 3 根柱子:A,B,C,现有 n 个大小不一的圆盘依半径的大小,从下而上套
在柱子 A 上,最大的圆盘放在柱子 A 的最下面。现要将所有的圆盘从柱子 A 移
动到 C 柱子上,每次只允许从一根柱子转移到另一根柱子上,且在转移过程中
不允许出现大圆盘放在小圆盘上。B 盘为可以利用的柱子,每次只允许移动一个
盘子,请问要转移多少次才能将柱子 A 上的圆盘全部转移柱子 C 上?
“Hanoi 塔”是组合数学中的著名问题之一。
3.3.2 问题求解
主程序调用:
global nmove
nmove=0;
hanta(‘A’,’B’,’C’,3)
nmove
说明:上面的程序调用表示有 3 根柱子:A ,B,C,现有 3 个盘子在 A 上,要将其
移动到 C 盘上,B 盘为可以利用的柱子。
3.3.3 实现程序
function hanta(posfrom,posmiddle,posend,numplate)
global nmove%移动次数,调用 nmove 之前声明 nmove 为全局变量,且赋值为 0
if numplate==1
sprintf('从%s 移到%s',posfrom,posend)
nmove=nmove+1;
return
end
try
hanta(posfrom,posend,posmiddle,numplate-1)
2022-02-27 13:07:53
4.06MB
数学建模
1