超级台阶(nyoj 76)

本题输出数据是有规律的，其实就是斐波那契数列的变形，但是可以换一种思路，采用递归思想来解决这个问题，不过实践证明递归效率不高，会超时，但是这并不影响对递归的学习。

一. 采用递归思想，会超时

思路：和用递归求组合数类似，设置递归出口，每次递归都解决一步，然后交给下一次递归，直至到达出口。

代码如下：

#include<stdio.h>
int fun(int m);
int main(void)
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);        
        printf("%d
",fun(m));
    }    
    return 0;
} 
int fun(int m)
{
    if(m==0)
    {
        return 0;
    }
    if(m==1)
    {
        return 1;
    }    
    return fun(m-1)+fun(m-2);
}

二.根据规律，把每种情况的答案都存入数组，根据输入数据，直接调出答案

代码如下：

#include<stdio.h>
int main(void)
{
    int n,m,i;
    int a[41]={0,0,1,2};
    for(i=4;i<41;i++)
    {
        a[i]=a[i-1]+a[i-2];
    }    
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        printf("%d
",a[m]);
    }    
    return 0;
}