【问题背景】

古代有一个梵塔，塔内有三个座A、B、C，A 座上有64个盘子，盘子大小 不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移 到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子 始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求输出移动 的步骤。

问题一：关于移动次数

设移动的盘子数量为n， T_n 为将n个圆盘从一根桩柱移动到另一根桩柱所需要的最少移动次数；

显然 T₀ = 0， T₁ = 1， T₂ = 3

那么如何移动 n 个盘子？

1. 首先把n - 1个小的圆盘移动到一个不同的桩柱上（需要移动T_n-1次），然后再移动最大的圆盘（移动1次），最后再把那n - 1个小的圆盘移回到最大的圆盘上面（移动T_n-1次），这样至多需要2T_n-1 + 1次，我们可以得到 T_n <= 2T_n-1 + 1；

2. 事实上，当我们移动最大的盘子时，那n - 1个小的圆盘必须已经在某根桩柱上了，而这至少需要移动T_n-1次，如果我们不太精明，则移动最大的圆盘则会多于1次，但是在最后一次移动最大盘子之后，我们必须把那n - 1个盘子移动到最大盘子的上面，这也需要T_n-1次，我们可以得到T_n >= 2T_n-1 + 1；

3. 把这两个不等式与T₀结合起来可以得到：

   T₀ = 0；
   T_n = 2T_n-1 + 1，n > 0

4. 此时可以通过数学归纳法得到 T_n = 2ⁿ - 1，n >= 0

问题二：如何理解Hanoi塔

1. 递归的基本思想在于将规模较大的问题转化为规模较小的同类问题，递归的正确性是通过数学归纳法来证明的；
2. 理解Hanoi塔的关键在于从层与层之间的交接来理解，而不是展开整个递归；

#include<iostream>
using namespace std;
void hanoi(int n, char src, char mid, char dest){
	 //将src座上的n个盘子，以mid座为中转，移动到dest座 
	if(n == 1){//只需移动一个盘子 
		cout << src << "->" << dest << endl;
		//直接将盘子从src移动到dest即可 
	}	
	else{
		hanoi(n - 1, src, dest, mid);		//先将n-1个盘子从src移动到mid 
		cout << src << "->" << dest << endl;
		hanoi(n - 1, mid, src, dest);	 //最后将n-1个盘子从mid移动到dest 
	}
}
int main(){
	int n;
	cin >> n;
	hanoi(n, 'A', 'B', 'C'); 
	return 0;
}

总结

1. 像Hanoi塔这样大规模的递归，合理性是通过数学归纳法证明的，而不是逐步跟着程序的运行顺序思考，这样很容易被弄的晕头转向；

补充：
对于问题一的证明，参考自：《具体数学》

对于问题二，参考的网站有：

如何理解汉诺塔的递归？
带你理解 Hanoi 汉诺塔递归算法