当前位置:网站首页>【斐波那契数列】
【斐波那契数列】
2022-06-11 01:43:00 【爱吃榴莲的喵星人】
1.基本介绍
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368
提示:这个数列从第3项开始,每一项都等于前两项之和。
2.递归实现
#include<stdio.h>
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
运行结果

时间复杂度:O(2^n)
空间复杂度:O(n)
提示:空间可以重复利用,不累计的;时间是一去不复返,累计的
3.非递归实现
迭代实现
提示:时间复杂度:O(n) ; 空间复杂度O(1)
#include<stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
运行结果
数组实现
提示:时间复杂度:O(n) ; 空间复杂度O(n)
#include<stdio.h>
#include<stdlib.h>
long long Fibonacci(unsigned int n)
{
if (n == 0)
return 0;
long long ret=0;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
if (fibArray == NULL)
{
printf("空间开辟失败");
}
else
{
fibArray[1] = 1;
fibArray[2] = 1;
for (long long i = 3; i <= n; i++)
{
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
ret = fibArray[n];
free(fibArray);
fibArray = NULL;
}
return ret;
}
int main()
{
unsigned int n = 0;
scanf("%d", &n);
long long ret = Fibonacci(n);
printf("%lld\n", ret);
return 0;
}
以上是本篇文章的全部内容,如果文章有错误或者有看不懂的地方,多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助,可以给喵博主一个关注,你们的支持是我最大的动力。
边栏推荐
- Mentality cannot collapse
- Navicat Premium 15 工具自动被杀毒防护软件删除解决方法
- Everything实现快速搜索的原理
- [C language] storage of data in memory -1 plastic
- app 测试 常用 adb 命令集合
- P4338 [zjoi2018] history (tree section) (violence)
- ADVANCE.AI首席执行官寿栋将在2022新兴市场品牌出海线上峰会分享跨境电商运用AI技术合规
- 深度学习基础篇【4】从0开始搭建EasyOCR并进行简单文字识别
- Project load failed
- Fundamentals of deep learning [4] build easyocr and carry out simple character recognition from 0
猜你喜欢

多级介孔有机金属骨架材料ZIF-8负载乳酸氧化酶(LOD)/四氧化三铁(Fe304)/阿霉素DOX/胰岛素/cas9蛋白/甲硝唑/大黄素甲醚

Enrichment of core knowledge points of interface automation to add points to the interview

NFT insider 61:animoca brands holds US $1.5 billion of encrypted assets in 340 investments

Nodejs send mail

Epoll 原理及应用 && ET模式与LT模式

ShaderGraphs

MySQL backup and recovery

可扩/减容线程池C语言原理讲解及代码实现

Test questions and answers of 2022r1 quick opening pressure vessel operation certificate

Analysis of the difficulties in the architecture design of massive chat messages in the live broadcast room
随机推荐
Epoll 原理及应用 && ET模式与LT模式
Penetration test - security service system +owasp top 10
Stc8a8k64d4 EEPROM read / write failure
Customized redistemplate in redis
Colab reported an error: importerror: cannot import name '_ check_ savefig_ extra_ args‘ from ‘matplotlib. backend_ bases‘
【AI周报】AI与冷冻电镜揭示「原子级」NPC结构;清华、商汤提出「SIM」方法兼顾语义对齐与空间分辨能力
SQL | 计算总和
当逻辑删除遇上唯一索引,遇到的问题和解决方案?
Unity3d model skin changing technology
Bingbing learning notes: find the greatest common divisor and the least common multiple. Complex version reverse string
APP测试_测试点总结
ADVANCE.AI首席执行官寿栋将在2022新兴市场品牌出海线上峰会分享跨境电商运用AI技术合规
92. CompletableFuture 实战
Jetpack compose box control
Blue Bridge Cup: the sixth preliminary round - "temperature recorder"
Why can some programmers get good offers with average ability?
GCC C inline assembly
Record scroll bar position, passive, scrolltop
NFT insider 61:animoca brands holds US $1.5 billion of encrypted assets in 340 investments
可扩/减容线程池C语言原理讲解及代码实现


