帮我解决奥数题(见补充说明)小明要登20节台阶,每步登2级或3级台阶,共有多少不同的登法?

1个回答

  • 假设最后一步到X级台阶,有F(X)种走法,

    这题求的就是F(20) 因为每步可以迈2级台阶或3级台阶.

    所以最后一步到20级台阶,而倒数第2步可能是在第18或17级台阶.

    所以到20级台阶的走法,是到第18或17级台阶走法的和.

    同样到17级台阶的走法,是到第15或16级台阶走法的和..

    F(20)

    =F(17)+F(18)

    =2F(17)+F(16)

    =3F(16)+2F(15)

    =5F(15)+3F(14)

    =8F(14)+5F(13)

    =13F(13)+8F(12)

    =21F(12)+13F(11)

    =34F(11)+21F(10)

    =55F(10)+34F(9)

    =89F(9)+55F(8)

    =144F(8)+89F(7)

    =233F(7)+144F(6)

    =377F(6)+233F(5)

    =610F(5)+377F(4)

    因为:上4级台阶只有1种走法,所以F(4)=1.

    上5级台阶有2种走法,1次2步走2次走3步或1次走3步再走2步.所以F(5)=2

    F(20)

    =610F(5)+377F(4)

    =610*2+377

    =1220+377=1597

    上20级台阶一共有1597不同的迈法.