SDUT OJ 走楼梯

89
55
28657

大数的递推（这题挺简单，但再次做又有了问题）

#include <iostream>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
char s[1010][500]={"0","1","2"};//用2维字符数组存
int a[1010],b[1010];

int main()
{
? ? int n,m,i,j,k;
? ? for(i=3;i<=1000;i++)
? ? {
? ? ? ? memset(a,sizeof(a));
? ? ? ? memset(b,sizeof(b));
? ? ? ? int l1=strlen(s[i-1]);
? ? ? ? int l2=strlen(s[i-2]);
? ? ? ? k= l1>l2?l1:l2;
? ? ? ? for(j=l1-1;j>=0;j--)//注意这里的处理a[],b[]里的都是s[][]的逆数组。方便了a,b 相加 时a[j+1]++；故a要存逆数组
? ? ? ? ? ? a[l1-1-j]=s[i-1][j ]-'0';
? ? ? ? for(j=l2-1;j>=0;j--)
? ? ? ? ? ? b[l2-1-j]=s[i-2][j ]-'0';
? ? ? ? for(j=0;j<k;j++)
? ? ? ? {
? ? ? ? ? ? a[j]+=b[j];
? ? ? ? ? ? if(a[j]>=10)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? a[j+1]++;
? ? ? ? ? ? ? ? a[j]=a[j]-10;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(j=400;j>=0;j--)
? ? ? ? {
? ? ? ? ? ? if(a[j]!=0)
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? int p=j,t=j;
? ? ? ? for(j=0;j<=p;j++)//有=号
? ? ? ? {
? ? ? ? ? ? s[i][j]=a[t--]+'0';
? ? ? ? }
? ? }
? ? ? ? int o;
? ? ? ? cin>>o;
? ? ? ? while(o--)
? ? ? ? {
? ? ? ? ? ? cin>>n;
? ? ? ? ? ? cout<<s[n]<<endl;
? ? ? ? }
? ? return 0;
}

法二：此法可针对多种递推公式

#include<cstdio> #include<iostream> #include<cstring> using namespace std; char s[1010][500];//列数组要大于下边for中j的的范围否则多输出00000000.... int main() { ? ? int n,k; ? ? memset(s,'0',sizeof(s));//清零在赋值前！ ? ? s[0][0]='0'; s[1][0]='1',s[2][0]='2',s[3][0]='3'; ? ? for(i=4; i<=1000; i++) ? ? { ? ? ? ? for(j=0; j<300; j++) ? ? ? ? { ? ? ? ? ? ? k=((s[i-2][j]-'0')+s[i-1][j]-'0'+s[i][j]-'0');//记得加s[i][j]; ? ? ? ? ? ? s[i][j]=k%10+'0'; ? ? ? ? ? ? s[i][j+1]=k/10+'0'; ? ? ? ? } ? ? } ? ? int o; ? ? cin>>o; ? ? while(o--) ? ? { ? ? ? ? cin>>n; ? ? ? ? int x=300; ? ? ? ? for(i=300; i>=0; i--) ? ? ? ? ? ? if(s[n][i]!='0') ? ? ? ? ? ? { ? ? ? ? ? ? ? ? x=i; ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? if(n==0) ? ? ? ? ? ? printf("0n"); ? ? ? ? else ? ? ? ? { ? ? ? ? ? ? for(i=x; i>=0; i--) ? ? ? ? ? ? ? ? printf("%c",s[n][i]); ? ? ? ? ? ? cout<<endl; ? ? ? ? } ? ? } ? ? return 0; }