递归实例:汉诺塔
首先说下汉诺塔的规则:
- 把圆盘从下面开始按大小顺序重新摆放到另一根柱子上。
- 在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘
现在假设总共有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
//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站视频:https://www.bilibili.com/video/BV1uA411N7c5?p=6
\