斐波那契数列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

总结

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

原创内容,如需转载,请注明出处;

本文地址: https://www.perfcode.com/p/c-program-fibonacci-series.html

分类: 计算机技术
推荐阅读:
Linux下快速的重命名文件 在Linux系统下,不知道你们是怎么重命名文件的,虽然方法很多,但我这个绝对是最简单且最高效的,而且只有一条命令就可实现:
Python计算二阶行列式的值 本文将使用Python语言编写程序计算二阶行列式的值;
C语言isdigit()函数:判断字符是否为数字字符 isdigit()是C语言标准库中的一个函数,用于判断一个字符是否是数字字符(ASCII码为48~57);如果传入的字符参数是一个数字字符(0~9),则返回非0值,否则返回0;
python object()函数 object() 是 Python 的内置函数之一,它返回一个新的 object 对象。这个对象没有任何特殊的属性或方法,它是所有类的基类,即所有 Python 类都直接或间接地继承自 object 类。
配置Nginx实现简单的反盗链 本文通过Nginx的配置指令valid_referers来实现简单的图片和其它类型文件的防盗链。
C/C++程序打印输出中文导致乱码的解决方法 C/C++程序打印输出中文导致乱码的解决方法如下: