题目梗概

Hanoi塔问题的基础上，每种圆盘加了一个。实际内容并没有变化。

思考

首先来一波Hanoi问题的步数公式推导：

首先n个不同的圆盘。

只有把n-1个圆盘从a->b，最后把a上剩余的一个圆盘从a->c。

之后把b上的n-1个圆盘从b->c。

这里的两步:把n-1个圆盘从a->c，和n-1个圆盘从b->c.所需要的步骤数。实际上就是把n-1个圆盘从a移动到c的步骤数*2，因为是等价的。从a->b和从b->c移动的圆盘个数都是一样的，所以步数就是 (n-1)*2。

然后还要多一步就是把a上的一个圆盘放到c。

所以递推式是 $A_{n}=A_{n-1}\times 2+1$

这个递推式一般递推取模时使用，不过有个更加简便的公式。

$A_{n}=A_{n-1}\times 2+1$

$\mapsto A_{n} = A_{n-1}\times 2 + 1 + 1 - 1$

$\mapsto A_{n} = A_{n-1}\times 2 + 2 - 1$

$\mapsto A_{n} + 1 = (A_{n-1} + 1 )\times 2$

设$B_{n}=A_{n}+1$

则$B_{n}$为等比数列

所以$B_{n}=B_{1}\times 2^{n-1}$ 即 $B_{n}=2 \times 2^{n-1}$ ->  $B_{n}=2^{n}$

所以$A_{n}=2^{n}-1$

推导完毕

这道题目不过是两个相同的圆盘，所以只是步数*2的问题。只不过这道题目需要高精

代码实现：

#include <cstdio>#include <iostream>#include <algorithm>int Pos,a[1002],n,len=1;void Run(int n){    a[1]=1;    while(n--){            for(int i=1;i<=len;i++){            a[i]*=2;        }        for(int i=1;i<=len;i++){            if(a[i]>9) {            a[i+1]+=a[i]/10;            a[i]%=10;            }        }        if(a[len]) len++;    }    a[1]-=2;    while(a[len]==0){        len--;    }    for(int i=len;i>=1;i--){        printf("%d",a[i]);    }    return ;}int main(){    scanf("%d",&n);    Run(n+1);    return 0;    }

[DP][高精][NOIP]Hanoi双塔问题