汉诺塔 递归详解

#include <stdio.h>

void move (int n , char x , char y , char z)

// x为起点柱，y为中转柱，z为终点柱

{

    if (n == 1)

    {

        printf("%c --> %c\n",x,z);

        // 把在x的最顶层的盘子只需要转到终点柱就行了，想想看你玩游戏第一个步骤就是这么搬的

    }

    else

    {

        // 以下呢，不妨想象最底层的盘子以上那好几十个盘子为一个整体的盘子，叫做厚盘子，这时候，就只有两个盘子了

        // 那怎么办呢？很简单，把厚盘子移到中转柱，再把最底的盘子移到终点柱，再把厚盘子搬过去不就行了

        // 那你可能会问，可你这样想，那厚盘子里也有那么多个啊，怎么处理？

        // 其实你再想想，我们把目光聚焦在那堆厚盘子，这时候，你会发现

        // 原来我们又可以用到上面提到的处理方法！这就开始山里有座庙，庙里有个和尚，和尚在讲故事，讲什么呢？

        // 讲着山里有座庙，庙里有个和尚，和尚在讲故事，讲什么呢......

        // 那你可能会问，那有好多层，什么时候停止呢？

        // 假设我们到最顶层，就停止了，因为我们不满足一个条件，就是我们没有在上面的盘子可以移动了

        // 这时候，我们只需要把它帮到终点站就行了，跳过第一，第三个步骤

        // 可能很多人会觉得我很难想象出那个搬运的过程，其实你只需要掌握那个循环的过程还有终点就行了

        // 因为去跟踪递归的每一步执行，是非常费劲的，可能只有两三个盘子我们人脑可以去模拟，多了就不行了

        // 递归的精髓是掌握架构，以下三句代码就是架构

        move(n-1 , x , z , y);

        // 把最底层的盘子以上n-1个盘子搬到中转站

        printf("%c --> %c\n",x,z);

        // 把最底层的盘子搬到终点柱

        move(n-1 , y , x , z);

        // 把中转柱那n-1个盘子搬过去终点柱

    }

}

int main ()

{

    int n ;

    scanf("%d",&n);

    move(n,'x','y','z');

    return 0 ;

}