专栏首页sunsky动态规划的楼层算法

动态规划的楼层算法

这是一种常用的算法,本人摸索出一个规律:
/usr/local/Cellar/python3/3.5.1/Frameworks/Python.framework/Versions/3.5/bin/python3.5 /Users/wuqj/PycharmProjects/testPy/step.py
1111111122
1111112222
1111122122
1111221122
1111222222
1112211122
1112212222
1112222122
1122111122
1122112222
1122122122
1122221122
1122222222
1221111122
1221112222
1221122122
1221221122
1221222222
1222211122
1222212222
1222222122
2211111122
2211112222
2211122122
2211221122
2211222222
2212211122
2212212222
2212222122
2222111122
2222112222
2222122122
2222221122
2222222222
10层阶梯,每次最多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)方法就很好了,没有必要用矩阵乘法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • vim打开多个文件、同时显示多个文件、在文件之间切换 打开多个文件:

    1.vim还没有启动的时候: 在终端里输入 vim file1 file2 ... filen便可以打开所有想要打开的文件 2.vim已经启动 输入 ...

    sunsky
  • Xinetd服务的安装与配置详解

    xinetd即extended internet daemon,xinetd是新一代的网络守护进程服务程序,又叫超级Internet服务器。经常用来管理多种轻量...

    sunsky
  • python时间日期格式化和反格式化

    date,datetime和time对象都支持一种 strftime(format)方法,以创建一个表示显式格式字符串控制下的时间的字符串。从广义上讲, 尽管不...

    sunsky
  • 等差数列与等比数列

    数列中的每一项都和它的序号有关,排在第一位的数称为这个数列的第一项(通常也叫做首项)

    attack
  • 斐波那契数列的四种实现

    孔乙己自己知道不能和他们谈天,便只好向 Intern 说话。有一回对我说道,“你写过代码么?”我略略点一点头。他说,“写过代码,……我便考你一考。斐波那契数列的...

    Crossin先生
  • 个人整理方幂和公式(∑i^k 公式)

    有个Oier小学妹问了我一个Σi^k,i<=1e8 ,k<=1e6的问题,我认为这个用伯努利数列可能可以解决他的问题,所以整理了以下文章,给学弟学习学习~~~本...

    Angel_Kitty
  • 使用Kubernetes和容器扩展Spinnaker

    Kubernetes和容器完全改变了我们对完成工作所使用的工具的看法。扩展自动化平台需要通过fork开发定制扩展,并决定是否应该贡献上游的日子已经一去不复返了。...

    CNCF
  • 如何对非结构化文本数据进行特征工程操作?这里有妙招!

    文本数据通常是由表示单词、句子,或者段落的文本流组成。由于文本数据非结构化(并不是整齐的格式化的数据表格)的特征和充满噪声的本质,很难直接将机器学习方法应用在原...

    AI研习社
  • Lucene全文检索的基本原理

    根据http://lucene.apache.org/java/docs/index.html定义:

    Java团长
  • Lucene学习总结之一:全文检索的基本原理

    根据http://lucene.apache.org/java/docs/index.html定义:

    Hongten

扫码关注云+社区

领取腾讯云代金券