递归条件

• 相同结构的子问题————考察子问题与当前问题的关系

• 存在可以单独计算基础结构

所以我们考察第一个条件，汉诺塔的移动方式

第一步将所有上层移动到一个目标柱子外的柱子上

第二步将最大的柱子移动到目标柱子上

第三步将剩下的柱子移动到目标柱子上

而第二步和第三步又可以看做是第一步的一个变种，只是将柱子的顺序打乱了，但是执行同样的步骤是同样的。理解之后，我们便可以将无论有多少层的汉诺塔看做只有两层的汉诺塔进行处理，而这样以后，每当处理上层时我们便要解决上层移动到空柱子上的问题，而又有一个与上一个问题相同的子问题，于是这样一直下去，直到最后真的只剩下两层……

#include<bits/stdc++.h>
using namespace std;

int n;
int ans;
void f(int num,char A,char B,char C){
	if(num==1){
		ans++;
		cout<<A<<"->"<<C<<endl;
		return;
	}
	f(num-1,A,C,B);            //将num-1层从A移动到空白柱子B上 
	cout<<A<<"->"<<C<<endl;
	ans++;
	f(num-1,B,A,C);           //从刚才的B上移动到目标柱子C上 
	cout<<B<<"->"<<C<<endl;
	ans++;
}

int main(){
	cin>>n;
	f(n,'A','B','C');
	cout<<ans;
}