斐波纳契数列的算法函数

Question

我不一定要找答案,但我正在寻找这个问题的要求.发现这个问题正在学习面试,但不确定他们在问什么？

编写通过斐波那契序列运行并返回传递作为参数的指数函数.

Answer 1

首先,您可以使用wiki中的此链接更新有关Fibonacci的基础数学信息.并查看此公式以进行快速计算.您可以在此链接中阅读所有相关内容.

这是计算第n个Fibonacci数的递归函数,并且是O(2 ^ n)时间:

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

计算序列

您可能会争辩说,就计算机上实际计算Fibonacci序列的值而言,最好使用原始递归关系f [n] = f [n-1] + f [n-2].我倾向于同意.要对大n使用直接闭合形式的解决方案,您需要保持很高的精度.即使输出9位小数,例如,fn≈round(0.723606798⋅(1.618033989)n)仅对n = 38有效(此处与此处相比).此外,添加整数比计算符号分数或浮点值的计算成本更低且更精确

这是计算第n个Fibonacci数并且是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个Fibonacci数的最佳方法,并且是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被认为是常数时).

对于Fibonacci重复,还有一个封闭的公式解决方案,请参见http://en.wikipedia.org/wiki/Fibonacci_number,查找Binet或Moivre的公式.

并看一下:在次线性时间内的第 1 个斐波纳契数

Answer 2

在我看来,你被要求返回第n个斐波纳契号,其中n是传递的参数.您可以使用各种方法来回答这个问题,而所有这些方法的时间复杂度和代码复杂性都各不相同.

方法1(使用递归)一种简单的方法,它是上面给出的直接recusrive实现数学恢复关系.

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个Fibonacci数是一个糟糕的实现.

                     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)如果我们考虑fuinction调用堆栈大小,否则O(1).

方法2(使用动态编程)我们可以通过存储到目前为止计算的斐波那契数来避免重复的工作是方法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)我们可以通过存储前两个数字来优化方法2中使用的空间,因为这就是我们需要获得的下一个Fibannaci数.

 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)

方法4(使用matrx {{1,1},{0,1}}的幂)这另一个O(n)依赖于如果我们n倍乘矩阵M = {{1,1}, {0,1}}自身(换句话说,计算功率(M,n)),然后我们得到第(n + 1)个斐波纳契数作为结果矩阵中行和列(0,0)的元素.

矩阵表示为Fibonacci数提供以下闭合表达式:

  /* 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)时间复杂度下工作.我们可以进行递归乘法来获得流行方法中的幂(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(); 返回0; }

参考文献:http : //en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html