汉诺塔模板

汉诺塔的模板

递归做法(超时):

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
stack<int> S[3];
long long sum,hp;

void move(int A,int B){
    ++sum;
    int tmp = S[A].top();
    S[A].pop();
    hp += tmp;
    S[B].push(tmp);
}

void hanoi(int A,int B,int C,int n){
    if(n == 1){
        move(A,C);
        return;
    }else{
        hanoi(A,C,B,n-1);
        move(A,C);
        hanoi(B,A,C,n-1);        
    }
}

int main(){
    int n;
    cin >> n;
    for(int i=n;i>=1;--i){
        S[0].push(i);
    }
    hanoi(0,1,2,n);
    cout << sum << " " << hp << endl;
    return 0;
}

递推做法：

f[1] = 1;
f[n] = f[n-1] + 1 + f[n-1];
f[n] = (1LL << n) - 1;//大数避免pow