欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有( )
(A)34种 (B)55种 (C)89种 (D)144种
欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有( )
(A)34种 (B)55种 (C)89种 (D)144种
C.方法一：分类法：
第一类：没有一步两级，则只有一种走法；
第二类：恰有一步是一步两级，则走完10级要走9步，9步中选一步是一步两级的，有C
＝9种可能走法；
第三类：恰有两步是一步两级，则走完10级要走8步，8步中选两步是一步两级的，有C
＝28种可能走法；
依此类推，共有1＋C＋C＋C
＋C
＋C
＝89种，故选C.
方法二：递推法：
设走n级有an种走法，这些走法可按第一步来分类，
第一类：第一步是一步一级，则余下的n－1级有an－1种走法；
第二类：第一步是一步两级，则余下的n－2级有an－2种走法，
于是可得递推关系式an＝an－1＋an－2，
又易得a1＝1，a2＝2，
由递推可得a10＝89，故选C.