2019-05-16（栈 递归 ----hanoi塔问题）

严版数据结构：p55

问题描述：

假设有三座塔：X,Y,Z塔，在塔X上插有n个直径大小各不相同的，依小到大编号 1、2、3、4......n的圆盘（如图）现在需要 将 X 下的圆盘转移到塔座Z底下，任然以同样顺序叠排。

同时需要遵循的规则：

1、每次只能移动一个圆盘；
2、圆盘可以插入到X 、Y 和 Z 的任意一座塔；
3、任何时刻都不能将较大的圆盘压到较小的圆盘之上；

如何实现移动圆盘：

如果 n = 1; 直接 从 X 移动到 Z；
如果 n >1,需要借助Y作为辅助的塔坐，
若能设法将 X 中 n之上的 n-1个元素 移动到Y之上， 然后将n 移动到Z 塔座上，然后再讲Y上的n-1个盘移动到Z之上。

如果问题是将X的编号为 n-1个盘转移到z只是和上面的问题的规模缩小一是一样的。

图片引用地址：https://blog.csdn.net/cml__96/article/details/82755706

image.png

下面是关于hanoi塔问题的C语言函数（数据结构）描述：

void hanoi(int n, char x, char y, char  z){
    printf("%i move disk %i from %c to %c \n", ++c, n, x, z);
    {
        if (n == 1){
            move(x, 1, z);"直接将X中的1个元素转移到Z 中"
        }
        else{
            hanoi(n - 1, x, y, z); "将n-1个元素 Z作为辅助塔，将X上编号为1 到 n-1个数据转移到Y上"
            move(x, n, z);  " 将X上编号为n 的圆盘 x移动到z"
            hanoi(n - 1, y, x, z);" 将 y上的编号的1到n-1的盘移动待z,x作为辅助塔"
        }
    }
}

C语言 IDE 实现版：

#include <stdio.h>
#include <string.h>
void move(int n, int x, int y, int z)
{
    if (n == 1)
        printf("%c--->%c\n", x, z);
    else
    {
        move(n - 1, x, z, y);
        printf("%c--->%c\n", x, z);
        move(n - 1, y, x, z);
    }
}
int main()
{
    int num;
    printf("input number:\n");
    scanf_s("%d", &num);
    printf("the step to moving %2d diskes:\n", num);
    move(num, '1', '2', '3');
    system("pause");
    return 0;
}

image.png