(算法) - 不使用递归，实现斐波那契数列

- 日理万妓 2023-01-14 01:36 142阅读 0赞

> [https://jackniu81.github.io/2021/04/18/Algorithm-Fibonacci-numbers/][https_jackniu81.github.io_2021_04_18_Algorithm-Fibonacci-numbers]

### 文章目录 ###

*  1. 斐波那契数列
 *  2. 解题思路
 *   *  2.1. 递归
     *  2.2. 动态规划
 *  3. Javascript 实现

# 1. 斐波那契数列 #

`斐波那契数列`：0, 1, 1, 2, 3, 5, 8, 13 … …

通常用 F(n) 表示，形成的序列称为 `斐波那契数列` 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

F(0) = 0，F(1) = 1
    F(n) = F(n - 1) + F(n - 2)，其中 n > 1

敏捷开发时，我们估算`Story Point`，通常就是使用斐波那契数列。

# 2. 解题思路 #

## 2.1. 递归 ##

F(n) = F(n - 1) + F(n - 2)， 很简单，就不谈了。

## 2.2. 动态规划 ##

动态规划的思想是，记录中间计算结果，计算后面相时，根据前面保存的结果直接计算，避免重复计算。

# 3. Javascript 实现 #

/** * @param {number} n * @return {number} */
    var fib = function(n) { 
        if(n===0)
            return 0;
        if(n===1)
            return 1;
    
        let arr = [0,1]
        for(let i=2;i<=n;i++){ 
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n];
    };

> 还可以进一步优化，当前使用数组记录以及计算过的F(n)，由于F(n) = F(n - 1) + F(n - 2)，实际只需要记录最近的2个值即可，不需要使用数组记录全部数据。

> \---------------- END ----------------
> 
>   
>   
>   
>   
>   
>   
>   
>   
>

[https_jackniu81.github.io_2021_04_18_Algorithm-Fibonacci-numbers]: https://jackniu81.github.io/2021/04/18/Algorithm-Fibonacci-numbers/

发表评论取消回复

表情：

评论列表（有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：栈模拟递归斐波那契数列

题目来源 [LEETCODE][] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

快来打我*/ 2023年02月16日 00:42/ 0 赞/ 145 阅读

相关 (算法) - 不使用递归，实现斐波那契数列

> [https://jackniu81.github.io/2021/04/18/Algorithm-Fibonacci-numbers/][https_jackniu81.

- 日理万妓/ 2023年01月14日 01:36/ 0 赞/ 143 阅读

相关斐波那契数列(递归思想)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

矫情吗；*/ 2022年11月11日 06:13/ 0 赞/ 241 阅读

相关递归算法——阶乘、斐波那契数列

文章目录前言一、什么是递归算法？二、递归算法特点三、递归算法的使用要求四、应用示例——阶乘 1.阶乘概述

蔚落/ 2022年10月28日 14:28/ 0 赞/ 233 阅读

相关斐波那契数列（递归与非递归算法）

斐波那契数列，又称[黄金分割][Link 1]数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F

一时失言乱红尘/ 2022年09月19日 15:29/ 0 赞/ 266 阅读

相关斐波那契数列--递归与非递归实现

初识斐波那契数列：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖

ゝ一纸荒年。/ 2022年05月23日 05:40/ 0 赞/ 231 阅读

相关递归算法--斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 很容易我们想到使用递归求解： public

刺骨的言语ヽ痛彻心扉/ 2022年05月18日 01:06/ 0 赞/ 228 阅读

相关递归算法实现斐波那契数列

假定兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？这就是著名的斐波那契数列，也称作兔子数列。 >

Dear 丶/ 2022年05月14日 05:42/ 0 赞/ 232 阅读

相关斐波那契数列递归非递归实现

斐波那契数列是学习c语言递归时，必写的。递归实现代码 int fun(int n) //递归 { if(n==1||n==2)

桃扇骨/ 2022年03月30日 15:12/ 0 赞/ 236 阅读

相关递归求斐波那契数列

斐波那契数列题目描述：编写一个函数，求斐波那契数列的第n项的值。首先，对于斐波那契数列，我们是非常熟悉了，对斐波那契定义为如下：f(0)=0,f(1)=0,f(2)=1

左手的ㄟ右手/ 2021年11月17日 12:34/ 0 赞/ 387 阅读