NC65 斐波那契数列

https://www.nowcoder.com/share/jump/8325865981750260107387

描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足 fib(x)={1x=1,2fib(x−1)+fib(x−2)x>2fib(x)={1fib(x−1)+fib(x−2)​x=1,2x>2​ 的数列

数据范围：1≤n≤401≤n≤40

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn) 的解法

输入描述：

一个正整数n

返回值描述：

输出一个正整数。

第一次提交运行时，提示错误：

solution.c:25:1: error: non-void function does not return a value in all control paths [-Werror,-Wreturn-type]
}
^

#include <stdio.h>
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
int Fibonacci(int n )
{
    int val;
    val = n;
    // write code here
    if ((val < 1) || (val > 40))
    {
        return -1;
    } else if ((val == 1) || (val == 2))
    {
        return 1;
    }
    if ((val > 2) && (val < 41))
    {
        return (Fibonacci(val-1) + Fibonacci(val-2));
    }
}

错误原因：

这个错误提示表明函数 Fibonacci 在某些控制路径中没有返回值。具体来说，当 val 的值在 2 < val < 41 时，你的代码会进入递归调用，但编译器认为如果条件不满足时（虽然逻辑上已经覆盖了所有情况），函数没有明确的返回值。

为了解决这个问题，你可以在函数的最后添加一个默认的 return 语句，即使逻辑上不会执行到那里。以下是修正后的代码：

int Fibonacci(int n )
{
    int val;
    val = n;
    // write code here
    if ((val < 1) || (val > 40))
    {
        return -1;
    } else if ((val == 1) || (val == 2))
    {
        return 1;
    }
    if ((val > 2) && (val < 41))
    {
        return (Fibonacci(val-1) + Fibonacci(val-2));
    }
    return -1; // 默认返回值，虽然逻辑上不会执行到这里
}

其他建议：

• 递归实现是正确的，但对于较大的 n（比如接近 40），递归的效率会很低，因为会有大量的重复计算。可以考虑使用动态规划或迭代的方法来优化性能。
• 条件 (val > 2) && (val < 41) 可以简化为 val > 2，因为前面的条件已经排除了 val <= 2 和 val > 40 的情况。

优化后的代码（迭代法）：

int Fibonacci(int n)
{
    if (n < 1 || n > 40)
    {
        return -1;
    }
    if (n == 1 || n == 2)
    {
        return 1;
    }
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}