您的位置:首页 > 科技 > IT业 > 算法题解:斐波那契数列(C语言)

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

2024/12/23 10:48:48 来源:https://blog.csdn.net/m0_74412436/article/details/142308434  浏览:    关键词:算法题解:斐波那契数列(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.

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com