找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1539|回复: 4

[分享] 求fibonacci数的高效递归算法

[复制链接]

已领礼包: 1857个

财富等级: 堆金积玉

发表于 2016-6-2 22:56:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
本帖最后由 aimisiyou 于 2016-6-4 00:06 编辑

;;;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)

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 40个

财富等级: 招财进宝

发表于 2016-6-3 12:17:34 | 显示全部楼层
你的代码不够高效吗?

点评

这是我在网上偶然看到的。说实话,可能大家都会写这个程序,觉得太简单了不屑一顾,但看到别人用递归算法做到这么高效,不得不让人佩服,所以我复制粘贴在这里供大家学习其算法!或许将来用得上。  详情 回复 发表于 2016-6-3 23:56
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 19个

财富等级: 恭喜发财

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

  1. 题目:定义Fibonacci数列如下:
  2.         /  0                      n=0
  3. f(n)=      1                      n=1
  4.         \  f(n-1)+f(n-2)          n=2

  5. 输入n,用最快的方法求该数列的第n项。
  6. 分析:第一种思路。如果使用递归的方法计算,每次都会重复计算之前计算过的f(n)的值,针对这种计算的重复问题,如果我们每次都记录之前计算过的的f(n)的值,就可以避免重复计算。上述方法的时间复杂度为o(n)。
  7. 第二种思路。上述算法还不是最快的计算方法。[f(n-1) f(n)] = A^(n-1)[f(1) f(0)],这个公式在这里不推导了,其中A=[1,1;1,0],使用矩阵的幂的快速算法,我们可以讲f(n)计算的时间复杂度降低到o(log(n))。
  8. 第一种思路的代码:

  9. int Fibonacci(int n){
  10. int result[2]={0,1};
  11. if(n<2)
  12. return result[n];
  13. int fibsum;
  14. int fibone = 1;
  15. int fibtwo = 0;
  16. for(int i=1;i<n-1;i++){
  17. fibsum = fibone + fibtwo;
  18. fibtwo = fibone;
  19. fibone = fibsum;
  20. }
  21. return fibsum;
  22. }
  23. 第二种思路的代码:

  24. #include <iostream>
  25. using namespace std;

  26. struct mx{
  27. int m,n;
  28. int matrix[2][2];
  29. };

  30. mx multiply(mx a,mx b){
  31. int i,j,k,s;
  32. mx ans={2,2,{0,0,0,0}};
  33. for(i=0;i<a.m;i++){
  34. for(j=0;j<b.n;j++){
  35. s = 0;
  36. for(k=0;k<a.n;k++)
  37. s += a.matrix[k]*b.matrix[k][j];
  38. ans.matrix[j] = s;
  39. }
  40. }
  41. return ans;

  42. }
  43. mx MatPow(mx a,int b){
  44. mx s={2,2,{1,0,0,1}};
  45. while(b){
  46. if(b&1)
  47. s = multiply(s,a);
  48. a = multiply(a,a);
  49. b>>=1;
  50. }
  51. return s;
  52. }
  53. int Fibonacci_Matrix(int n){
  54. mx s={2,2,{1,1,1,0}};
  55. s = MatPow(s,n-1);
  56. return s.matrix[0][0];
  57. }

  58. void main(){
  59. int n = 3;
  60. int m = Fibonacci_Matrix(n);
  61. cout<<m<<endl;
  62. system("pause");
  63. }

点评

该算法复杂度也是O(log(n))且代码简练!  详情 回复 发表于 2016-6-3 23:58
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2016-6-3 23:56:08 | 显示全部楼层
newer 发表于 2016-6-3 12:17
你的代码不够高效吗?


这是我在网上偶然看到的。说实话,可能大家都会写这个程序,觉得太简单了不屑一顾,但看到别人用递归算法做到这么高效,不得不让人佩服,所以我复制粘贴在这里供大家学习其算法!或许将来用得上。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2016-6-3 23:58:44 | 显示全部楼层
Lisphk 发表于 2016-6-3 13:50
下面算法的时间复杂度能到 ologn, 楼主试试改造下你的代码

该算法复杂度也是O(log(n))且代码简练!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-29 17:22 , Processed in 0.364449 second(s), 41 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表