斐波那契数列C语言多种实现方法


本文将使用C语言通过递归、动态规划、通项公式等技巧来计算斐波那契数列;并获得斐波那契数列的第n项值;

斐波那契数列

斐波那契数列指的是这样一个数列:

0,1,1,2,3,5,8,13,21,34,55,89,144,........

从第3项开始,每一项都等于前两项的和;递推方式定义:

F n = F n-1 + F n-2

且:

F 0 = 0
F 1 = 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

总结

这三种方法中,使用通项公式计算斐波那契数列的性能是好的。

如需转载,请注明出处;本文地址:https://www.perfcode.com/p/c-program-fibonacci-series.html