很经典的问题,经常被用来演示DP
首先是一种很糟糕的递归解法
我不知道第45项有没有超过int32的范围,但是记得90多项才超过int64,所以这里姑且先用long long int
递归是一种计算科学中很重要的方法,如果你不熟悉而又对计算科学有兴趣,那么就请多花点时间去熟悉它- #include <stdio.h>
- long long int fib(int);
- int main()
- {
- printf("%lld", fib(45));
- return 0;
- }
- long long int fib(int n)
- {
- if(n == 1)
- return 1;
- if(n == 2)
- return 1;
- return fib(n-1) + fib(n-2);
- }
复制代码 这段代码在我的机器上用了将近11秒,因为存在大量的重复计算,例如计算第五项,那么要重新计算第四项和第三项,计算第四项又要计算第三项和第二项
但是之前第四项和第三项都已经计算过了,为了除掉这些重复计算,用一个数组把之前计算过的都保存起来:
因为已经知道不会溢出,所以这里就改用int了
去掉重复运算后,运行时间可以忽略
这是我比较喜欢的解法,代码的含义一眼就能看出来,如果问题还要求小于45的其他项,可以直接在这个数组中查询- #include <stdio.h>
- int main()
- {
- int i;
- int fib[45 + 1];
- fib[1] = 1;
- fib[2] = 1;
- for(i = 3; i != 45+1; ++i)
- fib[i] = fib[i-1] + fib[i-2];
- printf("%d\n", fib[45]);
- return 0;
- }
复制代码 当然,递归也是可以的,用函数的参数来保存前两项,从而避免重复运算
但是对于C和其他命令式语言而言,递归的写法没有那么自然,运行效率也必然低一些(这个问题上看不出)- #include <stdio.h>
- int fib(int);
- int _fib(int, int, int, int);
- int main()
- {
- printf("%d\n", fib(45));
- return 0;
- }
- int fib(int n)
- {
- if(n == 1 || n == 2)
- return 1;
- return _fib(1, 1, 1, n-2);
- }
- int _fib(int a, int b, int n, int des)
- {
- if(n == des)
- return a+b;
- else
- return _fib(b, a+b, n+1, des);
- }
复制代码 最后,如果要尽可能地节省内存,而且只要求45项这一个解,可以这么写- #include <stdio.h>
- int main()
- {
- int a = 1;
- int b = 1;
- int pos = 3;
- while(pos <= 45){
- b = a + b;
- a = b - a;
- pos += 1;
- }
- printf("%d\n", b);
- return 0;
- }
复制代码 为什么?因为计算第n项,只需要第n-1项和第n-2项,所以无论何时保存两项就够了
最后,求斐波那契数列的第n项可以转化为矩阵乘法,((0 1) (1 1)) ^( n - 2 )
因为乘方可以二分计算,对于大数来说是最理想的方法
但对于这道题目中的小数字,矩阵乘法反而会慢一点,而且代码也会复杂很多
对于这个问题,代码4是最佳解法 |