赞
踩
1. 定义:
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、55、...... 这个数列从第3项开始,每一项都等于前两项之和。
2. 求第n个斐波那契数的方法:
(1)递归
- #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;
- printf("input n: ");
- scanf("%d", &n);
- printf("%d\n",Fib(n));
-
- return 0;
- }
我们输入50,看一下第50个斐波那契数是什么
可以看见,光标一直在闪,说明程序是一直在执行的状态,但是没有输出结果,这是为什么呢?
可见,重复计算的数有很多,是个不小的工程量,我们可以计算一下某个斐波那契数被重复计算的次数
统计一下计算第40个斐波那契数时第3个斐波那契数被重复计算的次数(代码如下):
- //递归法
- #include<stdio.h>
- int count = 0;//全局变量
-
- int Fib(int n)
- {
- //统计的是 第3个斐波那契数被重复计算的次数
- if (3 == n)
- {
- count++;
- }
- if (n <= 2)
- {
- return 1;
- }
- else
- {
- return Fib(n - 1) + Fib(n - 2);
- }
- }
- int main()
- {
- int n = 0;
- printf("input n: ");
- scanf("%d", &n);
- printf("%d\n",Fib(n));
- printf("count= %d\n", count);
-
- return 0;
- }
由此可见,计算机的计算量非常大,时间复杂度和空间复杂度都极高,很容易造成栈溢出和超时。所以这里使用递归显然不是一个明智的选择。
(2)迭代
- //迭代法
- #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;
- printf("input n: ");
- scanf("%d", &n);
- printf("%d\n",Fib(n));
-
- return 0;
- }
循环迭代方法的效率大大高于递归,只是相比于递归代码可读性稍微差一些。
3. 提示:
(1)许多问题是以递归的形式进行解释的,这只是因为它们比非递归的形式更为清晰。
(2)但是这些问题的迭代实现往往比递归实现效率更高,虽然代码的可读性稍微差一些。
(3)当一个问题相当复杂,难以用迭代实现时,此时递归实现的简洁性便可以补偿它所带来的运行时的开销。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。