[栈](1.3)Hanoi塔

说实话刚看到这个程序的时候还不太理解题意,后边看了懒猫老师的视频,才有所理解,其实这比之前接触的回溯算法还简单很多。

我们知道,递归与栈是分不开的,在函数的执行函数中,需多次进行自我调用,与汇编程序所设计中主程序和子程序之间的链接及信息交换相类似,在高级语言编制的程序中,调用函数和被调用函数之间的链接及信息交换需要通过栈来进行。

  • 若在函数A中调用了函数B,则称函数A为调用函数,称函数B为被调用函数

通常,在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需先完成3件事

  1. 将所有的实在参数、返回地址等信息传递给被调用函数保存
  2. 为被调用函数的局部变量分配存储区
  3. 将控制转移到被调函数的入口

,而从被调函数返回调用函数之前,系统也应该完成3件工作

  1. 保存被调用函数的计算结果
  2. 释放被调用函数的数据区
  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,盘子从上到下分别为

img

这时候n的参数为3。

我们从主函数进入:

img

然后调用hanoi参数,此时hanoi(3,'1','2','3')

进入到hanoi函数内,首先判断是不是函数接口,n的参数值为3,如下图所示,圆圈的地方再次进入hanoi函数

img

将刚刚进入的场景压入栈中,然后进入到下一个场景

img

又碰到hanoi函数,将场景保存起来,进入下一次递。

img

这时碰到出口,将第一个盘子从第一柱移动到第三柱

img

执行结束后,将栈顶元素退栈,返回到上一个场景,继续执行下面的程序块。

img

执行完移动步骤后,又碰到递归,继续调用,将当前场景压入栈中。

img

进入到新的函数内

img

执行移动后,如图所示:

img

此时后边已经没有语句了,退栈,回到栈顶场景。

img

执行move移动后如下图所示:

img

继续进入红框内的递归

img

将当前场景压入栈中,继续递归。

img

此时满足归的条件,移动后:

img

归回来,继续执行下面的代码块:

img

移动后:

img

继续递归,如下图所示:

img

移动后:

img

成功了,程序结束了没?

执行完后,消除栈顶场景,两个场景后面都没语句,这程序结束。

运行结果:

img

一个递归函数的运行过程类似于多个函数的嵌套调用,只是调用函数和被调函数是同一函数。

为了保证递归函数正确执行,系统需设立一个“递归工作栈”,在实际的系统中,一般都综合考虑递归调用和非递归调用统一处理,在此,我们只讨论直接递归调用的处理机制。

每一层次递归所需信息构成一个“工作记录”,其中包括所有的实在参数、所有的局部变量以及上一层的返回地址,每进入一层递归,就产生一个新的工作记录压入栈顶,每退出一层递归,就从栈顶弹出一个工作记录

上述其实少了几次的工作记录,因为一段代码块内调用了两次递归,为了方便理解,我把所有在同一层次内的内层次递归记录省略掉了。

本文链接:

https://nullcode.fun/21.html
1 + 8 =
快来做第一个评论的人吧~