1223. 汉诺塔的移动次数

汉诺塔的问题大家都已经很熟悉了，有三个柱子，每个柱子上有一些大小不一的金片，要把金片从 AA柱移动到 CC柱，可以借助 B 柱，请问 n个金片的情况下，需要最少移动多少次？

输入

输入一个整数 nn 代表金片的数量（n≤20）。

输出

一个整数，代表 n 个金片的移动次数。

方法一：

数组+递推求解

#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int a[n];a[1]=1;for(int i=2;i<=n;i++){a[i]=a[i-1]*2+1;}cout<<a[n];return 0;
}

方法二：

递归方式求解

#include<iostream>
using namespace std;
int sum(int n)
{if(n==1){return 1;}return sum(n-1)*2+1;
}
int main()
{int n;cin>>n;cout<<sum(n);return 0; 
}