斐波那契数列C语言多种实现方法
本文将使用C语言通过递归、动态规划、通项公式等技巧来计算斐波那契数列;并获得斐波那契数列的第n项值;
斐波那契数列
斐波那契数列指的是这样一个数列:
0,1,1,2,3,5,8,13,21,34,55,89,144,........
从第3项开始,每一项都等于前两项的和;递推方式定义:
Fn = Fn-1 + Fn-2
且:
F0 = 0
F1 = 1
C语言递归实现
#include <stdio.h>
//返回斐波那契数列的第n项
//n从0开始
int fibonacci(int n){
if (n <= 1){
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main(){
for(int n=0;n<10;n++){
printf("%d ", fibonacci(n));
}
return 0;
}
斐波那契数列前10项:
0 1 1 2 3 5 8 13 21 34
C语言动态规划实现
#include <stdio.h>
int fibonacci(int n){
int a = 0, b = 1, c, i;
if (n == 0){
//第一项为0
return 0;
}
for (i = 2; i <= n; i++) {
c = a + b; //第n项等于前两项的和
//更新前两项的值
a = b;
b = c;
}
return b;
}
int main()
{
int n = 11;
printf("%d",fibonacci(n));
return 0;
}
程序输出:
89
C语言通项公式实现
斐波那契数列的通项公式为:

#include <stdio.h>
#include <math.h>
//使用通项公式
int fibonacci(int n){
return (1/sqrt(5))*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n));
}
int main(){
for(int n=0;n<10;n++){
printf("%d ",fibonacci(n));
}
return 0;
}
输出:
0 1 1 2 3 5 8 13 21 34
总结
这三种方法中,使用通项公式计算斐波那契数列的性能是好的。