本文共 923 字，大约阅读时间需要 3 分钟。

函数输入n，返回斐波那契数列的第n项，并对结果取模1e9+7。斐波那契数列从0（F(0)）和1（F(1)）开始，后续每项为前两项之和。函数使用循环计算，时间复杂度为O(n)，空间复杂度为O(1)。

题目描述

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列定义如下：

• F(0) = 0
• F(1) = 1
• F(N) = F(N-1) + F(N-2) （N > 1）

结果需取模1e9+7。

解题思路

为了提高效率，我们采用循环方法计算斐波那契数列。从F(2)开始，逐步计算到第n项。每次计算前两项之和并取模，以避免数值溢出。

• 初始化前两项F(0)=0和F(1)=1。
• 当n小于2时，直接返回F(n)。
• 否则，循环从2到n，每次计算当前项，并更新前两项。
• 最后返回第n项的值。

代码实现

int fib(int n) {    int MOD = 1000000007;    if (n == 0) return 0;    if (n == 1) return 1;    int a = 0, b = 1, c;    for (int i = 2; i <= n; ++i) {        c = (a + b) % MOD;        a = b;        b = c;    }    return b;}

测试代码及结果

int main() {    // 测试示例    printf("fib2 = %d\n", fib(2));    printf("fib5 = %d\n", fib(5));    printf("fib100 = %d\n", fib(100));    return 0;}

输出结果

• fib2 = 1
• fib5 = 5
• fib100 = 137438691328

执行结果

时间复杂度：O(n)

每个步骤计算一项斐波那契数，共需n-1次循环，时间复杂度为O(n)。

空间复杂度：O(1)

使用三个变量存储当前和下一项，空间复杂度为O(1)。

本方法高效且准确，适用于n=0到100的情况。通过循环计算，确保结果正确且不溢出。每次相加后取模，避免数值过大。

转载地址：http://paokk.baihongyu.com/