C语言实现汉诺塔(图文详解)

Hadara ·

更新时间:2024-09-20

· 1255 次阅读

思路：

当n=1时：

当n=2时：

当n=3时：

当n=4时：

见代码

运行截图

总结

汉诺塔的游戏规则：

有三根金刚石柱子A、B、C，在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环。大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在任何一个柱子上，小环上不能放大环，在三根柱子之间一次只能移动一个环。

即将A柱子上全部的环通过中间柱子B（B柱子作为中介）移动到C柱子上

当A只有一个环的时候：

A->C

当A只有两个环的时候：

A->B A->C B->C

当A只有三个环的时候：

A->C A->B C->B A->C B->A B->C A->C

思路：

1、将 n-1个环先放到B柱子上
2、将A柱子上的最后一个环移动到C柱子上
3、将n-1个环从B柱子移动到C柱子上

当n=1时：

1、将0个环先放到B柱子上

2、将A柱子上的最后一个环移动到C柱子上：A->C

3、将0个环从B柱子移动到C柱子上

当n=2时：

1、将1个环先放到B柱子上：A->B

2、将A柱子上的最后一个环移动到C柱子上：A->C

3、将1个环从B柱子移动到C柱子上:B->C

当n=3时：

1、将2个环先放到B柱子上：使用递归将2个环放到B上，因为A柱子的最后一个环是最大的因此可以先不理会，递归重复当n=2时的步骤，不过是从将2个环从A放到C上改为将2个环从A放到B上了

2、将A柱子上的最后一个环移动到C柱子上：A->C

3、将2个环从B柱子移动到C柱子上:使用递归将2个环从B柱子移动到C柱子上，此时C柱子上已经有了最大的一个环因此可以不用再理会了，递归重复当n=2的步骤，不过是从将2个环从A放到C上改为将2个环从B放到C上了

当n=4时：

1、将3个环先放到B柱子上：递归重复n=3的步骤，不过是从将3个环从A放到C上改为将3个环从A放到B上了

2、将A柱子上的最后一个环移动到C柱子上：A->C

3、将3个环从B柱子移动到C柱子上:递归重复当n=3的步骤，不过是从将3个环从A放到C上改为将3个环从B放到C上了

见代码


#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void move(char X, char Y)
{
printf("%c->%c ", X, Y);
}
void HanoiTower(int n, char A, char B, char C)
{
if (n == 1)//递归终止条件
{
move(A, C);
return;
}
else
{
HanoiTower(n - 1, A, C, B);//将n-1个环从A柱子放到B柱子上，C柱子作为中介
move(A, C);//将A柱子上的最后一个环移动到C柱子上
HanoiTower(n - 1, B, A, C);//将n-1个环从B柱子放到C柱子上，A柱子作为中介
}
}
int main()
{
printf("请确认A柱子上一共有多少个环:\n");
int n = 0;
scanf("%d", &n);
HanoiTower(n, 'A','B','C');//将n个环从A柱子放到C柱子上，B柱子作为中介
}

运行截图