函数递归-汉诺塔问题

1.问题描述：

①有三根柱子X，Y，Z。X杆上有n只碟子

②每次移动一块碟子，小的只能叠在大的上面

③把所有碟子 从X杆 经Y杆 全部移动到Z杆上.

2.递归求解：

①n<=1

若只有一只碟子，直接X杆→Z杆；

②n>1

<1>把n-1只碟子按大小递减的次序 从X杆 经Z杆 移动到Y杆；

<2>将X杆上第n只碟子 移到Z杆；

<3>然后再将n-1只碟子按大小递减的次序 从Y杆 经X杆 移动道Z杆。

递归体 - 程序中自相似的部分：

·移动n-1只碟子和移动n只碟子的过程是相似的。

·但是这个过程不完全一样，因为盘子插入的杆子变了。

递归的出口 - 递归终止的语句：

·n=1时。

·只剩下1个碟子，直接移动到Z杆即可。

整体大概思路如图：

代码编写如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void hanoi(int, char, char, char);
void move(char, char);
int main()
{
    int n;
    printf("Please input n:");
    scanf("%d", &n);
    hanoi(n, 'a', 'b', 'c');
    return 0;
}
//n个盘子，从x移动到z，用y作临时存放
//            个数     从      经由     到
void hanoi(int n, char x, char y, char z)
{
    if (n == 1)
        move(x, z);
    else
    {
        hanoi(n - 1, x, z, y);
        move(x, z);
        hanoi(n - 1, y, x, z);
    }
}
//显示盘子的移动轨迹
void move(char c1, char c2)
{
    printf("%c → %c\n", c1, c2);
}

三级汉诺塔运行结果如下：

具体的有关该程序的汉诺塔递归调用过程可参考下面的链接：

懒猫老师-C语言-汉诺塔问题详解（hanoi）