C语言 - 汉诺塔详解（最简单的方法，进来看看就懂）

一.什么是汉诺塔？

汉诺塔起源于印度的一个古老传说，传说是什么不重要。重要的是它是怎么实现的以及代码是怎么写的。
是这样的，总共有 3 个柱子，第一个柱子上有 n 个圆盘，圆盘的大小由下到上依此递减。
以 n = 3为例

大概就是这么个东西。
我们要做的就是利用第二个柱子把第一个柱子上的所有圆盘放到第三个柱子上，在移的过程中大盘子不能放在小盘子上。

二.如何实现捏？

假如有 n 个盘子

我们要将这 n 个盘子移到第三个柱子上，先需将前 n-1 个盘子移到第二个柱子上，再将第 n 个盘子移到第三个柱子上，最后将这 n 个盘子移到第三个柱子上。

要将这 n-1 个盘子移到第三个柱子上，先需将前 n-2 个盘子移到第二个柱子上，再将第 n-1 个盘子移到第三个柱子上，最后将这 n-1 个盘子移到第三个柱子上。

以此类推。。。

所以，不难看出，汉诺塔的问题本身是一个大问题，我们可以将这个大问题转化为许多个相似的小问题来进行解决。若要将一个大问题转化为许多个相似的小问题来解决，我们就需要用到递归了。

三.如何写代码？

在写汉诺塔的时候不能过于关注函数内部是如何实现的，只需知道它的逻辑即可。如果过于关注函数内部是如何实现的，那么这个问题是很难解决的。

#include 

void hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		printf("%c->%c ", pos1, pos3);
	}
	else
	{
		hanoi(n - 1, pos1, pos3, pos2);
		printf("%c->%c ", pos1, pos3);
		hanoi(n - 1, pos2, pos1, pos3);
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	hanoi(n,'A','B','C');
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四.为什么需要移动 2^n - 1 次/