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

分类: 计算机技术
推荐阅读:
Rust debug_assert宏的用法和示例 在Rust中,debug_assert宏是一个用于在调试时检查条件的宏;它类似于assert宏,不同之处在于debug_assert仅在Rust编译器的debug模式下进行检查,而在release模式下被完全忽略。
Python any()函数详细教程 any()函数只接受一个可迭代的类型参数;如果该迭代器的任意一个元素为True,则返回True,否则返回False;如果迭代器为空返回False;
Python打印有颜色的字符串 使用Python在命令行或shell终端输出有颜色的字符串,效果如下:
使用Rust serde处理文件(读取、保存) 本文使用serde_json为例;展示Rust serde如何读取文件、保存文件;
C语言计算卡特兰数(catanlan number) 卡特兰数(Catalan number),是组合数学中一种常出现于各种计数问题中的数列;本文使用C语言来计算卡特兰数;
Python abs()函数详细教程 abs()函数返回一个数的绝对值;该函数的参数可以是一个整数、浮点数、复数或定义了__abs__()方法的类;