問題詳情:
欲登上第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.
知識點:計數原理
題型:選擇題