递推(70分)

【算法分析】 设$f_n$是将$n$层双塔从$A$移动到$C$柱子的方案数目，那么通过单层汉诺塔易得$f_{n+2}=2*f_n+2$,中间的那步需要两次。 【代码实现】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=210;
LL f[N];
int main()
{
    int n;
    cin>>n;
    f[0]=0; //初始化
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1]*2+2; //递推
    }
    cout<<f[n];
    return 0;
}

递推+高精度

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int a[N];
//f[i]表示2*i个盘子需要的移动次数
//递推式 f[i]=2*f[i-1]+2(最大的盘子一共有两个) 
void work()
{
    for(int i=0;i<N;i++) //高精度乘以低精度模板 
    {
        a[i]*=2;
    }
    a[0]+=2;//+2
    for(int i=0;i<N;i++) //处理进位模板 
    {
        a[i+1]=a[i+1]+a[i]/10;
        a[i]%=10;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    a[0]=0; //初始化 
    for(int i=1;i<=n;i++)
    {
        work();
    }
    int len=N-1;
    while(len>0&&a[len]==0) len--;
    for(int i=len;i>=0;i--)
    {
        cout<<a[i];
    }
    return 0;
}