汉诺塔问题求解

    汉诺塔问题是一个典型的递归问题。

怎么去理解？

实际上就是给你3个固定的圆柱，然后给你若干个盘子在起始圆柱上通过挪动依次搬到最后一根圆柱，但是还是要按照圆盘的大小从小到大排列。具体描述以及三个圆盘的搬移。

上图可以看到要完成操作需要执行七次操作，我们再来看4个圆盘的操作

可以很清楚的发现是15次移动即可完成

我们往前推移，发现1个圆盘则需要移动一次即可，两个圆盘即可挪动3次

我们可以发现一个规律挪动圆盘的次数和盘子的数量有紧密关系

不难得出，T(n) = 2^n-1次挪动

但是我们还可以发现一个规律，那么就是每一个T(n) = 2*T(n-1)+1

我们可以发现3个盘子挪动7次，2个盘子挪动3次，会发现T(3) = 2*T(2)+1

4个盘子挪动15次，3个盘子挪动7次，会发现T(4) = 2*T(3)+1

T(n) = 2*T(n-1)+1

这个式子得出来可以干什么？

我们可以得出来n个盘子挪动的次数可以由n-1个盘子先从A柱子挪动到B柱子，然后将最大的盘子挪动到C柱子，最后再将B柱子的盘子在做n-1次挪动到C柱子即可。

所以我们可以使用递归不断重复操作即可的到答案。

参考源代码：

#include<iostream>
using namespace std;

int count(int n)
{
	if(n == 1) return 1;
	else return 2*count(n-1)+1;
}

void hanio(int n,char start,char middle,char end)
{
	if(n == 0){
		return;
	} 
	else
	{
		hanio(n-1,start,end,middle);
		cout<<start<<"->"<<end<<endl;
		hanio(n-1,middle,start,end);
	}
}

int main()
{
	hanio(3,'A','B','C');
	cout<<"一共搬移"<<count(3)<<"次盘子"<<endl;
	return 0;
}