图解栈分析Hanoi Tower(汉诺塔)程序
程序员文章站
2024-03-17 08:52:22
...
汉诺塔程序伪算法:
将 n 个盘子从 A 塔移动到 C 塔
分解为以下步骤:
1、将 A 塔上 n-1 个盘子借助 C 塔先移动到 B 塔;
2、将 A 塔剩下的第 n 个盘子移动到 C 塔;
3、将 B 塔上的 n-1 个盘子借助 A 塔移动到 C 塔;
以下是代码实现:
#include "stdio.h"
void move(char from, char target)
{
printf("%c -> %c\n", from, target);
}
void hanoi(int n, char from, char media, char target)
{
if (1 == n)
move(from, target); //只有一个盘子时,直接从初始塔移动到目标塔
else
{
hanoi(n - 1, from, target, media); //将前 n-1 个盘子从初始塔移动到介质塔
move(from, target); //将第 n 个盘子从初始塔移动到目标塔
hanoi(n - 1, media, from, target); //将前 n-1 个盘子从介质塔移动到目标塔
}
}
int main(void)
{
int n = 0;
//定义三个柱子:初始柱、介质柱、目标柱
char from = 'A', media = 'B', target = 'C';
printf("请输入盘子数:");
scanf_s("%d", &n);
printf("移动%d个盘子的步骤为:\n", n);
hanoi(n, from, media, target);
return 0;
}
下面图解分析当汉诺塔的A塔上有2个、3个盘子的情况
递归实际上是一种不断压栈、出栈的操作
对于2个盘子的情况,其代码执行情况为:
//已定义 from = 'A', media = 'B', target = 'C',下面演示时用A、B、C代替from、media、target
/*将A塔上的盘子借助C塔先移动到B塔,即要不断利用B塔和C塔,在递归中表现为不断的交换B塔和C塔的参数位置;
将B塔上的盘子借助A塔移动到C塔,即要不断利用A塔和B塔,在递归中表现为不断的交换A塔和B塔的位置*/
hanoi(2, A, B, C)
hanoi(1, A, B, C)
move(A, B)
hanoi(1, A, B, C)
move(A, C)
hanoi(1, A, B, C)
move(B, C)
hanoi(1, A, B, C)
hanoi(2, A, B, C)
压栈后的整个递归如图所示:
一步步出栈即得到:
A -> B
A -> C
B -> C
这就是有2个盘子的汉诺塔的解法。
同理,当汉诺塔有三个盘子时,压栈后的整个递归可以表示为:
一步步出栈即得到
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
这就是有3个盘子的汉诺塔的解法,随着盘子数量的增多,栈操作会变得极为复杂,但其基本原理可以通过2个、3个盘子的汉诺塔的压出栈来理解。