【C语言】【递归】汉诺塔问题代码编写思路(代码意义解读)

  • Post author:
  • Post category:其他


汉诺塔问题介绍:

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

(该介绍来自——百度百科)

假设只有一个金盘,那么直接从A移动到C即可;

假设金盘数量大于一个,那我们需要将A上边除了最大的金盘以外的所有金盘先借助C移动到B,然后把A剩余的最大的金盘移动到C,再用同样的方法将B上的所有金盘借助A移动到C即可;

即假设A有n个金盘,步骤如下:

1. 将A上  n – 1 个金盘先借助C移动到B;

2. 将A上第n个金盘,也就是最大的金盘移动到C;

3. 将B上  n-1  个金盘借助A移动到C;

完成!


那么如何将 n-1个金盘移动到B呢?

步骤如下:

1. 将A上n – 2 个金盘借助B移动到C;

2. 将A上第  n-1 个金盘移动到B;

3. 将C上  n-2  个金盘移动到B;

完成!


而第一步中要移动 n-2  个金盘到C 也是同理。

通过观察我们可以发现,n不断减小,直到 n 等于 1 时便可以直接挪动。且每一步操作的逻辑相似。由此我们考虑使用

递归

来解决汉诺塔问题。


首先创建需要的变量:

我们需要: 三个柱子A、B、C ,金盘;

所以创建变量:char A; char B; char C; int n;         //n为初始时A柱子上的金盘数量;

建议使用scanf()函数以便自定义n的值;


接下来我们来编写汉诺塔游戏的函数,命名为   Hanoi   。

首先考虑Hanoi所需要的参数:

三个柱子,和金盘个数。

先在main函数中继续写出:

Hanoi(A, B, C, n);

这里我们将Hanoi工作的逻辑认作为:通过 B 将 A上 的 n 个金盘移动到C。


你也可以修改游戏规则,比如要求把所有的圆盘移动到B,以进一步理解


代码的逻辑,要自己多做尝试!

由于Hanoi函数未定义,我们要在main函数上边新建函数:

void Hanoi(char A, char B, char C, int n) {  }

函数的具体内容如下:

void Hanoi(char A, char B, char C, int n)
{


    if (n ==  1)
    {
        m(A,C);
    }
    else
    {
        Hanoi(A,C,B,n-1);         
        m(A,C);
        Hanoi(B,A,C,n-1);
    }
}

还记得Hanoi的逻辑吗?

代码中,Hanoi(A,C,B,n-1); 的含义为 通过C将A上的n-1个圆盘移动到B上。

那么  Hanoi(B,A,C,n-1); 是不是也很好理解了呢?

这个代码通过递归实现了我们最开始的想法。

在写到 if ( n == 1) 时,考虑如何实现移动,于是暂时用 m()函数来完成移动。


将 Hanoi代码写完后,再补上 m()函数。

该函数的功能是将圆盘A移动到C:

void m(char from, char dest)
{
    printf("从%c 移动到%c\n",from,dest);
}

至此,代码关键部分完毕。


全代码如下:

void m(char from, char dest)
{
    printf("从%c 移动到%c\n",from,dest);
}

void Hanoi( char A, char B, char C,int n)
{


    if (n ==  1)
    {
        m(A,C);
    }
    else
    {
        Hanoi(A,C,B,n-1);
        m(A,C);
        Hanoi(B,A,C,n-1);
    }
}



int main ()
{
    char A = 'A';
    char B = 'B';
    char C = 'C';
    int n = 0;                          
    scanf("%d", &n);

    Hanoi(A,B,C,n);

    return 0;
}


总结递归心得:


1. 当逻辑相似,且 上一步是下一步的铺垫,且有尽头

(比如在汉诺塔问题中n-1不断重复总会到n =      1,此时便会停止递归并且逐层返回)

,可以考虑使用递归。


2. 使用递归时,要明确递归函数的逻辑,即意义

(在本问题中为上文红字标出的部分)

。递归时,只要逻辑正确,便可以直接编写递归代码,不要详细考虑递归代码运行时的具体过程,此过程非常繁琐。


我容易犯得错误就是陷入思考递归代码运行的过程,忽略了函数的意义,以至于很难构建函数。


仅分享和记录经验与学习过程。 若有错误,还请大家指正!



版权声明:本文为weixin_48212831原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。