一共有20级楼梯，每次可以上1级或2级，登上第20级一共有多少种上法

一共有20级楼梯，每次可以上1级或2级，登上第20级一共有多少种上法

1. 分析

上第1级： 1种上法

上第2级： 2种上法

上第3级： 3种上法  3 = 2 + 1

上第4级： 5种上法  5 = 3 + 2

上第5级： 8种上法  8 = 5 + 3

...

1，2，3，5，8， ...

从第3级楼梯开始，每级楼梯的上法等于之前两级楼梯上法的和。

由此构成斐波那契数列，登上第20级台阶种类数即为该数列第二十项的数值,经计算为10946种

2. 代码

#include<stdio.h>
#include<string.h>int foo(int n)
{if (1 == n) {return 1;}if (2 == n) {return 2;}if (n > 2) {return foo(n-1) + foo(n-2);}
}int main(void)
{int x = foo(20);printf("%dn", x);
}