郑州轻工业大学oj题解(c语言)1091: 童年生活二三事（多实

• 题目描述
  Redraiment小时候走路喜欢蹦蹦跳跳，他最喜欢在楼梯上跳来跳去。 但年幼的他一次只能走上一阶或者一下子蹦上两阶。 现在一共有N阶台阶，请你计算一下Redraiment从第0阶到第N阶共有几种走法。
• 输入
  输入包括多组数据。 每组数据包括一行:N(1≤N≤40)。 输入以0结束
• 输出
  对应每个输入包括一个输出。 为redraiment到达第n阶不同走法的数量。
• 参考代码：

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int a[41],i,n;
    a[1]=1;a[2]=2;
    for(i=3;i<=40;i++){
        a[i]=a[i-2]+a[i-1];
    }
    while((scanf("%d",&n)==1)&&(n!=0))
    printf("%d\n",a[n]);
    return 0;
}

• 代码解析：
  首先这题是肯定不难的，千万不要被感觉的繁琐吓到。把问题的数字整理出来：输入的数据是台阶数，我们要算的是，只走一阶加走两阶的走法有多少种。
  很明显，只走一阶加走两阶的走法，是一个标准的斐波那契数列。也就是前两项相加等于第三项，a[i]=a[i-2]+a[i-1];

为什么说是斐波那契数列呢？

我们假设，这个台阶是3阶。我们每次只能走一阶或者两阶。那么走三阶，可以穷举出最多三种走法"

根据上表我们可以把它分类为，第一步只走1阶，和第一步走2阶的。也就是不管后面怎么划分，我们这一步都可以划出两组分支。
以此类推，如果我们继续往上走，我们就要继续判断第二步只走1阶，和第二步走2阶的这两种情况。故，我们每次判断它走一阶和两阶的时候。另一组分支，也应同样考虑。所以，每次判断走法，都要把另一种情况加上，也就是加上前一项的判断。
故，公式为：f(x)=f(x-1)+f(x+2)

理解以上逻辑，做出这题应该不成问题。我们先把题目范畴的走法从3开始，用循环把公式写好，最后输入时，直接输出对应次数的走法次数即可。

解法都在代码中了，不懂的可以评论区问，已经尽量讲详细了！