斐波那契数的几种求法

爱被打了一巴掌 2022-05-19 10:51 181阅读 0赞

斐波那契数列是比较出名的，其形式为：1，1，2，3，5，8，13，21，34，55……  
那么如何求第n个斐波那契数，我总结了几种算法：

#### 运用三个变量： ####

int fibonacci(int n)
        {
            int a = 1;
            int b = 1;
            int c = 1;
            if (n <= 2)
            {
                return c;
            }
            else
            {
                for (int i = 2; i < n; i++)
                {
                    c = a + b;
                    a = b;
                    b = c;
                }
                return c;
            }
        }

#### 运用数组 ####

int fibonacci(int n)
        { int arr[100] = { 0 };
            arr[0] = 1;
            arr[1] = 1;
            for (int i = 2; i < n; i++)
            { arr[i] = arr[i - 1] + arr[i - 2]; }
            return arr[n - 1];
        }

#### 递归 ####

首先，我们看一下斐波那契数的数学表示方法  
![这里写图片描述][70]

则代码为：

int fibonacci(int n)
        {
            if (n <= 2)
            {
                return 1;
            }
            else
            {
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        }

就这三种方法来说，递归所用的时间复杂度最大，效率最低，但没有创建临时变量；对于第二种方法，因为不知道数组所开辟的空间大小多少，很容易就造成空间浪费，个人推荐使用第一种方法。

[70]: /images/20220519/816f83d44cbe4a71ab1a08bf4e059c44.png

发表评论取消回复

表情：

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

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

相关阅读

相关 509. 斐波那契数

509. 斐波那契数题干描述动态规划五部曲 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如

朴灿烈づ我的快乐病毒、/ 2023年10月16日 15:50/ 0 赞/ 63 阅读

相关斐波那契数列的求法

1、斐波那契数列的递归求法（不推荐使用，一般都会超时）：原理：把fib(n) 问题的计算拆分成 fib(n-1)和fib(n−2) 两个子问题的计算，并递归，以 f(0)

旧城等待，/ 2023年07月25日 11:25/ 0 赞/ 34 阅读

相关斐波那契数

1、用java代码去计算 / @Title:斐波那契数(这个数列从第3项开始，每一项都等于前两项之和) @Author: longzhou

た入场券/ 2023年06月15日 13:29/ 0 赞/ 62 阅读

相关 509. 斐波那契数

参考： [面试题10- I. 斐波那契数列][10- I.] [10- I.]: https://blog.csdn.net/zyx_ly/article/detai

朴灿烈づ我的快乐病毒、/ 2022年12月12日 02:18/ 0 赞/ 216 阅读

相关 509. 斐波那契数

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

太过爱你忘了你带给我的痛/ 2022年10月07日 07:50/ 0 赞/ 222 阅读

相关求斐波那契数列

文章目录一、求斐波那契数列 1.题目描述 2.题目链接 3.解题思路一、求斐波那契数列

落日映苍穹つ/ 2022年08月30日 04:18/ 0 赞/ 262 阅读

相关斐波那契数

> 牛客网《剑指offer》时间限制：`1秒` 空间限制：`32768K` 热度指数：`199742` 解题思路一：如果像这样，将会有大量的计算是重复的，时空

╰+哭是因爲堅強的太久メ/ 2022年06月08日 02:46/ 0 赞/ 224 阅读

相关大斐波那契数

斐波那契数计算公式 : f(n)=f(n-1)+f(n-2) (n>=3) f(1)=1 f(2)=1 对于 n 比较小的情况下，下边的程序就可以实现这个功能

妖狐艹你老母/ 2022年05月26日 02:47/ 0 赞/ 261 阅读

相关斐波那契数的几种求法

斐波那契数列是比较出名的，其形式为：1，1，2，3，5，8，13，21，34，55…… 那么如何求第n个斐波那契数，我总结了几种算法：运用三个变量： in

爱被打了一巴掌/ 2022年05月19日 10:51/ 0 赞/ 182 阅读

相关 golang 斐波那契数

golang 斐波那契数 package main import "fmt" / 斐波那契数，亦称之为斐波

短命女/ 2021年11月02日 02:02/ 0 赞/ 345 阅读