-递推- [洛谷 P1096][NOIp 2007]Hanoi双塔问题

题目描述

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

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

输入格式

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

输出格式

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

样例输入

2

样例输入

6

Solution

首先我们知道如果是单个盘子，设$n$个盘子所需步数为$F(n)$ 则$F(n)=2*F(n-1)+1$

然而这道题是双盘，所以相当于把单盘移动次数乘2。

我们可以得出单盘的通项公式为$2^p-1$；

所以双盘的通项公式为$2^{p+1}-2$

这道题数据范围贼大，所以我们需要高精度

Code

//Hanoi双塔问题.cpp
#include<iostream>
#include<cstring>
using namespace std;
int a[100010];
int main(){
    int n;
    cin>>n;
    int j=1;
    int k=1;
    memset(a,-1,sizeof(a));
    a[1]=1;
    for(int i=1;i<=n+1;i++){
        while(a[j]>=0){
            a[j]*=2;
            j++;
        }
        while(a[k]>=0){
            if(a[k]>=10){
                a[k]%=10;
                if(a[k+1]<0){
                    a[k+1]=0;
                    a[k+1]++;
                    break;
                }
                else{
                    a[k+1]++;
                }
            }
            k++;
        }
        j=1;k=1;
    }
    int y=0;
    a[1]-=2;
    for(int i=1;i<=100000;i++){
        if(a[i]>=0){
            y++;
        }
    }
    for(int i=y;i>=1;i--){
        cout<<a[i];
    }
}