汉诺塔游戏递归.docx
《汉诺塔游戏递归.docx》由会员分享，可在线阅读，更多相关《汉诺塔游戏递归.docx（15页珍藏版）》请在冰点文库上搜索。
汉诺塔游戏递归
第17课汉诺塔游戏——递归
相传在古印度布拉玛婆门圣庙中的僧侣喜欢玩一种被称为汉诺塔的游戏。
该游戏的装置是如图所示的一块铜板，上面有三根铜（编号A，B，C），A柱自下而上、由大到小按顺序串上64个金盘。
游戏的目标是把A柱上的金盘全部移到C柱上，移动时可以借用B柱，并仍按原有顺序叠好。
条件是每次只能移动一个盘，并且在每次移动时每个柱子上都不允许大盘移到小盘之上。
现要求用程序来实现给出n个盘从A柱移到C柱的移动过程。
【分析】打开压缩包，运行里面的程序HANOI.EXE
先考虑简单情形。
如果n=3,则具体移动步骤如图17-1所示：
图：
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个盘捆在一起，同理可求解。
图：
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时才停止，因为这时已无盘可移了。
【参考程序】
ProgramP17_1;
varx,y,x:
char;
n,k:
integer;
Proceduremov（n:
integer;a,c,b:
char）;{借用b,实现把n个盘片从a移动到c}
Begin
ifn=0thenexit;
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）,这个过程把移动分为以下三步来进行：
（1）先调用过程mov（n-1,a,b,c）,把（n-1）片从A柱移到B柱，C柱作为过渡柱;
（2）直接执行writeln（k,':
form',a,'to',c），把A柱上剩下的一片直接移到C柱上;
（3）调用mov（n-1,b,c,a），把B柱上的（n-1）片从B移到C柱上，A柱是过渡柱。
对于B柱上的（n-1）片如何移动，仍然调用上述的三步，只是把（n-1）当成n，每调用一次，要移动目标柱上的片数n就减少了一片，直到减少到n=0时就退出，不再调用。
调试过程视频演示
【及时充电】
●递归——上面程序中，采用了程序设计中的一种重要的算法，即递归算法。
简单地说，递归就是编写这样的一个特殊的过程或函数，该过程体或函数体中有一个语句用于调用过程自身（称为递归调用）。
函数或过程直接调用其自身，称为直接递归;函数或过程间接调用其自身，称为间接递归。
如图17-3所示：
（a）直接递归（b）间接递归
图17-3递归的两种形式
使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题来求解，最终达到对原问题的求解。
【探索奥秘】
〖例1〗阶乘函数定义（n!
）描述如下:
1
fac（n）=
n×fac（n-1）（当n>0）
请编程实现从键盘输入n（n
10）值，通过调用函数求f（n）的值。
〖分析〗
读入n值，根据数学知识，1!
=1，正整数n的阶乘为：
n×（n-1）×（n-2）×…×2×1,该阶乘序列可转换为求n×（n-1）!
而（n-1）!
以可转换为（n-1）×（n-2）!
……，直至转换为2×1!
，而1!
=1。
〖参考程序一〗
ProgramP17_2;
varn:
byte;
functionfac（n:
byte）:
longint;
begin
ifn=1thenfac:
=1{当n=1时，函数值为1}
elsefac:
=n*fac（n-1）;{当n>1时，函数值为n*fac（n-1）,调用自身}
end;
begin{主程序}
write（'N='）;readln（n）;
writeln（'N!
',fac（n））;
end.
在子程序fac中，当n>1时，又调用函数fac,参数为n-1,…,这种操作一直持续到n=1为止。
例如当n=5时，fac（5）的值变为5*fac（4）,求fac（4）又变为4*fac（3）……,当n=1时递归停止，逐步返回到第一次调用的初始处，返回结果5*4*3*2*1,即5!
。
如图17-4所示就是求f（5）的递归调用过程。
n
fac（n）
fac（n）
5
n*fac（n-1）
5*fac（4）
5*fac（4）
20
4（n-1）
4*fac（3）
4*fac（3）
24
3
3*fac
（2）
3*fac
（2）
6
2
2*fac
（1）
2*fac
（1）
2
1
1
1
1
先把因数推向极值1，然后再逐层退回来利用关系n*fac（n-1）得到最后结果
图17-4递归调用的过程
从图17-4中可以看出，递归过程的执行总是一个过程体执行完，就带着本次执行的结果又进入另一轮过程执行。
如此反复，不断深入。
直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入。
而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体，执行其余的部分。
如此反复，直到回到起始位置上，才最终结束整个递归过程执行，得到相应的执行结果。
图17-4中左边部分表明了由于递归调用不断产生新的局部变量是保存在一个栈中，这些变量虽然同名，但各自独立，在逐层返回的过程中又是不断地从栈顶取出，直到取完。
采用递归算法来编程，程序结构简洁，它能使一个蕴涵递归关系且结构复杂的程序简洁精练，增加可读性。
但递归过程的实现决定了递归算法的效率往往很低，费时和费内存空间。
如在汉诺塔游戏中，按照移动原则，将n个盘从A杆移动到C杆需要移动盘的次数是2的n次幂减1,那么64个盘移动次数就是18446744073709511645,近19亿亿次。
这是一个天文数字，即使一台功能很强的现代计算机来解汉诺栽塔问题，恐怕也需要很长的时间，因此要想得到结果，在运行程序时，输入的n可不能太大。
据说布拉玛婆罗门圣庙的僧侣声称，汉诺塔游戏结束就标志着世界末日的到来，现在看来确实是有道理的。
因为如果每秒移动一次，64个盘则大约需近5800亿年，而据科学家以能源角度推算，太阳系的寿命只不过150亿年而已。
所以在实际编程中，如果能使用递推法解决的，应尽量用递推法，其效率更高些。
用递推法求解上面阶乘函数的思路是：
先求fac
（1）,再求fac
（2）,…直到求出fac（n）。
〖参考程序二〗
programP17_3;
varn:
integer;
functionfac（n:
integer）:
longint;
vari:
integer;m:
longint;
begin
m:
=1;
fori:
=1tondom:
=m*I;
fac:
=m;
end;
begin{主程序}
write（'n='）;readln（n）;
writeln（'fac（',n,'）=',fac（n）:
6:
2）;
end.
〖例2〗输入一个字符串，最后以“#”结束，再按逆序输出来。
〖分析〗读入一个字符，判断是否为"#"号，如果不是就继续读入，即可以调用程序本身。
如果是“#”，则输出字符
〖参考程序〗
programP17_4;
procedurerever;
varc:
char;
begin
read（c）;
ifc<>'#'thenrever;{递归调用的地方，下一次调用会分配新单元c}
write（c）;{输出c,则会逐层栈中的Cr值}
end;
begin
rever;{调用子程序}
end.
典型的栈操作
〖例3〗用递归算法求xn。
〖分析〗我们可以：
把xn分解成：
x0=1（n=0）
x1=x*x0（n=1）
x2=x*x1（n>1）
x3=x*x1（n>1）
……
xn=x*xn-1（n>1）
因此当n>1时，将xn转化为x*xn-1，其中求xn-1又用求xn的方法进行求解。
（1）定义过程xn（x,n:
integer）求xn;如果n>1则递归调用xn（a,n-1）求xn-1。
（2）当递归调用到达n=0，就执行tt:
=1,然后执行本“层”的后继语句。
（3）遇到过程的end就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:
=tt*x.
（4）继续执行步骤（3），从调用中逐“层”返回，最后返回到主程序，输出tt的值。
〖参考程序〗
programp17_5;
vartt,a,b:
integer;
provedurexn（x,n:
integer）;
begin
ifn=0thentt:
=1
elsebegin
xn（x,n-1）;{递归调用过xn（x,n-1）求纪-1}
tt:
=tt*x;
end;
end;
begin{主程序}
write{'inputx,n:
'}
readln（a,b）;{输入a，b}
xn（a,b）;{主程序调用过程xn（a,b）求ab}
writeln（a,'^',b,'=',tt）;
end.
〖例4〗要求找出具有下列性质的数的个数（包含输入的自然数n）;先输入一个自然数n（n<50）,然后对此自然数按照如下方法进行处理：
（1）不作任何处理。
（2）在它的左边加上一个自然数，但该自然数不能超过原数的一半。
（3）加上数后，继续按些规则进行处理，䞠到不能再加自然数为止。
输入
输出
6
6
6
16
26
126
36
136
〖分析〗
（1）这道题只要求出满足条件的数的个数，在n值不大的情况下用递归求解比较方便，因为它本身题目的条件就是递归定义的。
（2）目前可加的数x为1～[n/2]。
（3）当前加上了x时，这时x前面根据题意也可以加上1～[n/2]，这是一个不断递归调用本身的过程。
（4）直到x=0，则不能再加任何数了，结束递归。
〖参考程序〗
programP17_6;
varn,i:
integer;
s:
real;
procedureqiu（x:
integer）;{递归的过程}
vark:
integer;
begin
ifx<>0then{当x为零时结束递归调用}
begin
s:
=s+1;{累加统计个数}
fork:
=1toxdiv2doqiu（k）{递归调用本身}
end
end;
begin{主程序}
real（n）;
s:
=0;{s清零，用来统计满足条件的个数}
qiu（n）;{调用子程序}
writeln（s:
2:
0）
end.
展示实力
万炽洋的程序：
1、某人写了n封信和n个信封，结果所有信都装错信封。
求所有的信都装错信封共有多少种不同的情况。
2、楼梯有n阶台阶，上楼可以一步上一阶，也可以一步上二阶。
请用递归方法编程计算共有多少种不同的走法。
3、用递归方法方法完成：
有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第三张牌开始，凡是3的倍数位置上的牌以，正面朝上的翻成正面朝下，正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，从此类推，直到第一张要翻的牌超过52为止。
统计最后有几张牌正面朝上，以及它们的位置号。
4、用递归方法来实现：
在不改变字符串的内容的情况下，将字符串S中的字符逆序输出。
如s='abcd',则输出dcba.
5、有n个硬币（n为偶数）正面朝上排成一排，每次将n-1个硬币翻成朝上为止。
编程让计算机把悉硬币的最简过程及翻币次数打印出来（用*代表正面，用0代表反面）。
6、阿克曼（ackmann）函数a（x,y）中，x,y定义域是非负整数，函数值定义为：
a（x,y）=y+1（x=0）
a（x,0）=a（x-1,1）（x>0,y=0）
a（x,y）=a（x-1,a（x,y-1））（x,y>0）
设计一个递归程序求阿克曼（ackmann）函数的值。
7、如图17-5所示，输入N，请打印出0~N（0≤N≤9）的所有路径：
图17-5
8、键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。
注意输入a+b时不能输出b+a。
表达式以字符串输入，长度不超过255。
输入不要判错。
所有变量为单个小写字母。
只是要求去掉所有多余括号，不要求对表达式化简。
输入
输出
a+（b+c）
a+b+c
（a*b）+c/d
a*b+c/d
a+b/（c-d）
a+b/（c-d）
升级会员 