Question

欲登上第10級(jí)樓梯，如果規(guī)定每步只能跨上一級(jí)或兩級(jí)，則不同的走法共有(   )

A．34種

B．55種

C．89種

D．144種

Answer 1

C

解法1：分類法：
第一類：沒有一步兩級(jí)，則只有一種走法；
第二類：恰有一步是一步兩級(jí)，則走完10級(jí)要走9步，9步中選一步是一步兩級(jí)的，有種可能走法；
第三類：恰有兩步是一步兩級(jí)，則走完10級(jí)要走8步，8步中選兩步是一步兩級(jí)的，有種可能走法；
依此類推，共有=89，故選(C)。
解法2：遞推法：
設(shè)走級(jí)有種走法，這些走法可按第一步來分類，
第一類：第一步是一步一級(jí)，則余下的級(jí)有種走法；
第二類：第一步是一步兩級(jí)，則余下的級(jí)有種走法，
于是可得遞推關(guān)系式，又易得，由遞推可得，故選(C)。