斐波那契数列

Posted on Edited on In

题目描述
斐波那契数列是一个非常著名的数列，它的定义如下：F(0)=0，F(1)=1，对于n≥2，F(n)=F(n-1)+F(n-2)。也就是说，斐波那契数列的第n项等于前两项之和。本问题要求计算斐波那契数列的第n项。

输入格式
输入共 1 行，包含一个非负整数 n。

输出格式
输出共 1 行，包含斐波那契数列的第 n 项的值。

数据范围
0 ≤ n ≤ 90

输入样例1：

1
10

输出样例1：

1
55

输入样例2：

1
50

输出样例2：

1
12586269025

注意事项

  • 斐波那契数列的增长速度非常快，所以需要使用能够处理大整数的数据类型，如long long。
  • 递归方法计算斐波那契数列会有大量的重复计算，时间复杂度为O(2^n)，不适合计算较大的n值。
  • 迭代方法可以避免重复计算，时间复杂度为O(n)，空间复杂度为O(1)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;

// 递归方法计算斐波那契数列（不推荐用于大n值）
long long fibonacciRecursive(int n)
{
    if (n <= 1)
    {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// 迭代方法计算斐波那契数列（推荐使用）
long long fibonacciIterative(int n)
{
    if (n <= 1)
    {
        return n;
    }
    
    long long a = 0; // F(0)
    long long b = 1; // F(1)
    long long result;
    
    for (int i = 2; i <= n; i++)
    {
        result = a + b;
        a = b;
        b = result;
    }
    
    return result;
}

int main()
{
    int n;
    cin >> n;
    
    // 调用迭代版本的斐波那契函数（效率更高）
    long long result = fibonacciIterative(n);
    
    // 如果要使用递归版本，可以取消下面这行的注释，并注释掉上面这行
    // 注意：递归版本只适合较小的n值
    // long long result = fibonacciRecursive(n);
    
    cout << result << endl;
    
    return 0;
}

时间复杂度

  • 递归版本时间复杂度：O(2^n)，其中 n 为输入的非负整数。
  • 迭代版本时间复杂度：O(n)，其中 n 为输入的非负整数。
  • 空间复杂度：O(1)（迭代版本）或 O(n)（递归版本，由递归调用栈占用的空间）。

代码解释

  • 递归方法计算斐波那契数列的思想很简单，但存在大量的重复计算，时间复杂度为指数级，不适合计算较大的n值。
  • 迭代方法通过保存前两项的结果来避免重复计算，时间复杂度为线性，适合计算较大的n值。
  • 在代码中，我们使用 long long 类型来存储中间结果和最终结果，以避免在处理较大的n值时发生溢出。
  • 对于n≤90的情况，long long 类型足够存储斐波那契数列的值。如果n更大，可能需要使用大数运算库。