汉诺塔——经典递归问题（c语言实现）

汉诺塔——经典递归问题（c语言实现）

问题背景

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

问题分析

思路：
1.使用的语言：C语言
2.使用的编译器：vs2019
3.参考书籍：谭浩强第四版
4.主要使用的知识：函数的递归
5.代码实现的思路主要分为三步：
假设总共需要移动n个盘子
1.将A柱上的n-1个盘子借助C柱移向B柱
2.将A柱上仅剩的最后一个盘子移向C柱
3.将B柱上的n-1个盘子借助A柱移向C柱

代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void move(int x, int y)
{
	printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c)
{
	if (n == 1)
	{
		move(a, c);
	}
	else
	{
		hanoi(n - 1, a, c, b);//将A座上的n-1个盘子借助C座移向B座
		move(a, c);//将A座上最后一个盘子移向C座
		hanoi(n - 1, b, a, c);//将B座上的n-1个盘子借助A座移向C座
	} 
}
//move中的实参与hanoi函数中的形参相对应，而hanoi函数中形参a，b，c所对应的值也是在有规律的变化
int main()
{
	int n = 0;
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

运行结果

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

D:\c code\小题库\汉诺塔问题\Debug\汉诺塔问题.exe (进程 13928)已退出，代码为 0。
按任意键关闭此窗口. . .

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

D:\c code\小题库\汉诺塔问题\Debug\汉诺塔问题.exe (进程 19616)已退出，代码为 0。
按任意键关闭此窗口. . .

代码分析

图解

核心算法

if (n == 1)
	{
		move(a, c);
	}
else
	{
		hanoi(n - 1, a, c, b);//将A座上的n-1个盘子借助C座移向B座
		move(a, c);//将A座上最后一个盘子移向C座
		hanoi(n - 1, b, a, c);//将B座上的n-1个盘子借助A座移向C座
    } 

判断条件为n是否为1，当n=1时结束，再通过move函数将所需步骤打印即可，递归的过程实在不好描述，只能靠自己理解了

个人研究

1.你会发现n个盘子所需的步数为2的n次方减一，并且最中间一步永远为A–>C
2.为什么奇数个盘子时第一步永远为A–>C，而偶数个时，第一步永远为A–>B？
解释：hanoi(n - 1, a, c, b)函数的实参a，b和c并不是总对应A盘，B盘和C盘并且在传递给形参后abc对应的值会发生变化，但是确是有规律的在变化，为什要了解这个呢?因为这个hanoi函数的形参对应的值会影响move函数的打印。规律为形参abc对应值为ACB，ABC循环变化，再加上第一次调用hanoi函数形参abc对应ABC，这也就解释了为什么奇数个盘子时第一步永远为A–>C，而偶数个时，第一步永远为A–>B

体会

好难，看了一下午才理解，也看了书上的解释，看了其他人的解释，上面的分析图就是拷过来的（hhh），只能举几个实例，一遍遍实现代码再一边理解，找出规律。递归问题都好抽象，很难想象出运行结果，可以做一些简单的递归题目加以理解，慢慢来啦，头疼，哈哈哈

如有错误，还请指正，谢谢！