文档介绍：第17课汉诺塔游戏——递归
相传在古印度布拉玛婆门圣庙中的僧侣喜欢玩一种被称为汉诺塔的游戏。该游戏的装置是如图所示的一块铜板,上面有三根铜(编号A,B,C),A柱自下而上、由大到小按顺序串上64个金盘。游戏的目标是把A柱上的金盘全部移到C柱上,移动时可以借用B柱,并仍按原有顺序叠好。条件是每次只能移动一个盘,并且在每次移动时每个柱子上都不允许大盘移到小盘之上。现要求用程序来实现给出n个盘从A柱移到C柱的移动过程。
【分析】打开压缩包,
N=3时的初始状态
第一步:从A移到C
第二步:从A移到B
第三步:从C移到B
第四步:从A移到C
先考虑简单情形。如果n=3,则具体移动步骤如图17-1所示:
第五步:从B移到A
第六步:从B移到C
第七步:从A移到C
图:17-1只有三个盘的汉诺塔游戏天字第一号示意图
如图17-2所示,假设把上面的第3步,第4步,第7步抽出来就相当于n=2的情况(但第3步要调用过程mov(n-1,a,b,c),即第1、第2步; 第7步要调用过程mov(n-1,b,c,a),即第5、第6步),(把上面2个盘捆视为1个盘)。原有n个盘问题,可把n-1个盘捆在一起,同理可求解。
问题:将A柱上的n个盘移动到C柱
第1步:将A柱上的n-1个盘移动到B上(A为源柱,B为目标,C为过渡柱)
第2步:将A柱上的1个盘移动C上,不用调用过程
第3步:将B柱上的n-1个盘移动到C上(B为源柱,C为目标,A为过渡柱,记为(B,C,A)
图:17-2汉诺塔移动简化过程
所以可按n=2的移动步骤设计:
如果n=0,则退出,那结束程序否则继续往下执行。
用C柱作为协助过度,将A柱上的(n-1)个盘移动到B柱上,调用过程mov(n-1,a,b,c)。
将A柱上剩下的一个盘直接移到C柱上。
用A柱作为过渡,将B柱上的(n-1)个盘移动C柱上,调用过程mov(n-1,b,c,a)。
其中mov中的参数分别表示需移动的盘数、开始柱、终止柱与临时过渡柱,这种转换直到转入和盘数为0时才停止,因为这时已无盘可移了。
【参考程序】
Program P17_1;
var x,y,x:char;
n,k:integer;
Procedure mov(n:integer;a,c,b:char); {借用b,实现把n个盘片从a移动到c}
Begin
if n=0 then exit;
mov(n-1,a,b,c); {借用 c,实现把n-1个盘片从b移动到b}
inc(k); {统计移动的次数}
writeln(k,':form ',a,' to ',c); {输出移动的第几步及移动的方法}
mov (n-1,b,c,a); {借用a,实现把n-1个盘片从b移动到C}
end;
begin {主程序}
write('n='); readln(n);
k:=0;
x:='A'; y:='B'; Z:='C';
mov(n,x,z,y); {调用子程序,实现把n个盘片从a移动到c}
readln
end.
程序定义了把n片盘子从A柱移到C柱的过程mov(n,a,b,c),这个过程把移动分为以下三步来进行:
先调用过程mov(n-1,a