走楼梯

﹏ヽ暗。殇╰゛Y 2022-08-10 09:58 139阅读 0赞

## 走楼梯 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

小虎发现走楼梯的时候一次上一个台阶比较惬意，一次上两个台阶比较高效，一次上三个台阶就很累人。

小虎是一个即注重质量又注重高效的人，于是他就在上楼梯的时候每步就只跨上一个台阶或两个台阶，

现在小虎想知道他这样上n阶的楼梯一共有多少种走法，但是他又不想亲身经历，只好求助于会编程的你，帮他解决这个问题了。

## 输入 ##

第一行是T，表示接下来有T组输入，每组输入一个N（2 <= N <= 1000)

## 输出 ##

对应每组输入输出一共有多少种走法。

## 示例输入 ##

3
    10
    9
    22

## 示例输出 ##

89
    55
    28657

## 提示 ##

## 来源 ##

## 示例程序 ##

#include <stdio.h>    
    #include <string.h>    
    int max(int a,int b)  
    {  
        return a>b?a:b;  
    }  
    char dsf[1001][500]= {"0","1","2","3"};    
    int main()    
    {    
        int a[500],b[500],i,j;    
        for(i=3; i<=1000; i++)    
        {    
            memset(a,0,sizeof(a));    
            memset(b,0,sizeof(b));    
            int l1=strlen(dsf[i-1]);    
            int l2=strlen(dsf[i-2]);    
            for(j=0; j<l1; j++)    
                a[j]=dsf[i-1][l1-j-1]-'0';    
            for(j=0; j<l2; j++)    
                b[j]=dsf[i-2][l2-j-1]-'0';    
            for(j=0; j<max(l1,l2); j++)    
            {    
                a[j]+=b[j];    
                if(a[j]>9)    
                {    
                    a[j]-=10;    
                    a[j+1]++;    
                }    
            }    
            for(j=400; j>=0; j--)    
            {    
                if(a[j]!=0)    
                {    
                    break;    
                }    
            }    
            int l=j,ll=j;    
            for(j=0; j<=l; j++)    
                dsf[i][j]=a[ll--]+'0';    
            dsf[i][j]=0;    
        
        }    
        int t,n;    
        scanf("%d",&t);    
        while(t--)    
        {    
            scanf("%d",&n);  
            printf("%s\n",dsf[n]);  
        }    
        return 0;    
    }