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。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言求Fibonacci斐波那契数列通项问题的解法总结 - Python技术站