C语言递归算法——汉诺塔问题（河内塔）

C语言递归算法——汉诺塔问题（河内塔） 2023-04-08 379

汉诺塔(Tower of Hanoi)，又称河内塔，是一个源于古老传说的。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

简化来说，就是将n个从小到大的圆盘，通过多余的一杆，满足过程圆盘始终上大下小的条件。将n个圆盘移动到另一个杆子。

问题分析

对此问题，我们可以将其简化为两步，首先将n-1个盘，移到一个过渡柱，再将n盘子移到目标柱，如此往复即可最终将盘子移到目标柱。

函数的实现

算法我们使用函数递归算法来实现此函数。首先，设置hanoihans，实现整体功能。然后，再写移动显示函数，输出为盘子n由a移到b柱输出每个步骤。

具体实例

#include <stdio.h>
void hanoi(int n, char x, char y, char z)
{
    void move(char, int, char);
    if (n == 1)
        move(x, 1, z);
    else
    {
        hanoi(n - 1, x, z, y);
        move(x, n, z); //打印显示步骤
        hanoi(n - 1, y, x, z);
    }

}
int main()
{
    void hanoi(int, char, char, char);
    int n;
    printf("请输入要移动的盘子数：（整数）>");
    scanf_s("%d", &n);
    printf("
");
    hanoi(n, A, B, C);
    return 0;                      
}
void move(char getone, int n, char putone)
{
    static int k = 1;
    printf("%2d:%3d 号盘由 %c--->%c
", k, n, getone, putone);
    if (k++ % 3 == 0)//设置行数分理使代码更易读
        printf("
");
   
}