汉诺塔问题（Hanoi Tower Problem）

汉诺塔问题家喻户晓，它源于一个印度的神话，内容如下：

在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

这个问题看起来十分可怕，实际上很简单。接下来就解决一个问题来体会这个小小问题中的大大的递归思想！

有三根柱子，第一根柱子上有n个从下向上越来越小的圆盘。

目标：使第一根柱子上的n个圆盘按原样摆放在另一个柱子上。

注：一次移动一个圆盘，不可以出现大的盘子在小的盘子上面的情况。

解：
首先我们先玩一下这个游戏。

接着我们找出一个规律，要彻底地把这个塔移开，我们必须要移开上方的n-1个盘子，使最下面的盘子可以移动到另一个柱子上，然后在把上方的n-1个盘子移动到最下
面的盘子（也就是最大的盘子）上就可以解决了。而n-1个盘子的移动方法也一样，因为最下面的大盘子对上面的n-1个盘子的移动毫无影响。

因此，我们可以得出一个递推式：

Fn=2Fn−1+1F_n=2F_{n-1}+1

FnF_n代表第一个柱子上有n个盘子的情况，所以这个问题得到了解决

代码如下：时间复杂度O(2n)O(2^n )

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main()
{
	int n;
	int f[20];
	cin>>n;
	f[1]=1;
	for(int i=2;i<=n;i++)
	f[i]=2*f[i-1]+1;
	cout<<f[n]<<endl;
	return 0; 
}

这个问题就简单地这么解决了。（瞎说，还有更简单的方法）

让我们来看一看输出结果：从n=1开始:1 3 7 15 31 63 127 255 511 1023 2047 4095 8191……

我们发现一个规律，所有的FnF_n满足：

Fn=2n−1F_n=2^n-1

这才是最简单的方法！

有些人会说，这个方法是瞎猜的，只是凭运气而已，没事儿，我可以证明一下。

证：
数学归纳法。
当 n=1n=1 时，F(n)=1,2n−1=1F(n)=1,2n-1=1 ;命题显然成立
假设 n=kn=k 时命题成立，即F(k)=2k−1F(k)=2k-1；
当 n=k+1n=k+1 时，F(k+1)=F(k)∗2+1F(k+1)=F(k)*2+1 ;
因为F(k)=2k−1F(k)=2^k-1
所以
F(k+1)F(k+1)
=2F(k)+1=2F(k)+1
=(2k−1)∗2+1=(2^k-1)*2+1
=2k+1−1=2^{k+1}-1
证毕。
所以这才是这种汉诺塔问题的最优解！

最终代码如下：时间复杂度O(⁡log2nlog_2n )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int qp(int a,int b)
{
	if(b==0)
	return 1;
	int t=qp(a,b/2);
	if(b%2==0)
	return t*t;
	else
	return t*t*a;
}
int main()
{
	int n;
	cin>>n;
	cout<<qp(2,n)-1<<endl;
	return 0;
}