新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     >>计算机科学论坛<<     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [第五周第三帖]介绍一个高效求解Fibonacci数列的递归算法 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 18935 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [第五周第三帖]介绍一个高效求解Fibonacci数列的递归算法 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     apolor 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：39
      积分：382
      门派：XML.ORG.CN
      注册：2006/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给apolor发送一个短消息 把apolor加入好友 查看apolor的个人资料 搜索apolor在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看apolor的博客楼主
    发贴心情 [第五周第三帖]介绍一个高效求解Fibonacci数列的递归算法

    通常，我们在递归求解Fibonacci数列时，常感到递归效率的低下。因为我们容易写出如下递归算法：

    [算法一]
    int    Fib(n){
        if(n < 2)
            return n;
        else
            return (Fib(n-1) + Fib(n-2));
    }

    该算法效率确实很低，因为Fib(n-1)与Fib(n-2)做了许多重复计算。但是如果换一种方式使用递归，效率会高得多。

    [算法二]
    int    Fib(n){
        return AddSeq(n, 1, 1);
    }
    int    AddSeq(int n, int t0, int t1){
        if(0 == n)
            return t0;
        if(1 == n)
            return t1;
        return AddSeq(n-1, t1, t0+t1);
    }

    使用算法二，例如我们要求解Fib(5)，求解过程如下：
       AddSeq(5, 1, 1)
    →AddSeq(4, 1, 2)
    →AddSeq(3, 2, 3)
    →AddSeq(2, 3, 5)
    →AddSeq(1, 5, 8)   =>Fib(5) = 8
    只需5次递归即可求得结果。而算法一需要13次递归才可以求得结果。实际上，算法一的时间复杂度为指数级的，而算法二的时间复杂度是O(n)。孰优孰劣，效果立现。

    结论与启示：并不是递归的效率低，而是我们使用递归的方式使其变得效率低下。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/28 23:27:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第2楼
    发贴心情 
    有意思。：）

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/29 1:54:00
     
     淘客 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究C++)
      文章：33
      积分：211
      门派：XML.ORG.CN
      注册：2006/4/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给淘客发送一个短消息 把淘客加入好友 查看淘客的个人资料 搜索淘客在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看淘客的博客第3楼
    发贴心情 


              不错不错

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/29 12:11:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第4楼
    发贴心情 
    好！

    递归确实难！我的递归能力还需要提高。。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/29 22:35:00
     
     apolor 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：39
      积分：382
      门派：XML.ORG.CN
      注册：2006/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给apolor发送一个短消息 把apolor加入好友 查看apolor的个人资料 搜索apolor在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看apolor的博客第5楼
    发贴心情 
    有老师说一切非递归都是对递归的剖析，能用非递归实现的就一定能用递归实现（不知道是不是真的可以，没有研究过），递归思维简洁、直观，所以答题时最好用递归来写，这样思路会比较清晰。

    推荐一本讲解递归的书：

    ISBN:  7111137884  
    个人著者:  Roberts, Eric S.  
    题名:  Programming abstractions in C : a second course in computer science = C程序设计的抽象思维 / Eric S. Roberts 著.  
    出版信息:  Beijing : China Machine Press, 2004.  
    稽核项:  xx, 819 p. : ill. ; 24 cm.

    上面的方法就是在该书中看到的，该书用了好几章的篇幅来讲解递归，而且对递归讲解得极为深入。如果要培养递归能力，该书值得一读。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/29 23:23:00
     
     runningwulf 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：33
      积分：201
      门派：XML.ORG.CN
      注册：2006/5/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给runningwulf发送一个短消息 把runningwulf加入好友 查看runningwulf的个人资料 搜索runningwulf在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看runningwulf的博客第6楼
    发贴心情 
    还真有点意思，不过好像是用递归总会用到入栈出栈操作的，个人认为效率最高的还是用循环吧，虽然也是O(n)的复杂度。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/29 23:50:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第7楼
    发贴心情 
    以下是引用apolor在2006-9-28 23:27:00的发言：
    通常，我们在递归求解Fibonacci数列时，常感到递归效率的低下。因为我们容易写出如下递归算法：

    [算法一]
    int    Fib(n){
         if(n < 2)
             return n;
         else
             return (Fib(n-1) + Fib(n-2));
    }

    该算法效率确实很低，因为Fib(n-1)与Fib(n-2)做了许多重复计算。但是如果换一种方式使用递归，效率会高得多。

    [算法二]
    int    Fib(n){
         return AddSeq(n, 1, 1);
    }
    int    AddSeq(int n, int t0, int t1){
         if(0 == n)
             return t0;
         if(1 == n)
             return t1;
         return AddSeq(n-1, t1, t0+t1);
    }

    使用算法二，例如我们要求解Fib(5)，求解过程如下：
        AddSeq(5, 1, 1)
    →AddSeq(4, 1, 2)
    →AddSeq(3, 2, 3)
    →AddSeq(2, 3, 5)
    →AddSeq(1, 5, 8)   =>Fib(5) = 8
    只需5次递归即可求得结果。而算法一需要13次递归才可以求得结果。实际上，算法一的时间复杂度为指数级的，而算法二的时间复杂度是O(n)。孰优孰劣，效果立现。

    结论与启示：并不是递归的效率低，而是我们使用递归的方式使其变得效率低下。



    我晕，那还不如这样：
    int fib(int n){
        vector<int>m(n+1);
        m[0]=0;
        m[1]=1;
        for(int i=2;i<=n;++i)
            m[i]=m[i-1]+m[i-2];
        return m[n];
    }
    同样是O(n)级，同样使用O(n)级空间（不要跟我说你不知道为什么你的程序也用了O(n)级空间）
    总之，我觉得你们学校没开过算法课，至少你们几个都不知道什么叫动态规划，（别怪我措辞尖锐）呵呵：）
    fibnacci问题其实是等价与“爬楼梯问题的”（即：一共n阶台阶，一次一步或一次两步共有多少种上楼法），而动态规划的初衷就是防止重复计算递归中出现的重复子问题，因此递归问题是指数级而动态规划是多项式级的……
    不过好在pkuDS不怎么考算法，要像sjtu那样可就难了。

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/30 17:52:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第8楼
    发贴心情 
    以下是引用teng_t1986在2006-9-30 17:52:00的发言：
    我晕，那还不如这样：
    int fib(int n){
         vector<int>m(n+1);
         m[0]=0;
         m[1]=1;
         for(int i=2;i<=n;++i)
             m[i]=m[i-1]+m[i-2];
         return m[n];
    }
    同样是O(n)级，同样使用O(n)级空间（不要跟我说你不知道为什么你的程序也用了O(n)级空间）
    总之，我觉得你们学校没开过算法课，至少你们几个都不知道什么叫动态规划，（别怪我措辞尖锐）呵呵：）
    fibnacci问题其实是等价与“爬楼梯问题的”（即：一共n阶台阶，一次一步或一次两步共有多少种上楼法），而动态规划的初衷就是防止重复计算递归中出现的重复子问题，因此递归问题是指数级而动态规划是多项式级的……
    不过好在pkuDS不怎么考算法，要像sjtu那样可就难了。


    呵呵，楼主有没有学过DP我不知道。
    不过递归算法有其理论上和形式上的简洁性。
    在做算法正确性证明时，递归程序的证明显然要容易和直观得多。

    在讨论算法（注意是算法，不是代码）的时候，我觉得大家可能还是更倾向于用递归的方法去描述一个算法（至于实现时，如果在乎递归的效率问题，可以改成非递归实现就是了）。我记得Bruce Eckel说过，First make it work, then make it fast。
    用递归来讨论正确性，然后再用非递归来优化实现，这种方法在讨论复杂的（从而不容易立即判断其思路的正确性的）算法时好像更有效一些。

    我觉得楼主写的程序主要是给出一种利用参数来改变递推程序的behaviour的一种思路而已。
    如果只是追求复杂度低，当然大家都知道，求Fibonacci最快的方法是直接用通项公式。
    用递推公式的算法里复杂度最低的也应该是一个循环体内把两个临时变量交替使用。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/1 0:50:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第9楼
    发贴心情 
    说明一下：是这样的，楼主的解法二就是dp，是dp的记忆化搜索形式，我的程序也是dp，是dp的顺推形式，fibnacci问题是子问题规模为n的典型dp问题。
    至于利用参数来改变递推程序，既然原理一样也就没什么可说的了，好比设计外表不同机理相同的产品……

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/1 11:49:00
     
     apolor 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：39
      积分：382
      门派：XML.ORG.CN
      注册：2006/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给apolor发送一个短消息 把apolor加入好友 查看apolor的个人资料 搜索apolor在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看apolor的博客第10楼
    发贴心情 
    以下是引用teng_t1986在2006-10-1 11:49:00的发言：
    说明一下：是这样的，楼主的解法二就是dp，是dp的记忆化搜索形式，我的程序也是dp，是dp的顺推形式，fibnacci问题是子问题规模为n的典型dp问题。
    至于利用参数来改变递推程序，既然原理一样也就没什么可说的了，好比设计外表不同机理相同的产品……

    受教。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/1 22:43:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/4/23 18:37:57

    本主题贴数10，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 117.188ms