当前位置: 首页 > news >正文

算法题解:斐波那契数列(C语言)

斐波那契数列

斐波那契数列是一个经典的数学序列,其中每一项的值是前两项的和。数列的前两项通常定义为0和1,即:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n ≥ 2)

输入一个正整数n,求斐波那契数列的第n项。

样例

假设输入 n = 5,则其输出为:5,即斐波那契数列的第五项。

F(5) = F(4) + F(3)= (F(3) + F(2)) + (F(2) + F(1))= ((F(2) + F(1)) + (F(1) + F(0))) + (F(1) + F(0))= ((1 + 1) + (1 + 0)) + (1 + 0) = 5

下面我们将通过两种不同的算法来解决这个问题。


算法1

(递归)

递归算法是计算斐波那契数列的一种直观方法,基于定义中的递推公式,递归函数将从 n 向下递归到基准条件(n == 0n == 1)。

递归实现思路:
  1. 基本情况:当 n 等于 01 时,直接返回 n
  2. 递归情况:对于其他 n,返回 F(n-1) + F(n-2)
C语言代码:
int Fibonacci(int n){if(n == 0 || n == 1){return n;}return Fibonacci(n - 1) + Fibonacci(n - 2);
}
时间复杂度:

递归算法的时间复杂度是 O(2^n),因为对于每个非基本情况的 n,我们都会调用两次递归函数,这会导致指数级的增长。

空间复杂度:

递归调用使用了栈空间,空间复杂度为 O(n),因为递归的深度最深为 n

优缺点:
  • 优点:实现简单,直观地基于斐波那契定义公式。
  • 缺点:效率较低,存在大量重复计算,如 F(4) 会多次被计算。

算法2

(动态规划)

为了避免递归中的重复计算,我们可以使用动态规划的思想。通过保存中间计算结果来提高效率。通过自底向上的方法,从 F(0)F(1) 开始,逐步计算到 F(n)

动态规划实现思路:
  1. 初始化两个变量 a = 0b = 1,分别表示 F(0)F(1)
  2. 迭代更新 ab,每次计算 F(i) 时, a 存储 F(i-2) 的值,b 存储 F(i-1) 的值;
  3. 最后返回 b,即为 F(n) 的值。
C语言代码:
int Fibonacci(int n) {if(n == 0) return 0;if(n == 1) return 1;int a = 0, b = 1, c;for(int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return b;
}
时间复杂度:

动态规划的时间复杂度是 O(n),因为我们只需要从 F(0) 计算到 F(n),每个数字仅计算一次。

空间复杂度:

空间复杂度为 O(1),因为只用了固定的几个变量来存储中间结果,不需要额外的数组。

优缺点:
  • 优点:效率高,没有重复计算,时间复杂度从递归的 O(2^n) 降到了 O(n)
  • 缺点:相比递归实现稍微复杂一些。

参考文献

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.

通过对比递归算法和动态规划算法,显然动态规划具有更优的性能。在实际编程中,推荐使用动态规划来解决斐波那契数列问题。

http://www.lryc.cn/news/439830.html

相关文章:

  • SSM 框架 个人使用习惯 详细
  • [羊城杯 2020]Blackcat1
  • 腾讯云Ubuntu系统安装宝塔,配置Java环境,运行spring boot项目
  • 双亲委派机制知识点
  • vue part 11
  • 【QT】常用类
  • 从index_put出发全面学习cuda和pytorch技术
  • 浅谈住房城乡建设部科技创新平台布局重点方向
  • 调用 write()函数后,如何知道数据是否已经写入磁盘?
  • 策略路由与路由策略的区别
  • 从底层原理上理解ClickHouse 中的稀疏索引
  • xtu oj 锐角三角形
  • MATLAB系列04:循环结构
  • 虹科方案 | 精准零部件测试!多路汽车开关按键功能检测系统
  • 【加密算法基础——AES CBC模式代码解密实践】
  • 【ViT+Dis】Deepfake Detection Scheme Based on Vision Transformer and Distillation
  • maya-vray渲染蒙版
  • 计网简简单单复习一下
  • PyQt5-loading-圆环加载效果
  • RabbitMQ Spring客户端使用
  • Arduino IDE离线配置第三方库文件-ESP32开发板
  • Node.js 安装及项目实践
  • 如何从混合信号中剔除某一信号——Schmidt正交化的使用(信号互相关)
  • I2C/IIC学习笔记
  • Servlet学习详解--基本涵盖所有Servlet知识点
  • LabVIEW机械手视觉引导系统
  • rabbitmq容器化部署
  • 如何用 Helm Chart 安装指定版本的 GitLab Runner?
  • el-table使用合计和固定列时,滚动条被覆盖区域无法拖拽问题
  • 【疑难杂症2024-005】docker-compose中设置容器的ip为固定ip后,服务无法启动