斐波那契数列的C语言多种实现方法（递归、循环、动态规划、矩阵乘法和公式法） |
您所在的位置：网站首页 › 斐波那契兔子讲解 › 斐波那契数列的C语言多种实现方法（递归、循环、动态规划、矩阵乘法和公式法） |
|
介绍
斐波那契数列是一个非常有趣的数列，它的每一项都是前两项的和，前两项分别为0和1。这个数列的前几项是：0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765。这个数列的公式可以表示为： F0 = 0F1 = 1Fn = Fn-1 + Fn-2（n >= 2）这个数列有许多有趣的性质，例如，两个连续的斐波那契数之比会收敛于黄金比例，约等于1.61803399。 在这篇博客中，我们将探讨如何使用C语言实现斐波那契数列，并讨论各种方法的时间复杂度。 递归实现递归是最直观的方法，直接根据斐波那契数列的定义F(n) = F(n-1) + F(n-2)来实现。但是这种方法的时间复杂度是O(2^n)，因为它会重复计算很多项，效率非常低。 #include // 斐波那契数列函数 int fibonacci(int n) { if(n == 0) { return 0; } else if(n == 1) { return 1; } else { return fibonacci(n-1) + fibonacci(n-2); } } int main() { int n; printf("请输入一个整数："); scanf("%d", &n); printf("斐波那契数列的第%d项为：%d\n", n, fibonacci(n)); return 0; } 循环实现循环实现是一种更有效的方法，它使用两个变量来保存前两项，然后通过循环来计算第n项。这种方法的时间复杂度是O(n)，效率比递归高很多。 #include // 斐波那契数列函数 int fibonacci(int n) { if(n {1,1},{1,0}}; if (n == 0) return 0; power(F, n - 1); return F[0][0]; } void multiply(int F[2][2], int M[2][2]) { int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } void power(int F[2][2], int n) { int i; int M[2][2] = {{1,1},{1,0}}; // n - 1 times multiply the matrix to {{1,0},{0,1}} for (i = 2; i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |