Description

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


Input

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

Output

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


Sample Input


2
2
3



Sample Output


1
2

这道题你可以使用数学里学的排列组合的思想来解决，但是这样的题有一个固定的解法：递推！

这个是我用递推的方法给你写的：

# include <stdio.h>

int a[41] , result[1000];

int main()
{
    int n , m;
    int i , j;
    while(scanf("%d" , &n) != EOF)
    {
        for(i = 0 ; i < n ; i++)
        {
            scanf("%d" , &m);
            if(m > 1)
                a[1] = 1;
            else
                a[1] = 0;
            a[2] = 1;
            for(j = 3 ; j <= m ; j++)
                a[j] = a[j-1] + a[j-2];
            result[i] = a[m];
        }
        for(i = 0 ; i < n ; i++)
            printf("%d\n" , result[i]);        
    }   
    return 0;
}



这个是我以前做这道题的时候使用的数学里的排列组合写的：
# include <stdio.h>

double function(int x , int y) ;
double recursion(int n) ;
double a[1000] ;

int main()
{
    int n , m ;
    int i , j , x ;
    while(scanf("%d" , &n) != EOF)
    {
        i = 0 ;
        while(i < n)
        {
            scanf("%d" , &m) ;
            m -= 1 ;
            a[i] = 1 ;
            x = m / 2 ;
            for(j = 1 ; j <= x ; j++)
                a[i] += function(j , m - j) ;
            i++ ;
        }
        for(i = 0 ; i < n ; i++)
            printf("%.lf\n" , a[i]) ;
    }
    return 0 ;
}

double function(int x , int y)
{
    double a , b , c, result ;
    a = recursion(x) ;
    b = recursion(y) ;
    c = recursion(y - x) ;
    result = b / (a * c) ;
    return result ;
}

double recursion(int n)
{
    double sum ;
    if(n == 1 || n == 0)
        return 1 ;
    else
        sum = n * recursion(n - 1) ;
    return sum ;
}


好长时间没有做杭电的题了，都感觉有点陌生了！

我只想到数学方法，递推？怎么搞呀？还是想不到呀，麻烦楼上好友给个详解呀

#include <stdio.h>

int main() {
    long int i = 0, j = 1, ans = 0, n;
    printf("How many stairs are there? (1 <= n <= 40) ");
    scanf("%d", &n);
    for (; n > 1; n--) {
        ans = i + j;
        i = j;
        j = ans;
    }
    printf("\n%d\n", ans);
    return 0;
}

其实这还是 Fibonacci 数列

[ 本帖最后由 voidx 于 2011-4-19 20:15 编辑 ]

谢谢楼上好友