Hanoi 双塔问题

题目

给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有nn个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。

现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设A_n为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出A_n。

输入格式

一个正整数n，表示在AA柱上放有2n个圆盘。

输出格式

一个正整数, 为完成上述任务所需的最少移动次数A_n。

样例1

输入

1

输出

2

样例2

输入

2

输出

6
数据范围：n<=200

解题思路

这道题看上去跟汉诺塔截然不同，但我们仔细一看
.
.
.

这不就是道答案乘2的汉诺塔吗！
方便起见，附一个递推式：
f(1)=2
f(n(n>=2))= f(n-1)*2+2
最后，也是最重要的一点

用高精！

华丽丽的代码分割线
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
还没放弃？
好吧，这是代码：

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=201;
int n,a[maxn];
void init()
{
    cin>>n;
    memset(a,0,sizeof(a));
    a[maxn-1]=2;
}
void two_two()
{
    a[maxn-1]++;
    int g=0;
    for(int i=maxn-1;i>=1;i--)
    {
        a[i]=a[i]*2+g;
        g=a[i]/10;
        a[i]%=10;
    }
}
void work()
{
    for(int i=1;i<n;i++)two_two();
}
void output()
{
    int i=1;
    while(a[i]==0&&i<maxn)i++;
    for(int j=i;j<maxn;j++)cout<<a[j];
}
int main()
{
    init();
    work();
    output();
    return 0;
}