#递归

题意

• n层汉诺塔，从a柱移到c柱，每次移动只能向相邻的移动，求解所需要的步数

思路

• 设计递归函数：对于当前这一片，把它从a移动到c需要先把它上面的移动到c，然后再把它移动到b，再把c上的所有移动到a，再把自己移动到c，然后移过来
• 其中只有移动自己的部分需要记录步数
• 观察发现

代码

#include<bits/stdc++.h>
using namespace std;
int cnt;
void han(int n,int f,int t){
    if(n==0) return ;
    han(n-1,0,2);
    cnt++;
    han(n-1,2,0);
    cnt++;
    han(n-1,0,2);
}

int main(){
    int n;
    while(cin >> n){
        cnt=0;
        han(n,0,2);
        cout << cnt << endl;
    }
    return 0;
}
// int main(){
//     int n;
//     while(cin >> n){
//         cout << pow(3,n)-1 << endl;
//     }

//     return 0;
// }