[数据结构]-汉诺塔

递归实例：汉诺塔

首先说下汉诺塔的规则：

• 把圆盘从下面开始按大小顺序重新摆放到另一根柱子上。
• 在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘

现在假设总共有n个圆盘：

• n=2时：

  

  1.把小圆盘从A->B

  

  2.把大圆盘从A->C

  

  3.把小圆盘从B->C

• 当有n个盘子时：

把上面n-1个盘子看成是一个整体

1.把n-1个圆盘从A->C->B（原问题规模小了1的问题）

2.把第n个盘子从A->C（移动了一步）

3.把n-1个小圆盘从B->A->C（原问题规模小了1的问题）

代码实现：

 #include<stdio.h>
 ​
 //a,b,c 为盘子的行动路径
 void hanoi(int n,char a,char b,char c)
 {
     if (n > 2)
     {
         //1.把n-1个圆盘从A->C->B
         hanoi(n - 1, a, c, b);
 ​
         //2.把第n个盘子从A->C
         printf("moving from %c to %c\n", a, c);
 ​
         //3.把n-1个小圆盘从B->A->C
         hanoi(n - 1, b, a, c);
     }
 }
 ​
 int main()
 {
     hanoi(5, 'A', 'B', 'C');
 }
复制代码

得出结果：

具体可参照B站视频：www.bilibili.com/video/BV1uA…

\