二维码

斐波那契数列-编程求解方法大全 - 数据结构 - 机器学习

1289 人阅读 | 时间：2021年01月15日 01:22
斐波那契数列-编程求解方法大全 - 数据结构 - 机器学习 #daohang ul li t,.reed .riqi,a.shangg,a.xiatt,a.shangg:hover,a.xiatt:hover,a.shang,a.xiat,a.shang:hover,a.xiat:hover,.reed-pinglun-anniu,span.now-page,#daohangs-around,#caidan-tubiao,#daohangs,#daohangs li,#btnPost{background-color:#D10B04;} .dinglanyou1 h3{border-bottom:3px solid #D10B04;} #dibuer{border-top:2px solid #D10B04;}.cebianlan .rongqi h3{border-bottom:1px solid #D10B04;} #edtSearch{border:1px solid #D10B04;} #daohang .zuo ul li{border-right:1px solid #;} #daohang ul li t a{border-top:1px solid #;border-right:1px solid #D10B04;} #daohang ul li t a:hover{border-right:1px solid #;} #daohang .you ul li a:hover,#daohang .zuo ul li a:hover,.reed-pinglun-anniu:hover{background-color:#;} a:hover,.reed h6 a:hover,#dibuer a:hover,.reed .riqiding,.cebianlan .rongqi li a:hover,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.shu a,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.huifuliuyan a:hover,.reed-biaoti h6 span{color:#D10B04;} .reed .kan a{color:#0A0AF5;}.reed .kan a:hover{color:#D10101;} @media screen and (max-width:1492px){a.shang,a.xiat{background:none;} a.xiat:hover,a.shang:hover{background-color:#f9f9f9;background-image:none;text-decoration:none;}} var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?2d748c9763cfc72fb7d1ccab29f0770d"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?f6d451f3f1be23f3abf240c64c469c1b"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })();

当前位置：首页 » 面试笔试 » 正文

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646201", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646162", container: s }); })();

斐波那契数列-编程求解方法大全

12650 人参与  2019年03月15日 10:51  分类 : 面试笔试  评论

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

直接上我的代码：

int Fibonacci(int n) {
        int sum =0,l=0,r=1;
        if(n==1)
            return 1;
        else
        {
            for(int i=0;i<n-1;i++)
            {
                sum=l+r;
                l=r;
                r=sum;
            }
        }
        return sum;
    }



这个题可以说是迭代（Iteration） VS 递归（Recursion），

f(n) = f(n-1) + f(n-2)，第一眼看就是递归啊，简直完美的递归环境，递归肯定很爽，这样想着关键代码两三行就搞定了，注意这题的n是从0开始的：
1
2
if(n<=1) return n;
else return Fibonacci(n-1)+Fibonacci(n-2);
然而并没有什么用，测试用例里肯定准备着一个超大的n来让Stack  Overflow，为什么会溢出？因为重复计算，而且重复的情况还很严重，举个小点的例子，n=4，看看程序怎么跑的：
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
                    = Fibonacci(2) + Fibonacci(1) + Fibonacci(1)  + Fibonacci(0);
                    = Fibonacci(1) + Fibonacci(0) + Fibonacci(1)  + Fibonacci(1) + Fibonacci(0);
由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果，对于程序来说它每次递归都是未知的，因此光是n=4时f(1)就重复计算了3次之多。
那么如何求解呢，动态规划似乎不错，关于动态规划三个条件：最优子结构、无后效性、子问题重叠这些就不谈了，因为理(wo)论(ye)性(bu)太(tai)强(dong)了。
下例是一个简单的动态规划，以一定的空间代价避免代价更大的重复计算的栈空间浪费：

斐波那契数列-编程求解方法大全 - 数据结构 - 机器学习

虽然看起来很蠢，空间浪费了sizeof(int)*(n-1)，但是对于那个超大n的测试用例应该是可以通过了，时间复杂度也达到了O(n)。

那能不能把“优雅”的递归和动态规划结合起来呢？递归的优点在于便于理解和编码，而重复计算的关键原因在于代码里直接就“递”进去然后等着“归”了，所以避免重复的关键在于对子问题是否已经得出解的判断，即：

斐波那契数列-编程求解方法大全 - 数据结构 - 机器学习

对于这种有很小范围内的计算，我们可以更暴力一点的。像下面这样：

public class Solution {
   public static int Fibonacci(int n) {
        int[] ns = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,
                 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,
                 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986};
         return ns[n];
     }
}

另类解法：

public int Fibonacci(int n) {
     if (n==0) return 0;
     if (n <= 2) {
          return 1;
      }
      if (n == 3)
          return 2;
      int n1 = 1;
      int n2 = 2;
      for (int i = 4; i <= n; i++) {
          n1 ^= n2;
          n2 ^= n1;
          n1 ^= n2;
          n2 += n1;

 

      }
      return n2;
  }

代码量最少的解法：

public class Solution {
    public int Fibonacci(int n) {
        return n<=0 ? 0 :n<=2 ? 1 : Fibonacci(n-1) + Fibonacci(n-2);
    }
}
简单粗暴，拿走不谢！

下面这几个解法最牛逼，汇总了，真是逆天的操作：

// 遍历求解
function Fibonacci(n)
{
    var pre = 0;
    var num = 0;
    while (n > 0) {
        if (num == 0) {
            num = 1;
        } else {
            var tmp = num;
            num += pre;
            pre = tmp;
        }
 
        n--;
    }
 
    return num;
}
 
// 暴力求解
function Fibonacci2(n)
{
    var arr = [0,1,1,2,3,5,8,13,21,34,55,89,
    144,233,377,610,987,1597,2584,4181,6765,
    10946,17711,28657,46368,75025,
    121393,196418,317811,514229,832040,
    1346269,2178309,3524578,5702887,9227465,
    14930352,24157817,39088169,63245986];
    return arr[n];
}
 
// 通项公式求解
function Fibonacci3(n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;
 
    var sqrt5 = Math.sqrt(5);
    var result = 1 / sqrt5 * (Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n));
    return Math.round(result);
}


来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=1232

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
程序员面试  

微信号：qq444848023    QQ号：444848023

加入【我是码农】QQ群：864689844（加群验证：我是码农）

<< 上一篇 下一篇 >>
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646186", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646175", container: s }); })();
搜索

网站分类

标签列表

最近发表

    (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https'){ bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else{ bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！

jQuery(document).ready(function($){ /* prepend menu icon */ $('#daohangs-around').prepend('
'); /* toggle nav */ $("#caidan-tubiao").on("click", function(){ $("#daohangs").slideToggle(); $(this).toggleClass("active"); }); });

©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任 来源：ZhiKuGroup博客，欢迎分享。

评论专区
  • 昵 称必填
  • 邮 箱选填
  • 网 址选填
  • 验证码
◎已有 0 人评论
相关文章
搜索
作者介绍
superadmin

superadmin

30天热门
热评文章
最近发表
标签列表

©2012-2022 Think tank 鄂ICP备19030179号-1 | 使用Chrome浏览本站最佳 | 声明：本站的文章和资源来自互联网或者站长的原创，按照 CC BY -NC -SA 3.0 CN协议发布和共享，转载或引用本站文章应遵循相同协议。 如果有侵犯版权的资源请尽快联系站长，我们会在24h内删除有争议的资源； 本站所有收费以及免费的信息和数据仅供参考，不构成投资建议，本网站不承担由此导致的任何责任。
登陆

Powered By Z-BlogPHP

本站会员尊享VIP特权，现在就加入我们吧！登录注册×
»
会员登录
新用户注册
×
会员注册
已有账号登录
×