问题:
F0 = 0
F1 = 1
Fn = Fn − 1 + Fn − 2
求Fn
Fibonacci数列是一个非常经典的用递归解决的问题。递归方法如下:
用递归做的话,它的复杂度是指数级的,原因可以通过画递归的结构图就能马上明白了。
还有一种方法是用动态规划的实现,从第一个开始,而不是从最后一个。这样做的好处是我们不会重复计算同一个值,比如我们计算F(10)的时候,如果用递归方法,F(4)会被计算很多遍,浪费了很多时间。
这种方法的空间复杂度为O(n),我们可以使一点小手段,把空间复杂度降为 O(1)
但是,这两种方法(递归和DP)都不是最好的方法,我们来看看一个更巧的方法。
首先告诉你一个事实(下图),可能你不一定会相信。如果你不相信,你可以自己动手试试看。
有了这个式子,问题就还没有完,我们先做一个简单的运算。
如果我们想知道2的100次方是多少,如果你稍微想一下就知道我们先找2的50次方(因为2^100 = 2^50 * 2^50),再找2的25次方,再找2的12次方,。。。,直到2的一次方。
好了,有了上面的基础,如果要算一个矩阵的n次方,我们就不会一个一个矩阵相乘了。代码如下:
这样,整个算法复杂度为O(lg n) .注意:这里的矩阵乘法并没有实现,可以写一个函数实现即可。
分享到:
相关推荐
Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个。 最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思。...
The Fibonacci numbers Fn are defined as follows: F0 is 1, F1 is 1, and ...In other words, each number is the sum of the previous two numbers. The first few Fibonacci numbers are 1, 1, 2, 3, 5, and 8.
//Main 代码如下:using System...namespace Fibonacci{ class Program { static void Main(string[] args) { Console.WriteLine(“Would you like to know which Fibonacci Numbers:”); int number = Convert.T
斐波那契数列随机数发生器、线性同余随机数发生器
爱德华·卢卡斯既研究了这个数列,也研究了有密切关系的斐波那契数(两个数列都是卢卡斯数列)。与斐波那契数一样,每一个卢卡斯数都定义为前两项之和,也就是说,它是一个斐波那契整数序列。两个相邻的卢卡斯数之比...
fibo-GMP 该程序计算斐波那契数列的第 N 个元素。 提出的实现使用执行矩阵乘法和递归供电的迭代算法。 程序用 C99 编写并使用 GNU MP 库。 在页面上阅读有关该方法的更多信息。 只要您链接到 GNU MP,许可证就有效。...
此文件找出所需的斐波那契数。 该函数可以称为 fibon(n),其中 n 是要计算斐波那契数的数字。 nb 此文件不提供斐波那契数列或数字序列,而仅提供所需的数字。 它不需要符号数学工具箱
斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳台阶 矩形覆盖 二进制中1的个数 191. Number of 1 Bits 数值的整数次方 50. Pow(x, n) 调整数组顺序使奇数位于偶数前面 905. Sort Array By ...
Fibonacci---斐波那契数列 FileRead---文件读取(错误) Fileproperties---文件属性 GuessTheNumber---猜数字 JosephusProblem---约瑟夫问题 NarcissisticNumber---水仙花数 PrimeNumber---素数 RPN---逆波兰式 binary...
测验我的一些测验的答案(即使用 node.js v0.12.4 实现): Calc 斐波那契数列。 // example 1$ node fibonacci.jsmax of the last number: 100,1,1,2,3,5,8,13// example 2$ node fibonacci.js 100max of the last ...
佩尔数(Pell Number)是一个自古以来就知道的整数数列,由递推关系定义,与斐波那契数类似。佩尔数呈指数增长,增长速率与白银比的幂成正比。它出现在2的算术平方根的近似值以及三角平方数的定义中,也出现在一些...
java8集合源码PBC-Vbeliaev Python 新兵训练营项目(SoftServe,2017 年 12 月)作者:Beliaev Viacheslav ...斐波那契数列 打印所需斐波那契数的函数。 您可以运行脚本Fibonacci.py number (int): (M
python_projects-beginners 这是一些简单的python项目,... 编写一个要在斐波那契数列中生成的程序并将其存储在列表中。 然后找到所有值的总和(100个问题) 需要问题吗? 在这里下载 :backhand_index_pointing_down:
12、输入一个数据n,计算斐波那契数列(Fibonacci)的第n个值 1 1 2 3 5 8 13 21 34 规律:一个数等于前两个数之和 //计算斐波那契数列(Fibonacci)的第n个值 public class Fibonacci{ public static void main...
跳台阶、变态跳台阶、矩形覆盖其实都和斐波那契数列是一类问题,文中通过示例代码介绍的非常详细,下面话不多说了,来一起看看详细的介绍吧。 跳台阶 问题描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该...
类似于Fibonacci数列的算法问题 台阶数为number或n,跳法数为ret,f(n)代表跳到第n阶台阶的跳法数 算法流程分析 由于青蛙每次只能跳一个台阶或者两个台阶,故 f(n) = f(n-1) + f(n-2) 注:青蛙跳到每
leetcode卡 展开查看 太阳花 - lowPoly风格 ~ 前端学习笔记 FE-Notes JavaScript基础 练习 ...1.求斐波那契数列第n项 2.减少额外空间开销 计算两个数组的交集 输入: [1,1,2,2] [1,2] 输出: [1,2] 找
斐波那契数列 js异步:setTimeout,Promise,callback 遍历:数组,对象,新旧方法 完全随机数 类型判断 原型及原型链 形参实参 Number精度 邮件签名 仿探探左滑右滑 Canvas 绘图 Flex 布局 css 伪类测试 常见面试题
编程实现斐波那契数列求值f(n)=f(n-1)+f(n-2) 编程实现求阶乘n! 编程实现一组数据集合的全排列 实现:assignment2 【任务3-排序与二分查找】 1、排序 实现归并排序、快速排序、插入排序、冒泡排序、选择排序、希尔
目录: 01 教程.png 01.01 2.x与3.x版本区别.png 02 基础语法.png 02.01 命令行参数.png ... 25.26 使用递归斐波那契数列.png 25.27 文件 IO.png 25.28 字符串判断.png 25.29 字符串大小写转换.png ...