[栈](1.3)Hanoi塔
说实话刚看到这个程序的时候还不太理解题意,后边看了懒猫老师的视频,才有所理解,其实这比之前接触的回溯算法还简单很多。
我们知道,递归与栈是分不开的,在函数的执行函数中,需多次进行自我调用,与汇编程序所设计中主程序和子程序之间的链接及信息交换相类似,在高级语言编制的程序中,调用函数和被调用函数之间的链接及信息交换需要通过栈来进行。
- 若在函数A中调用了函数B,则称函数A为调用函数,称函数B为被调用函数
通常,在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需先完成3件事
- 将所有的实在参数、返回地址等信息传递给被调用函数保存
- 为被调用函数的局部变量分配存储区
- 将控制转移到被调函数的入口
,而从被调函数返回调用函数之前,系统也应该完成3件工作
- 保存被调用函数的计算结果
- 释放被调用函数的数据区
- 依照被调函数保存返回地址将控制转移到调用函数
当有多个函数构成嵌套调用,按照“后调用,先返回”的原则,上述函数之间的信息传递和控制转移必须通过栈来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为它在栈顶分配一个存储区,每当从一个函数退出时,就释放它的存储区。
我们可以通过游戏来理解,先去找一个Hanoi塔的游戏。
首先需要定义一个移动函数,这个函数用来理解移动过程,所以只需要一个输出语句即可
void move(char x, int n, char z)
{
printf("%d次第%d个圆盘从%c->%c", ++c, n, x, z);
}
x和z是柱子,n是盘子。
然后主函数内调用Hanoi函数即可。下面是完整代码:
#include<stdio.h>
#include<stdlib.h>
int c = 0;
void hanoi(int, char, char, char);
void move(char, int, char);
int main()
{
int n;
printf("请输入盘子个数:");
scanf_s("%d", &n);
hanoi(n, '1', '2', '3');
system("pause");
return 0;
}
void hanoi(int n, char x, char y, char z)
/*将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到
塔座z上,y可用作辅助塔座
搬动操作move(x,n,z)可定义为(c是初值0的全局变量,对搬动计数)
printf("%i.Move disk %i from %c to %c\n",++c,n,x,z)
*/
{
if (n == 1)
{
move(x, 1, z);//将编号为1的圆盘从x移到z
}
else
{
hanoi(n - 1, x, z, y);//将x上编号为1至n-1的圆盘移到y,z作辅助塔
move(x, n, z);//将编号为n的圆盘从x移到z
hanoi(n - 1, y, x, z);//将y上编号为1至n-1的圆盘移到z,x作辅助塔
}
}
void move(char x, int n, char z)
{
printf("%d次第%d个圆盘从%c柱->%c柱\n", ++c, n, x, z);
}
我们通过游戏来剖析下此段程序
从上述我们知道,递归函数是不断将函数场景压入栈顶,知道达到出口开始出栈,通过程序可知,函数出口条件是:N=1
我们将x,y,z栈取个代号叫1,2,3,盘子从上到下分别为
这时候n的参数为3。
我们从主函数进入:
然后调用hanoi参数,此时hanoi(3,'1','2','3')
进入到hanoi函数内,首先判断是不是函数接口,n的参数值为3,如下图所示,圆圈的地方再次进入hanoi函数
将刚刚进入的场景压入栈中,然后进入到下一个场景
又碰到hanoi函数,将场景保存起来,进入下一次递。
这时碰到出口,将第一个盘子从第一柱移动到第三柱
执行结束后,将栈顶元素退栈,返回到上一个场景,继续执行下面的程序块。
执行完移动步骤后,又碰到递归,继续调用,将当前场景压入栈中。
进入到新的函数内
执行移动后,如图所示:
此时后边已经没有语句了,退栈,回到栈顶场景。
执行move移动后如下图所示:
继续进入红框内的递归
将当前场景压入栈中,继续递归。
此时满足归的条件,移动后:
归回来,继续执行下面的代码块:
移动后:
继续递归,如下图所示:
移动后:
成功了,程序结束了没?
执行完后,消除栈顶场景,两个场景后面都没语句,这程序结束。
运行结果:
一个递归函数的运行过程类似于多个函数的嵌套调用,只是调用函数和被调函数是同一函数。
为了保证递归函数正确执行,系统需设立一个“递归工作栈”,在实际的系统中,一般都综合考虑递归调用和非递归调用统一处理,在此,我们只讨论直接递归调用的处理机制。
每一层次递归所需信息构成一个“工作记录”,其中包括所有的实在参数、所有的局部变量以及上一层的返回地址,每进入一层递归,就产生一个新的工作记录压入栈顶,每退出一层递归,就从栈顶弹出一个工作记录
上述其实少了几次的工作记录,因为一段代码块内调用了两次递归,为了方便理解,我把所有在同一层次内的内层次递归记录省略掉了。