这是一种常用的算法，本人摸索出一个规律：就是 n层阶梯,每次最多m个台阶,一共有F(n) = F...
这是一种常用的算法，本人摸索出一个规律：就是 n层阶梯,每次最多m个台阶,一共有F(n) = F(n-1) + F(n-2)+ F(n-m)种走法，或者把上楼层想象为下楼！！！
理论在这：http://www.cnblogs.com/CCBB/archive/2009/04/25/1443441.html
# -*- coding:utf8 -*-class Algorithm: stairs = 10 maxSteps = 2 def calNStep(self, stairs, append=''): if len(append) == Algorithm.stairs: print(append) if stairs < 2: return stairs steps=0 for i in range(self.maxSteps): j=i+1 steps += self.calNStep(stairs - j, append+str(j)*j ) return stepsalgo = Algorithm()total=algo.calNStep(Algorithm.stairs)print("%d层阶梯,每次最多%d个台阶,一共有%d种走法" %(Algorithm.stairs,Algorithm.maxSteps,total))# Algorithm.maxSteps=3# total=algo.calNStep(Algorithm.stairs)# print("%d层阶梯,每次最多%d个台阶,一共有%d种走法" %(Algorithm.stairs,Algorithm.maxSteps,total))
/usr/local/Cellar/python3/3.5.1/Frameworks/Python.framework/Versions/3.5/bin/python3.5 /Users/wuqj/PycharmProjects/testPy/step.py111111112211111122221111122122111122112211112222221112211122111221222211122221221122111122112211222211221221221122221122112222222212211111221221112222122112212212212211221221222222122221112212222122221222222122221111112222111122222211122122221122112222112222222212211122221221222222122221222222111122222211222222221221222222221122222222222210层阶梯,每次最多2个台阶,一共有55种走法Process finished with exit code 0
我总结了斐波那契数列算法分析的规律， 用python写了一个，希望对大家有帮助。
图：
简单说，就是斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
递推公式
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)
显然这是一个线性递推数列。
另外斐波那契数列在实际工作中应该用的很少，尤其是当数据n很大的时候（例如：1000000000），所以综合考虑基本普通的非递归O(n)方法就很好了，没有必要用矩阵乘法。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
