河内塔中圆盘的移动

Question

请使用 F7 向我逐步解释递归过程。

我只是无法将回报与控制流联系起来。

#include<stdio.h>
#include<conio.h>

void t_of_h(char, char, char, int);

void main()
{
    int n;
    clrscr();

    printf("Enter no of DISC in Tower of Hanoi : ");
    scanf("%d",&n);

    printf("\nTower of Hanoi using %d DISCS\n",n);

    t_of_h('X', 'Y', 'Z', n);
    getch();
}

void t_of_h(char p1, char p2, char p3, int n)
{
   if(n==0)
     printf("Unsuccessful move\n");
   if(n==1)
     printf("Move DISC from %c to %c\n",p1,p3);
   else
   {
      t_of_h(p1,p3,p2,n-1);
      t_of_h(p1,p2,p3,1);
      t_of_h(p2,p1,p3,n-1);
   }
}

Answer 1

如何将 N 个磁盘从 A 塔移动到 B 塔？

1. 将 N-1 个磁盘从 A 塔移动到 C 塔。
2. 将底部磁盘从 A 塔移动到 B 塔。
3. 将 N-1 个磁盘从 C 塔移动到 B 塔。

代码是一个非常直接的实现。如果您假设可以将任意数量的磁盘从一个塔移动到另一个塔，那么这显然是有效的。如何将 N-1 个圆盘从 A 塔移动到 C 塔？好吧，你将 N-2 个圆盘从 A 塔移动到 B 塔，然后将第 N-1 个圆盘从 A 塔移动到 C 塔，然后将 N-2 个圆盘从 B 塔移动到 C 塔。然后重复...

最终，递归停止，因为您有一个磁盘要移动。

一个有趣的练习是“编写一个测试工具，确保不会做出无效的移动”。

---

好的 - 我已经运行了代码。其过程的可视化是可怕的。很难看出到底发生了什么。但它是算法功能的直接报告。现在怎么办？

1 个磁盘

Enter no of DISC in Tower of Hanoi : 1

Tower of Hanoi using 1 DISCS
Move DISC from X to Z

2 个磁盘

Enter no of DISC in Tower of Hanoi : 2

Tower of Hanoi using 2 DISCS
Move DISC from X to Y
Move DISC from X to Z
Move DISC from Y to Z

请注意，它是将磁盘从 X 移动到 Z。如何将 2 个磁盘从 X 移动到 Z？将顶部圆盘从 X 移动到 Y。将底部圆盘从 X 移动到 Z。将原始顶部圆盘从 Y 移动到 Z。

3 个圆盘

Enter no of DISC in Tower of Hanoi : 3

Tower of Hanoi using 3 DISCS
Move DISC from X to Z
Move DISC from X to Y
Move DISC from Z to Y
Move DISC from X to Z
Move DISC from Y to X
Move DISC from Y to Z
Move DISC from X to Z

Answer 2

使用F7？

如果您在理解递归时遇到困难，请拿出笔和纸并逐步执行该程序。使用正确的参数堆叠每个调用。

当你可以想象它时，它应该更简单。