HDU-超级阶梯（简单递推）_综合

超级阶梯

Crawling in process...Crawling failedTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

      
       2 2 3

Sample Output

        
         1 2 
          
        
        
         思路：
        
        
         递推的题目，前面几个数为1，1，2，3，第五个可以这样考虑：有些走法是和到第四个一样的，只是最后加了一步，这样f(5）=f(4)+x，x表示其他的走法，到第五级时不是走两步就是一步，一步刚才已经考虑过了，就是f(4)，而最后是走两步的是在第三级开始的，到第三级的走法为f(3)，所以f(5)=f(4)+f(3);后面的类似。所以是斐波那契数列f(n)=f(n-1）+f(n-2)
          
        
        
         代码：
        
        
         
         #include<stdio.h>
int main()
{int a[45];int n,m;a[1]=a[2]=1;for(int i=3;i<=40;i++){a[i]=a[i-1]+a[i-2];}scanf("%d",&n);while(n--){scanf("%d",&m);printf("%d\n",a[m]);}return 0;
}
         

        
        
         
         </pre></div>