LFYZ-OJ ID: 1011 hanoi双塔问题

思路

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

  • 因递推步骤较长(1~200),一定需要高精度运算,按照每次乘2估算,210=1024,即103,当递推200次时,则最大位数会有1000200/10=1060,所以最大数位大约为60位,设置个大小为100的数组来存储高精度数已绰绰有余。

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

例程1

#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

*例程2的思路是先按位乘2,再在最低位+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;
}
上一篇:一小时学会ECMAScript6新特性(一)


下一篇:JS进阶之---函数,立即执行函数