求fibonacci数的高效递归算法

aimisiyou

;;;https://www.felix021.com/blog/read.php?2111
;;;f(0)=0;f(1)=1;f(2)=1;f(3)=2;f(n)=f(n-1)+f(n-2),求f(n)=?
(defun f(n)  
   (defun  ff(a b p q n)      
          (if (= n 0)
              (setq va b)           
              (progn
                  (if (= (rem n 2) 0)
                      (setq va (ff a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ n 2)) )
                      (setq va (ff (+ (* a p) (* a q) (* b q)) (+ (* a q) (* b p)) p q (- n 1)) )
                   )
               )
           )
     )
(ff 1 0 0 1 n)
)
(f 100)

newer

你的代码不够高效吗？

Lisphk

下面算法的时间复杂度能到 ologn, 楼主试试改造下你的代码

1. 题目：定义Fibonacci数列如下：
   
2.         /  0                      n=0
   
3. f(n)=      1                      n=1
   
4.         \  f(n-1)+f(n-2)          n=2
   
5. 
   
6. 输入n，用最快的方法求该数列的第n项。
   
7. 分析：第一种思路。如果使用递归的方法计算，每次都会重复计算之前计算过的f(n)的值，针对这种计算的重复问题，如果我们每次都记录之前计算过的的f(n)的值，就可以避免重复计算。上述方法的时间复杂度为o(n)。
   
8. 第二种思路。上述算法还不是最快的计算方法。[f(n-1) f(n)] = A^(n-1)[f(1) f(0)]，这个公式在这里不推导了，其中A=[1,1;1,0]，使用矩阵的幂的快速算法，我们可以讲f(n)计算的时间复杂度降低到o(log(n))。
   
9. 第一种思路的代码：
   
10. 
    
11. int Fibonacci(int n){
    
12. int result[2]={0,1};
    
13. if(n<2)
    
14. return result[n];
    
15. int fibsum;
    
16. int fibone = 1;
    
17. int fibtwo = 0;
    
18. for(int i=1;i<n-1;i++){
    
19. fibsum = fibone + fibtwo;
    
20. fibtwo = fibone;
    
21. fibone = fibsum;
    
22. }
    
23. return fibsum;
    
24. }
    
25. 第二种思路的代码：
    
26. 
    
27. #include <iostream>
    
28. using namespace std;
    
29. 
    
30. struct mx{
    
31. int m,n;
    
32. int matrix[2][2];
    
33. };
    
34. 
    
35. mx multiply(mx a,mx b){
    
36. int i,j,k,s;
    
37. mx ans={2,2,{0,0,0,0}};
    
38. for(i=0;i<a.m;i++){
    
39. for(j=0;j<b.n;j++){
    
40. s = 0;
    
41. for(k=0;k<a.n;k++)
    
42. s += a.matrix[k]*b.matrix[k][j];
    
43. ans.matrix[j] = s;
    
44. }
    
45. }
    
46. return ans;
    
47. 
    
48. }
    
49. mx MatPow(mx a,int b){
    
50. mx s={2,2,{1,0,0,1}};
    
51. while(b){
    
52. if(b&1)
    
53. s = multiply(s,a);
    
54. a = multiply(a,a);
    
55. b>>=1;
    
56. }
    
57. return s;
    
58. }
    
59. int Fibonacci_Matrix(int n){
    
60. mx s={2,2,{1,1,1,0}};
    
61. s = MatPow(s,n-1);
    
62. return s.matrix[0][0];
    
63. }
    
64. 
    
65. void main(){
    
66. int n = 3;
    
67. int m = Fibonacci_Matrix(n);
    
68. cout<<m<<endl;
    
69. system("pause");
    
70. }
    

题目：定义Fibonacci数列如下： <br />         /  0                      n=0<br /> f(n)=      1                      n=1<br />         \  f(n-1)+f(n-2)          n=2<br /> <br /> 输入n，用最快的方法求该数列的第n项。<br /> 分析：第一种思路。如果使用递归的方法计算，每次都会重复计算之前计算过的f(n)的值，针对这种计算的重复问题，如果我们每次都记录之前计算过的的f(n)的值，就可以避免重复计算。上述方法的时间复杂度为o(n)。<br /> 第二种思路。上述算法还不是最快的计算方法。[f(n-1) f(n)] = A^(n-1)[f(1) f(0)]，这个公式在这里不推导了，其中A=[1,1;1,0]，使用矩阵的幂的快速算法，我们可以讲f(n)计算的时间复杂度降低到o(log(n))。<br /> 第一种思路的代码：<br /> <br /> int Fibonacci(int n){<br /> int result[2]={0,1};<br /> if(n<2)<br /> return result[n];<br /> int fibsum;<br /> int fibone = 1;<br /> int fibtwo = 0;<br /> for(int i=1;i<n-1;i++){<br /> fibsum = fibone + fibtwo;<br /> fibtwo = fibone;<br /> fibone = fibsum;<br /> }<br /> return fibsum;<br /> }<br /> 第二种思路的代码：<br /> <br /> #include <iostream><br /> using namespace std;<br /> <br /> struct mx{<br /> int m,n;<br /> int matrix[2][2];<br /> };<br /> <br /> mx multiply(mx a,mx b){<br /> int i,j,k,s;<br /> mx ans={2,2,{0,0,0,0}};<br /> for(i=0;i<a.m;i++){<br /> for(j=0;j<b.n;j++){<br /> s = 0;<br /> for(k=0;k<a.n;k++)<br /> s += a.matrix<i>[k]*b.matrix[k][j];<br /> ans.matrix<i>[j] = s;<br /> }<br /> }<br /> return ans;<br /> <br /> }<br /> mx MatPow(mx a,int b){<br /> mx s={2,2,{1,0,0,1}};<br /> while(b){<br /> if(b&1)<br /> s = multiply(s,a);<br /> a = multiply(a,a);<br /> b>>=1;<br /> }<br /> return s;<br /> }<br /> int Fibonacci_Matrix(int n){<br /> mx s={2,2,{1,1,1,0}};<br /> s = MatPow(s,n-1);<br /> return s.matrix[0][0];<br /> }<br /> <br /> void main(){<br /> int n = 3;<br /> int m = Fibonacci_Matrix(n);<br /> cout<<m<<endl;<br /> system("pause");<br /> }<br />

aimisiyou

newer 发表于 2016-6-3 12:17
你的代码不够高效吗？

这是我在网上偶然看到的。说实话，可能大家都会写这个程序，觉得太简单了不屑一顾，但看到别人用递归算法做到这么高效，不得不让人佩服，所以我复制粘贴在这里供大家学习其算法！或许将来用得上。

aimisiyou

Lisphk 发表于 2016-6-3 13:50
下面算法的时间复杂度能到 ologn, 楼主试试改造下你的代码

该算法复杂度也是O（log（n））且代码简练！