挑战4

rosynirvana

很经典的问题，经常被用来演示DP
首先是一种很糟糕的递归解法

我不知道第45项有没有超过int32的范围，但是记得90多项才超过int64，所以这里姑且先用long long int
递归是一种计算科学中很重要的方法，如果你不熟悉而又对计算科学有兴趣，那么就请多花点时间去熟悉它

1. #include <stdio.h>
   
2. 
   
3. long long int fib(int);
   
4. 
   
5. int main()
   
6. {
   
7.   printf("%lld", fib(45));
   
8.   return 0;
   
9. }
   
10. 
    
11. long long int fib(int n)
    
12. {
    
13.   if(n == 1)
    
14.     return 1;
    
15.   if(n == 2)
    
16.     return 1;
    
17.   return fib(n-1) + fib(n-2);
    
18. }

复制代码

这段代码在我的机器上用了将近11秒，因为存在大量的重复计算，例如计算第五项，那么要重新计算第四项和第三项，计算第四项又要计算第三项和第二项
但是之前第四项和第三项都已经计算过了，为了除掉这些重复计算，用一个数组把之前计算过的都保存起来：

因为已经知道不会溢出，所以这里就改用int了
去掉重复运算后，运行时间可以忽略
这是我比较喜欢的解法，代码的含义一眼就能看出来，如果问题还要求小于45的其他项，可以直接在这个数组中查询

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.   int i;
   
6.   int fib[45 + 1];
   
7.   fib[1] = 1;
   
8.   fib[2] = 1;
   
9.   for(i = 3; i != 45+1; ++i)
   
10.     fib[i] = fib[i-1] + fib[i-2];
    
11.   printf("%d\n", fib[45]);
    
12.   return 0;
    
13. }

复制代码

当然，递归也是可以的，用函数的参数来保存前两项，从而避免重复运算
但是对于C和其他命令式语言而言，递归的写法没有那么自然，运行效率也必然低一些（这个问题上看不出）

1. #include <stdio.h>
   
2. 
   
3. int fib(int);
   
4. int _fib(int, int, int, int);
   
5. 
   
6. int main()
   
7. {
   
8.   printf("%d\n", fib(45));
   
9.   return 0;
   
10. }
    
11. 
    
12. int fib(int n)
    
13. {
    
14.   if(n == 1 || n == 2)
    
15.     return 1;
    
16.   return _fib(1, 1, 1, n-2);
    
17. }
    
18. 
    
19. int _fib(int a, int b, int n, int des)
    
20. {
    
21.   if(n == des)
    
22.     return a+b;
    
23.   else
    
24.     return _fib(b, a+b, n+1, des);
    
25. }

复制代码

最后，如果要尽可能地节省内存，而且只要求45项这一个解，可以这么写

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.   int a = 1;
   
6.   int b = 1;
   
7.   int pos = 3;
   
8.   while(pos <= 45){
   
9.     b = a + b;
   
10.     a = b - a;
    
11.     pos += 1;
    
12.   }
    
13.   printf("%d\n", b);
    
14.   return 0;
    
15. }
    

复制代码

为什么？因为计算第n项，只需要第n-1项和第n-2项，所以无论何时保存两项就够了

最后，求斐波那契数列的第n项可以转化为矩阵乘法，((0 1) (1 1)) ^( n - 2 )
因为乘方可以二分计算，对于大数来说是最理想的方法
但对于这道题目中的小数字，矩阵乘法反而会慢一点，而且代码也会复杂很多
对于这个问题，代码4是最佳解法