Question

欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有(　　)

(A)34种  (B)55种  (C)89种  (D)144种

Answer 1

C.方法一：分类法：

第一类：没有一步两级，则只有一种走法；

第二类：恰有一步是一步两级，则走完10级要走9步，9步中选一步是一步两级的，有C＝9种可能走法；

第三类：恰有两步是一步两级，则走完10级要走8步，8步中选两步是一步两级的，有C＝28种可能走法；

依此类推，共有1＋C＋C＋C＋C＋C＝89种，故选C.

方法二：递推法：

设走n级有a_n种走法，这些走法可按第一步来分类，

第一类：第一步是一步一级，则余下的n－1级有a_n－1种走法；

第二类：第一步是一步两级，则余下的n－2级有a_n－2种走法，

于是可得递推关系式a_n＝a_n－1＋a_n－2，

又易得a₁＝1，a₂＝2，由递推可得a₁₀＝89，故选C.