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

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

11609 人参与  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)了。
下例是一个简单的动态规划,以一定的空间代价避免代价更大的重复计算的栈空间浪费:

image.png

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

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

image.png

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

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

程序员面试  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

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

本站资源大部分来自互联网,版权归原作者所有!