C语言求Fibonacci斐波那契数列通项问题的解法总结

问题描述

Fibonacci数列是一个非常经典的数学问题，定义如下：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n>=2)

要求编程实现Fibonacci数列的通项公式求解。

思路分析

Fibonacci数列的通项公式可以用公式表示，通项公式如下：

$$F(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n ]$$

用递归方式实现通项公式求解时，时间复杂度为O(2^n)，很容易造成计算的时间和空间的浪费，使用通项公式求解，时间复杂度为O(1)，算法效率较高，是一种非常好的解决方案。

代码示例

下面是使用C语言实现Fibonacci数列通项公式的代码示例：

#include <stdio.h>
#include <math.h>

// 使用通项公式求解斐波那契数列
int fibonacci(int n){
    int result;
    double sqrt5 = sqrt(5.0);
    double p = (1 + sqrt5)/2;
    double q = (1 - sqrt5)/2;
    result = (int)((1/sqrt5) * (pow(p, n) - pow(q, n)));
    return result;
}

// 测试程序
int main(){
    int n;
    printf("请输入斐波那契数列第n项的n值：");
    scanf("%d", &n);
    printf("斐波那契数列第%d项的值为：%d\n", n, fibonacci(n));
    return 0;
}

示例说明

示例1

输入：

请输入斐波那契数列第n项的n值：5

输出：

斐波那契数列第5项的值为：5

即斐波那契数列的前5个数为：0、1、1、2、3、5。

示例2

输入：

请输入斐波那契数列第n项的n值：10

输出：

斐波那契数列第10项的值为：55

即斐波那契数列的前10个数为：0、1、1、2、3、5、8、13、21、34、55。