C语言实现菲波那契数列求第n项 - 代码解析与优化

C语言实现菲波那契数列求第n项 - 代码解析与优化

菲波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34……该数列从第三项开始，每一项都等于前两项之和。

定义:

• f(0) = 0;
• f(1) = 1;
• f(n) = f(n-1) + f(n-2). n>1的整数

求第n项菲氏数:

输入格式: 输入数据含有不多于50个的正整数n（0≤n≤46）。

输出格式: 对于每个n，计算其第n项菲氏数，每个结果应占单独一行。

输入样例: 6 10

输出样例: 8 55

以下是使用C语言编写的解决方案:

#include <stdio.h>

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

int main() {
    int n;
    
    while (scanf('%d', &n) == 1) {
        int result = fibonacci(n);
        printf('%d
', result);
    }
    
    return 0;
}

解释:

• fibonacci 函数:
  • 该函数接受一个整数 n 作为输入，返回第 n 项菲波那契数。
  • 函数首先定义一个长度为 n+1 的整数数组 fib，用于存储菲波那契数列的前 n 项。
  • 当 n 等于 0 时，返回 0；当 n 等于 1 时，返回 1。
  • 使用循环从 i=2 开始遍历到 n，计算每一项的值，并存储在 fib 数组中。
  • 最后返回第 n 项的值 fib[n]。
• main 函数:
  • 该函数使用循环处理多个输入的正整数 n。
  • 当输入的正整数 n 大于 46 时，循环结束。
  • 在每个输入的正整数 n 中，调用 fibonacci 函数计算第 n 项的菲波那契数，并输出结果。

优化建议:

1. 使用递归实现: 递归实现更简洁，但效率较低，尤其在处理较大的 n 时。
2. 使用迭代实现: 迭代实现效率更高，但代码可能稍微复杂一些。
3. 避免重复计算: 可以使用缓存记录已经计算过的结果，避免重复计算。

总结:

本文提供了一个使用 C 语言实现菲波那契数列求第 n 项的解决方案，并附带详细代码解析和优化建议，希望能够帮助您理解菲波那契数列的计算方法。