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

分类: 计算机技术
推荐阅读:
Python实现列表去重的多种方法及性能对比 本文将通过多种方法实现列表(List)去重(将列表中的重复项删除);其中包括使用常规方法去重、set()集和去重、使用enumerate()去重、和使用collections.OrderedDict.fromkeys()实现去重;并编写了测试代码来测试这些去重方法的性能、以及去重后元素的排序是否改变;
Python中@property和@*.setter装饰器的详细用法 @property装饰器的作用是,将一个函数装饰成为类的一个属性,当某个属性需要动态的计算时,用@property来装饰函数最好不过了;
OpenSSL1.x和OpenSSL3.x的区别 OpenSSL 1.x和OpenSSL 3.x是两个不同版本的OpenSSL库,其中有很多重要的区别:
查看Nginx版本信息和编译配置参数 使用命令nginx -v 获取Nginx版本信息;使用命令nginx -V 获取Nginx编译信息;
应该掌握的Linux终端常用快捷键 本篇内容将介绍在Linux系统(例如Debian、CentOS、ubuntu等)终端下使用快捷键来加快你的输入速度,节省你的时间;
Python map()函数 map() 是 Python 中的一个内置函数,它接受一个函数和一个或多个可迭代对象作为输入,返回一个新的可迭代对象,其中每个元素都是将输入函数应用于相应元素的结果。