1109: Hanoi双塔问题-题解

解题思路：

根据汉诺塔移动次数通项公式：ai = 2^i-1作答即可

注意要乘2，因为每种大小汉诺塔片有2个，所以ai = 2*(2^i-1)

注意事项:

数据规模较大，须适用高精度

用a数组累乘或减1最终求解

init()初始化a数组和其长度指针l

calc1()计算a*2

calc2()计算a-1

参考代码:

#include using namespace std;
int a[10001],l;
void init()
{
    memset(a,0,sizeof(a));
    a[1] = 1;
    l = 1;
}
void calc1()
{
    for(int i = 1; i <= l; i++)
        a[i]*= 2;
       //每位*2
    for(int i = 1; i  9)
        {
            a[i+1]++;
            a[i] %= 10;
        }//遍历调整
    if(a[l+1] != 0) l++;
    //调整长度指针
}
void calc2()
{
    a[1]--; //减去各位
    for(int i = 1; i <= l+1; i++)
        if(a[i] < 0)
        {
            a[i] += 10;
            a[i+1]--;
        }//遍历调整
}
int main()
{
    int n; cin >> n;
    init();
    for(int i = 1; i = 1; i--)
    cout << a[i];
    cout << endl;
    return 0;
}