汉诺塔

2025年3月17日 | 阅读 3 分钟

1. 这是一个经典的问题，你要尝试只使用三个桩将所有圆盘从一个桩移动到另一个桩。

2. 最初，所有的圆盘都堆叠在一起，较大的圆盘位于较小圆盘的下方。

3. 你可以将圆盘移动到三个桩中的任何一个，试图重新安置所有圆盘，但是不能将较大的圆盘放在较小的圆盘之上，并且一次只能移动一个圆盘。

这个问题可以通过分治算法轻松解决

在上述 7 个步骤中，在给定条件下，桩 A 中的所有圆盘将被转移到 C

一次只能移动一个圆盘。
较小的圆盘可以放在较大的圆盘上。

设 T (n) 为将 n 个圆盘从桩 A 移动到桩 C 所花费的总时间

将 n-1 个圆盘从第一个桩移动到第二个桩。这可以在 T (n-1) 步中完成。
将较大的圆盘从第一个桩移动到第三个桩将需要第一步。
以递归方式将 n-1 个圆盘从第二个桩移动到第三个桩将再次需要 T (n-1) 步。

因此，花费的总时间 T (n) = T (n-1)+1+ T(n-1)

汉诺塔的关系公式是

我们得到，

这是一个公比为 r=2 的等比数列
第一项，a=1(2⁰)

B 等式是当我们必须将 n 个圆盘从一个桩移动到另一个桩时，汉诺塔技术所需的复杂度。

T (3) = 2³- 1
= 8 - 1 = 7 答案

[正如在概念中所证明的那样，将有 7 个步骤，现在通过一般方程证明]

汉诺塔的程序

#include<stdio.h>
void towers(int, char, char, char);
 int main()
 {
       int num;
       printf ("Enter the number of disks : ");
        scanf ("%d", &num);
      printf ("The sequence of moves involved in the Tower of Hanoi are :\n");
      towers (num, 'A', 'C', 'B');
      return 0;
 
}
     void towers( int num, char from peg, char topeg, char auxpeg)
 {
           if (num == 1)
 {
       printf ("\n Move disk 1 from peg %c to peg %c", from peg, topeg);
           return;
 }
   Towers (num - 1, from peg, auxpeg, topeg);
    Printf ("\n Move disk %d from peg %c to peg %c", num, from peg, topeg);
   Towers (num - 1, auxpeg, topeg, from peg);
 }

输出

Enter the number of disks: 3
The sequence of moves involved in the Tower of Hanoi is
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg