用递归解决汉诺塔问题

发表于   |   分类于

第二次接触这个问题了。

什么是汉诺塔问题？

汉诺塔 是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

  1. 每次只能移动一个圆盘；
  2. 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

什么是递归？

以我的理解就是，一个函数直接或间接地调用本身。

递归的理解

一个函数调用本身似乎有些难以理解，但函数调用的本质就是在栈顶分配内存，执行相应的操作（姑且这么理解，不知道对错）。

所以对于计算机来说，不管你调用谁。既然你要调用，我就在栈顶分配一块内存给你，执行完毕之后就释放栈顶的这块内存。

也就是说，函数 A 调用函数 B ，和函数 A 调用函数 A 在计算机看来是一样的

这样就引发了一个问题，无限的递归调用，对不断的分配空间，导致内存不够，空间复杂度也很大，所以 C 语言中递归一定次数后就会终止程序。

递归的写法

上面已经说过，不能无限的递归下去，所以必须要有停止的条件。

用一个简单的例子来说明:

1
2
3
4
5
6
7
8
9
10
11
int fun(int num)
{
	if(num <= 1)
	{
		return 1;
	}
	else
	{
		return num*fun(num-1);
	}
}

这是求阶层的一个函数，当 num 小于等于 1 的时候就返回 1 ，否则就返回 num 乘以 num-1 的阶层。所以说，num 小于等于 1 就是递归停止的条件。

如何解决汉诺塔问题

第一次在书上看到这个问题的时候，我就不知道这个怎么移动，题目我都看不太懂。

即便是现在我也说不出四个以上的圆盘该怎么移动，不过正着想不出，倒过来就行了。

逆向思维

  • 将 N 个圆盘从 A 移动到 C ，只要先将 N-1 个从 A 移动到 B ，然后将最下面这个从 A 移动到 C 即可。
  • 而解决 N-1 个圆盘，只要解决 N-2 个圆盘…
  • 一直到要解决 1 个圆盘的时候，直接移动就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//这个函数的作用就是：将 num 个盘子从 A 借助 B 转移到 C
void hannuota(int num, char A, char B, char C)
{
	如果要移动的只是一个盘子，直接将盘子从 A 移动到 C 。
	//用 printf 表示

	如果不止一个盘子，先把 N-1 个盘子从 A 移动到 B 。
	//hannuota(num-1, A, C, B);
	然后在将第 N 个盘子从 A 移动到 C 。
	//用 printf 表示
	上面只是把最下面这个圆盘移动到 C ,还需要把剩下的也移动到 C
	此时盘子在 B 杆上，所以接下来是将 N-1 个圆盘从 B 移动到 C 。
	//hannuota(num-1, B, A, C);
}

解决问题的前提

  • A 杆上面的 N-1 个圆盘可以借助 C 杆移动到 B 杆（同理，B 杆的圆盘也可以借助 C 杆移动到 A 杆）。
  • 当 C 杆放的是大盘子，而要转移的是小盘子的时候，可以把它看成是空杆子。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>


void hannuota(int num, char A, char B, char C)
{
	if(num == 1)
	{
		printf("%d 号盘子从 %c 移动到 %c 。\n", 1, A, C);
	}
	else
	{
		hannuota(num-1, A, C, B);
		printf("%d 号盘子从 %c 移动到 %c 。\n", num, A, C);

		hannuota(num-1, B, A, C);
	}
}

int main(void)
{
	int num;
	printf("请输入圆盘个数：\n");
	scanf("%d", &num);

	hannuota(num, 'A', 'B', 'C');

	return 0;
}

运行结果

1
2
3
4
5
6
7
8
9
10
请输入圆盘个数：
3
1 号盘子从 A 移动到 C 。
2 号盘子从 A 移动到 B 。
1 号盘子从 C 移动到 B 。
3 号盘子从 A 移动到 C 。
1 号盘子从 B 移动到 A 。
2 号盘子从 B 移动到 C 。
1 号盘子从 A 移动到 C 。
Press any key to continue

总结

  1. 这个问题采用的就是分而治之的方法，也就是解决一个问题，先解决一个更简单的问题。
  2. 有一些复杂的问题，只有通过递归才可以比较简单地实现。