有一个十层台阶,若每一次可以上一层或两层,登上十层台阶共有多少不同的办法
来源:学生作业帮助网 编辑:作业帮 时间:2024/05/11 17:20:04
有一个十层台阶,若每一次可以上一层或两层,登上十层台阶共有多少不同的办法
有一个十层台阶,若每一次可以上一层或两层,登上十层台阶共有多少不同的办法
有一个十层台阶,若每一次可以上一层或两层,登上十层台阶共有多少不同的办法
递推,菲波那契数列.
1,2,3,5,8,13,21,34,55,89
从第三层开始,每次都是前面两次的数量和.最后是89种.
是递推,但不是菲波那契数列。菲波那契数列是1,1,2,3,5.........
这个是1,2,3,5,.....
这个可以用fibonacci数列的应用来解决。
设登上第十层的台阶的方法数为F(10),登上第九阶的方法数为F(9),依此类推……
如果最后一次选择只登一级,则只能是在第九级上往上再登一级,方法数为:F(9);
若最后一次选择为登两级,则只能在第八级上往上登两级,方法数为:F(8):
登上第十层台阶的方法总数为:F(9)+F(8),依此类推……
F(10)=...
全部展开
这个可以用fibonacci数列的应用来解决。
设登上第十层的台阶的方法数为F(10),登上第九阶的方法数为F(9),依此类推……
如果最后一次选择只登一级,则只能是在第九级上往上再登一级,方法数为:F(9);
若最后一次选择为登两级,则只能在第八级上往上登两级,方法数为:F(8):
登上第十层台阶的方法总数为:F(9)+F(8),依此类推……
F(10)=F(9)+F(8)
=(F(8)+F(7))+F(8)=2F(8)+F(7)
=2(F(7)+F(6)))+F(7)=3F(7)+2F(6)
=3(F(6)+F(5))+2F(6)=5F(6)+3F(5)
=5(F(5)+F(4))+3F(5)=8F(5)+5F(4)
=8(F(4)+F(3))+5F(4)=13F(4)+8F(3)
=13(F(3)+F(2))+8F(3)=21F(3)+13F(2)
=21(F(2)+F(1))+13F(2)=34F(2)+21F(1)
而上第一级台阶的方法只有一次迈一个台阶一种方法,即:F(1)=1;
上第二级台阶的方法可以是一次迈一个台阶共迈两次,也可以是一次迈两个台阶共有两种方法,即:F(2)=2;
则F(10)=34*F(2)+21*F(1)=34*2+21*1=89种方法。即Fibonacci数列的数列1,2,3,5,8,13,21,34,55,89,144,……的10项的值。
收起