题解 | Hanoi双塔问题-NOIP2007普及组复赛D题

给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；

输入描述:

• 虽然每种大小盘子数量为2，但对总步数的影响只是一个简单的倍数关系而已，递推关系很容易可以总结出来：a_n=a_n-1+2+a_n-1=2(a_n-1+1)，n=1时，a₁=2。故递推的过程就是从a₁=2开始每次先加1，再乘2。

• 因递推步骤较长（1～200），一定需要高精度运算，按照每次乘2估算，2¹⁰=1024，即10³，当递推200次时，则最大位数会有1000^200/10=10⁶⁰，所以最大数位大约为60位，设置个大小为100的数组来存储高精度数已绰绰有余。

• 可以将程序的实现划分为几个功能函数：print()输出高精度数字，jia1()高精度数字+1，cheng2()高精度数字乘2。

#include<iostream>
using namespace std;
int an[100];                            //存储an， a[0]为位数
void print(){                           //高精度数字输出函数
    for(int i=an[0]; i>=1; i--) printf("%d", an[i]);
}
void jia1(){                            //高精度数字+1
    int i=1, jw=0;
    an[1]+=1;                           //最低位+1
    do{                                 //进位处理
        an[i]=an[i]+jw;
        jw=an[i]/10;
        an[i]%=10;
        i++;
    }while(jw);
    if(an[an[0]+1])  an[0]++;  
}
void cheng2(){                          //高精度数字*2
    int i, jw;
    for(i=1, jw=0; i<=an[0]; i++){
        an[i]=an[i]*2+jw;
        jw=an[i]/10;
        an[i]%=10;
    }
    if(jw) { an[i]=jw; an[0]=i; }
}
int main(){
    int n;
    scanf("%d", &n);
    an[0]=1, an[1]=2;                   //将an按照a1来初始化:a1=2;
    for(int i=2; i<=n; i++){
        jia1();                         //+1
        cheng2();                       //*2
    }
    print();
}

例程2

#include<cstring>   
#include<iostream>
using namespace std;
int f[300],n;
void oper(){
    int i;
    for (i=1;i<=f[0];i++) f[i]*=2;      //按位×2
    f[1]+=2;                            //最低位+2
    for (i=1;i<=f[0];i++){              //统一处理进位
        f[i+1]+=f[i]/10;
        f[i]%=10;
    }
    if (f[f[0]+1]!=0) f[0]++;           //确定位数
}
int main(){
    cin>>n;
    memset(f,0,sizeof(f));              //这行不需要，全局的会自动初始化为0
    f[0]=1; f[1]=2;                     //f初始化为a1=2；
    for(int i=2;i<=n;i++)
        oper();
    for(int i=f[0];i>=1;i--)            //输出结果
        cout<<f[i];
    cout<<endl;
    return 0;
}