斐波那契数列的算法函数

Question

斐波那契数列的算法函数

algorithmfibonacci

8

我并不是在寻找答案，而是想知道这个问题要求什么。我在为面试学习时发现了这个问题，但不确定他们想问什么?

编写一个函数，遍历斐波那契数列并返回作为参数传递的索引。

- KingKongFrog

啊……这样就清楚多了。谢谢。 - KingKongFrog

你读了我的答案吗？ - amin k

假设给定索引_i_。a) 运行斐波那契数列：1 1（它没有说明要运行多远或为什么？）b) 返回_i_。 - greybeard

5个回答

12

我觉得你被要求返回第n个斐波那契数，其中n是传递的参数。您可以使用各种方法来回答此问题，这些方法在时间复杂度和代码复杂度方面都有所不同。

方法1（使用递归）一种简单的方法是直接实现上述数学递推关系的递归实现。

int fib(int n)
{
    if ( n <= 1 )
    return n;
    return fib(n-1) + fib(n-2);
}

时间复杂度：T(n) = T(n-1) + T(n-2)，呈指数级增长。我们可以观察到，该实现会进行大量的重复计算（请见下方递归树）。因此，这是一个求解第n个斐波那契数的糟糕实现。

                     fib(5)   
                 /             \     
           fib(4)                fib(3)   
         /      \                /     \
     fib(3)      fib(2)         fib(2)    fib(1)
    /     \        /    \       /    \

fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0) 如果我们考虑函数调用栈的大小，那么额外空间为O(n)，否则为O(1)。

方法二（使用动态规划）我们可以通过存储到目前为止计算出的斐波那契数列来避免方法一中重复的工作。

int fib(int n)
{
     /* Declare an array to store fibonacci numbers. */
      int f[n+1];
      int i;

     /* 0th and 1st number of the series are 0 and 1*/
     f[0] = 0;
     f[1] = 1;

    for (i = 2; i <= n; i++)
    {
       /* Add the previous 2 numbers in the series
        and store it */
       f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

时间复杂度：O(n) 额外空间：O(n)

方法3（空间优化方法2）我们可以通过仅存储前两个数字来优化第二种方法中使用的空间，因为这是我们需要获取系列中下一个斐波那契数的所有内容。

 int fib(int n)
 {
      int a = 0, b = 1, c, i;
      if( n == 0)
       return a;
      for (i = 2; i <= n; i++)
      {
        c = a + b;
        a = b;
       b = c;
    }
    return b;
  }

时间复杂度：O(n) 额外空间：O(1)

方法四（使用矩阵{{1,1},{0,1}}的幂）这是另一种O(n)的方法，它依赖于一个事实，即如果我们将矩阵M = {{1,1},{0,1}}自乘n次（换句话说，计算power(M,n)），那么我们可以得到第(n+1)个斐波那契数作为结果矩阵中行和列（0,0）处的元素。

矩阵表示法给出了以下斐波那契数的闭式表达式：

  /* Helper function that multiplies 2 matricies F and M of size 2*2, and
    puts the multiplication result back to F[][] */
  void multiply(int F[2][2], int M[2][2]);

  /* Helper function that calculates F[][] raise to the power n and puts the
    result in F[][]
    Note that this function is desinged only for fib() and won't work as general
    power function */
  void power(int F[2][2], int n);

  int fib(int n)
  {
    int F[2][2] = {{1,1},{1,0}};
    if(n == 0)
        return 0;
    power(F, n-1);

    return F[0][0];
  }

  void multiply(int F[2][2], int M[2][2])
  {
    int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
    int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
    int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
    int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
  }

  void power(int F[2][2], int n)
  {
    int i;
    int M[2][2] = {{1,1},{1,0}};

    // n - 1 times multiply the matrix to {{1,0},{0,1}}
    for ( i = 2; i <= n; i++ )
        multiply(F, M);
  }

时间复杂度：O(n) 额外空间：O(1)

方法5（优化方法4）方法4可以优化为O(Logn)的时间复杂度。我们可以使用递归乘法来获得前面方法中的power(M，n)（类似于本文中所做的优化）。

  void multiply(int F[2][2], int M[2][2]);

  void power(int F[2][2], int n);

  /* function that returns nth Fibonacci number */
  int fib(int n)
  {
    int F[2][2] = {{1,1},{1,0}};
    if(n == 0)
      return 0;
    power(F, n-1);
    return F[0][0];
  }

  /* Optimized version of power() in method 4 */
  void power(int F[2][2], int n)
  {
    if( n == 0 || n == 1)
        return;
    int M[2][2] = {{1,1},{1,0}};

    power(F, n/2);
    multiply(F, F);

    if( n%2 != 0 )
       multiply(F, M);
  }

  void multiply(int F[2][2], int M[2][2])
  {
    int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
    int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
    int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
    int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
  }

时间复杂度：O(Logn) 额外空间：如果我们考虑函数调用堆栈大小，则为O(Logn)，否则为O(1)。

驱动程序： int main() { int n = 9; printf("%d", fib(9)); getchar(); return 0; }

References: http://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html

- Aman Chhabra

1

这是一个措辞非常不清晰的问题，但你需要假设他们正在询问提供参数n的第n个斐波那契数。

除了其他人列出的所有技术之外，对于n > 1，您还可以使用黄金分割法，这比任何迭代方法都要快。但是由于问题说“运行斐波那契序列”，这可能不符合条件。您可能还会吓到他们。

- user207421

0

public static int fibonacci(int i){
if(i==0)
  return 0;

if(i==1)
   return 1;
return fib(--i,0,1);
}


public static int fib(int num,int pre,int prepre){
   if(num==0){
    return prepre+pre;
   }
    return fib(--num,pre+prepre,pre);
}

- Dima

0

我对这个问题的理解有所不同...给定一个数字作为输入，该数字在序列中的索引是多少？例如，input=5，那么索引就是5（假设序列为0 1 1 2 3 5，其中索引从0开始）

以下是代码（返回索引）[免责声明：改编自http://talkbinary.com/programming/c/fibonacci-in-c/提供的代码]

int Fibonacci(int n)
{
  if ( n == 0 )
    return 0;
  if ( n== 1 )
    return 1;

  int fib1 = 0; 
  int fib2 = 1;
  int fib = 0;
  int i = 0;

for (i = 2; ; i++ ) 
{

    fib = fib1 + fib2;
    if ( n == fib )
       break;
    fib1 = fib2;
    fib2 = fib;
}


  return i;
}

- Bill

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amin k · Accepted Answer

首先，你可以通过这个链接从维基百科了解并更新有关斐波那契数列的基本数学信息。然后，看一下这个公式以进行快速计算。你可以在这个链接上阅读有关它的所有内容。

这是一个递归函数来计算第n个斐波那契数，时间复杂度为O(2^n)：

 int Fibonacci(int n) {  
        if (n == 0 || n == 1)  return n;
        else
        return Fibonacci(n - 1) + Fibonacci(n - 2); }

计算序列

你可能会认为，在计算斐波那契数列的值时，使用原始递推关系 f[n]=f[n−1]+f[n−2] 更好。我倾向于同意这种观点。如果要使用针对大 n 的直接闭式解决方案，则需要保持很高的精度。例如，即使截取小数点后 9 位，fn≈round(0.723606798⋅(1.618033989)n)，也只在n=38时有效（见这里和这里）。此外，添加整数比乘以符号分数或浮点值更具有计算效率且更加精确。

这是计算第 n 个斐波那契数的更好方法，时间复杂度为 O(n)：

int Fibonacci(int n) { 
if(n <= 0) return 0;
if(n > 0 && n < 3) return 1;

int result = 0;
int preOldResult = 1;
int oldResult = 1;

for (int i=2;i<n;i++) { 
    result = preOldResult + oldResult;
    preOldResult = oldResult;
    oldResult = result;
}

return result;}

这是计算第n个斐波那契数列的最佳方法，时间复杂度为O(log(n))：

链接

正如您已经猜测的那样，它的工作方式非常相似。使用x * x矩阵的n次幂。

|1 0 0 0  .... 1 1|
|1 
|  1
|    1
|      1
|        1
...................
...................
|          ... 1 0|

如果您将此矩阵与向量相乘，那么这将变得容易理解。

f(n-1), f(n-2), ... , f(n-x+1), f(n-x)

导致

f(n), f(n-1), ... , f(n-x+1)

矩阵指数可以在O(log(n))的时间内完成计算（当x被认为是常数时）。

对于斐波那契递归序列，也存在一个闭式解，可以在这里查看：http://en.wikipedia.org/wiki/Fibonacci_number，查找Binet或Moivre公式。

并参考以下链接： 1-nth fibonacci number in sublinear time