【C语言】斐波那契数列
C语言 数列 斐波 那契
2023-09-11 14:17:48 时间
什么是斐波那契数列?
1 1 2 3 5 8 13 21 34…,前两项为1,后面的值等于前两项值相加。兔子繁衍就是典型的斐波那契数列问题:
一对兔子,从出生后第三个月起每个月都生一对兔子。小兔子长到第三个月后每个月又生一对兔子。假如兔子都不死,请问第一个月出生的一对兔子,至少需要繁衍到第几个月时兔子总数才能到达n对?输入一个不超过10 000的正整数n,输出兔子总数达到n的最少月数,试编写相应程序。
一、递归实现
当n较大时 例如50,就会出现栈溢出的问题,这种时候需要我们用非递归来实现。
#include<stdio.h>
int Fib(int n)
{
//递归出口
if (n < 3)
return 1;
else
{
return Fib(n - 1) + Fib(n - 2);
}
}
int main()
{
int n;
scanf("%d", &n);
int ret = Fib(n);
printf("%d", ret);
return 0;
}
递归实现的时间复杂度
执行次数:
总的来说,这是一个斜三角。
空间复杂度:二叉树的高度O(n)
时间复杂度的计算:O(2^n)
(计算方法:错位相减)
二、非递归实现(优)
#include<stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n >= 3)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n;
scanf("%d", &n);
int ret = Fib(n);
printf("%d", ret);
return 0;
}
非递归实现的时间复杂度
非递归极大的优化了斐波那契数列算法的时间复杂度,这种算法的时间复杂度是O(n)
相关文章
- C语言字符串函数总结
- 用C语言实现中文到unicode码的转换
- C语言:strcpy()和memcpy()
- C语言/C++基础之跨年烟花程序代码(附源码)
- C语言/C++常见习题问答集锦(三)
- [Url]使用C语言来扩展PHP,写PHP扩展dll
- ZZNUOJ_C语言1041:数列求和2(完整代码)
- ZZNUOJ_C语言1042:数列求和3(完整代码)
- ZZNUOJ_C语言1110:最近共同祖先(函数专题)(完整代码)
- ZZNUOJ_C语言1135:算菜价(附完整源码)
- ZZNUOJ_用C语言编写程序实现1252:18岁生日(附完整源码)
- ZZNUOJ_用C语言编写程序实现1373:连续的n个1(附完整源码)
- 精心为学弟学妹整理了60个适合练手的C语言/C++项目,值得收藏!
- C语言 第四章 关系、逻辑运算与分支流程控制
- C语言之基本算法09—各位全是a的数列之和
- C语言逆向分析——IF条件语句的反汇编,要熟悉各种if的姿势以及与或非表达式组合
- C语言绘制爱心
- 开发成长之路(2)-- C语言从入门到开发(讲明白指针和引用,顺带讲解多文件编程)
- 【维生素C语言】第二章 - 分支和循环
- C语言进阶-指针运算