题目链接

斐波那契数列

题目描述

斐波那契数列（Fibonacci Sequence）定义如下：

  • 对于 ，有

给定一个正整数 ()，请你输出 的值。由于这个结果可能很大，你只需要输出这个结果对 取模后的结果即可。

解题思路

本题要求计算斐波那契数列的第 项。根据题目给出的数据范围 ，我们可以选择最直观且高效的线性递推方法（也称为动态规划）。

  1. 算法选择

    • 线性递推：由于 的最大值是 ，一个从头开始计算到第 项的循环，其计算量级在 左右，这对于现代计算机来说是完全可以接受的。因此，时间复杂度为 的线性递推是本题的最佳解法。

    • 矩阵快速幂：这种方法的时间复杂度为 ，通常用于处理 值非常大（例如 ）的情况。对于本题，，使用矩阵快速幂虽然也能解决问题，但代码实现更复杂，属于“杀鸡用牛刀”，不是必需的。

  2. 线性递推实现

    我们可以使用迭代的方式来计算 。

    • 状态定义：我们只需要知道前两项就能计算出当前项。

    • 初始条件：根据题目定义，。

    • 递推过程：我们从 开始循环，直到 。在每一步循环中，我们计算 。

    • 空间优化：在计算 时，我们只用到了 和 。因此，我们不需要一个大小为 的数组来存储整个数列，只需要三个变量来滚动更新即可。例如，用变量 分别代表 。在每次迭代后，更新 。

代码

#include <iostream>

using namespace std;

const int MOD = 1000000007;

int main() {
    int k;
    cin >> k;

    if (k == 1 || k == 2) {
        cout << 1 << endl;
        return 0;
    }

    long long a = 1;
    long long b = 1;
    long long c = 0;

    for (int i = 3; i <= k; ++i) {
        c = (a + b) % MOD;
        a = b;
        b = c;
    }

    cout << b << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        
        if (k == 1 || k == 2) {
            System.out.println(1);
            return;
        }

        long a = 1;
        long b = 1;
        long c = 0;

        for (int i = 3; i <= k; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }

        System.out.println(b);
    }
}

MOD = 1000000007

def main():
    k = int(input())
    
    if k == 1 or k == 2:
        print(1)
        return
    
    a, b = 1, 1
    for _ in range(3, k + 1):
        c = (a + b) % MOD
        a = b
        b = c
        
    print(b)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：动态规划 / 递推

  • 时间复杂度：。我们需要一个循环从 迭代到 来计算结果。

  • 空间复杂度：。我们只使用了常数个变量来存储斐波那契数列的中间值。