如何更快地生成斐波那契数

Question

我是一名 CSE 学生，正在为编程竞赛做准备。现在我正在研究斐波那契数列。我有一个大小约为几千字节的输入文件，其中包含正整数。输入格式看起来像

3 5 6 7 8 0

一个零意味着文件结束。输出应该像

2 
5 
8 
13 
21 

我的代码

#include<stdio.h>

int fibonacci(int n) {
  if (n==1 || n==2)
    return 1;
  else
    return fibonacci(n-1) +fibonacci(n-2);
}
int main() {
  int z;
  FILE * fp;    
  fp = fopen ("input.txt","r");    
  while(fscanf(fp,"%d", &z) && z) 
   printf("%d \n",fibonacci(z));
  return 0;
}

一样该代码适用于示例输入并提供准确的结果，但问题是对于我的真实输入集，它花费的时间比我的时间限制更多。谁能帮我一下。

Answer 1

如果内存有限，您可以简单地使用函数的尾递归版本，该函数返回最后两个斐波那契数。

int fib(int n)
{
    int a = 0;
    int b = 1;
    while (n-- > 1) {
        int t = a;
        a = b;
        b += t;
    }
    return b;
}

这是 O(n) 并且需要一个常量空间。

Answer 2

您可能应该研究一下记忆​​。

http://en.wikipedia.org/wiki/Memoization

它有一个解释和一个谎言示例就在那里

Answer 3

您可以通过矩阵乘法来完成此操作，将矩阵求 n 次方，然后乘以一个向量。您可以在对数时间内将其提高功率。

我认为您可以在此处找到问题。它是罗马尼亚语，但您可以使用谷歌翻译进行翻译。这正是您想要的，并且解决方案已列在此处。

Answer 4

您的算法是递归的，并且大约具有 O(2^N) 复杂度。

这个问题之前在stackoverflow上讨论过：
斐波那契数列的计算复杂性

在该特定讨论中还发布了更快的实现。

Answer 5

看看维基百科，有一个公式给出了斐波那契数列中的数字，没有递归全部

Answer 6

使用记忆。也就是说，您缓存答案以避免不必要的递归调用。

这是一个代码示例：

#include <stdio.h>

int memo[10000]; // adjust to however big you need, but the result must fit in an int
                 // and keep in mind that fibonacci values grow rapidly :)

int fibonacci(int n) {
  if (memo[n] != -1)
    return memo[n];

  if (n==1 || n==2)
    return 1;
  else
    return memo[n] = fibonacci(n-1) +fibonacci(n-2);
}
int main() {
  for(int i = 0; i < 10000; ++i)
    memo[i] = -1;
  fibonacci(50);
}

Answer 7

没有人提到 2 值堆栈数组版本，所以我只是为了完整性而这样做。

// do not call with i == 0
uint64_t Fibonacci(uint64_t i)
{
  // we'll only use two values on stack,
  // initialized with F(1) and F(2)
  uint64_t a[2] = {1, 1};

  // We do not enter loop if initial i was 1 or 2 
  while (i-- > 2)
    // A bitwise AND allows switching the storing of the new value
    // from index 0 to index 1.
    a[i & 1] = a[0] + a[1];

    // since the last value of i was 0 (decrementing i),
    // the return value is always in a[0 & 1] => a[0].
  return a[0];
}                                                                

这是一个 O(n) 常量堆栈空间解决方案，在优化编译时其执行效果与记忆化略有相同。

// Calc of fibonacci f(99), gcc -O2
Benchmark            Time(ns)    CPU(ns) Iterations
BM_2stack/99                2          2  416666667
BM_memoization/99           2          2  318181818

这里使用的 BM_memoization 只会初始化数组一次，并在每次其他调用中重用它。

优化后，2 值堆栈数组版本的性能与带有临时变量的版本相同。

Answer 8

您还可以使用生成斐波那契数列的快速倍增方法
链接： fastest-way-to-compute -fibonacci-number

它实际上是由矩阵求幂方法的结果推导出来的。

Answer 9

使用黄金比例

Answer 10

构建一个数组 Answer[100]，在其中缓存 fibonacci(n) 的结果。
检查您的斐波那契代码，看看您是否已预先计算出答案，并且
使用该结果。结果会让你大吃一惊。

Answer 11

您是否保证，如您的示例所示，输入将按升序提供给您？如果是这样，你甚至不需要记忆；只需跟踪最后两个结果，开始生成序列，但如果 N 是输入中的下一个索引，则仅显示序列中的第 N 个数字。当你达到索引 0 时停止。

类似这样的事情：

int i = 0;
while ( true ) {
    i++; //increment index
    fib_at_i = generate_next_fib()
    while ( next_input_index() == i ) {
        println fib_at_i
}

我留下退出条件并实际为你生成序列。

Answer 12

在 C# 中：

        static int fib(int n)
        {
            if (n < 2) return n;
            if (n == 2) return 1;
            int k = n / 2;
            int a = fib(k + 1);
            int b = fib(k);
            if (n % 2 == 1)
                return a * a + b * b;
            else
                return b * (2 * a - b);
        }

Answer 13

矩阵乘法，无浮点运算，O(log N) 时间复杂度（假设整数乘法/加法在恒定时间内完成）。

这是Python代码

def fib(n):
    x,y = 1,1
    mat = [1,1,1,0]
    n -= 1
    while n>0:
        if n&1==1:
            x,y = x*mat[0]+y*mat[1], x*mat[2]+y*mat[3]
        n >>= 1
        mat[0], mat[1], mat[2], mat[3] = mat[0]*mat[0]+mat[1]*mat[2], mat[0]*mat[1]+mat[1]*mat[3], mat[0]*mat[2]+mat[2]*mat[3], mat[1]*mat[2]+mat[3]*mat[3]
    return x

Answer 14

您可以减少 if 语句的开销： Calculate Fibonacci Numbers Recursively in C

Answer 15

首先，您可以使用 memoization 或同一算法的迭代实现。

考虑您的算法进行的递归调用次数：

fibonacci(n) 调用 fibonacci(n-1) 和 fibonacci(n-2)
fibonacci(n-1) 调用 fibonacci(n-2) 和 fibonacci(n-3)
fibonacci(n-2) 调用 fibonacci(n-3) 和 fibonacci(n-4)

注意到一个模式了吗？您计算同一函数的次数超出了需要的次数。

迭代实现将使用数组：

int fibonacci(int n) {
    int arr[maxSize + 1]; 
    arr[1] = arr[2] = 1; // ideally you would use 0-indexing, but I'm just trying to get a point across
    for ( int i = 3; i <= n; ++i )
        arr[i] = arr[i - 1] + arr[i - 2]; 

    return arr[n];
}

这已经比您的方法快得多。您可以按照相同的原则更快地完成此操作，只需构建一次数组，直到达到 n 的最大值，然后通过打印数组的元素在单个操作中打印正确的数字。这样您就不必为每个查询调用该函数。

如果您无法承担初始预计算时间（但这通常仅在您被要求对结果取模时才会发生，否则他们可能不希望您实现大数算术，而预计算是最好的解决方案），请阅读斐波那契维基页面了解其他方法。重点关注矩阵方法，在竞赛中了解该方法非常有用。

Answer 16

#include<stdio.h>

 int g(int n,int x,int y)
   {
   return n==0 ? x : g(n-1,y,x+y);}

 int f(int n)
   {
   return g(n,0,1);}

 int main (void)
   {  
   int i;
   for(i=1; i<=10 ; i++)
     printf("%d\n",f(i)
   return 0;
   }

Answer 17

在函数式编程中，有一种特殊的斐波那契计数算法。该算法使用累积递归。累积递归用于最小化算法使用的堆栈大小。我认为这会帮助你最大限度地减少时间。如果你愿意的话可以尝试一下。

int ackFib (int n, int m, int count){
    if (count == 0)
        return m;
    else
        return ackFib(n+m, n, count-1);
}



int fib(int n)
{
 return ackFib (0, 1, n+1);
}

Answer 18

使用以下任意一种：两个递归示例，一个使用 for 循环 O(n) 时间，一个使用黄金比例 O(1) 时间：

private static long fibonacciWithLoop(int input) {
    long prev = 0, curr = 1, next = 0;      
    for(int i = 1; i < input; i++){
        next = curr + prev;
        prev = curr;
        curr = next;
    }
    return curr;
}

public static long fibonacciGoldenRatio(int input) {
    double termA = Math.pow(((1 + Math.sqrt(5))/2), input);
    double termB = Math.pow(((1 - Math.sqrt(5))/2), input);
    double factor = 1/Math.sqrt(5);
    return Math.round(factor * (termA - termB));
}

public static long fibonacciRecursive(int input) {
    if (input <= 1) return input;
    return fibonacciRecursive(input - 1) + fibonacciRecursive(input - 2);
}

public static long fibonacciRecursiveImproved(int input) {
    if (input == 0) return 0;
    if (input == 1) return 1;
    if (input == 2) return 1;
    if (input >= 93) throw new RuntimeException("Input out of bounds");
    // n is odd
    if (input % 2 != 0) {
        long a = fibonacciRecursiveImproved((input+1)/2);
        long b = fibonacciRecursiveImproved((input-1)/2);
        return a*a + b*b;
    }

    // n is even
    long a = fibonacciRecursiveImproved(input/2 + 1);
    long b = fibonacciRecursiveImproved(input/2 - 1);
    return a*a - b*b;
}

Answer 19

using namespace std;

void mult(LL A[ 3 ][ 3 ], LL B[ 3 ][ 3 ]) {

     int i,

         j,

         z;

     LL C[ 3 ][ 3 ];

     memset(C, 0, sizeof( C ));

     for(i = 1; i <= N; i++)

         for(j = 1; j <= N; j++) {

             for(z = 1; z <= N; z++)

                 C[ i ][ j ] = (C[ i ][ j ] + A[ i ][ z ] * B[ z ][ j ] % mod ) % mod;
         }

     memcpy(A, C, sizeof(C));
};

void readAndsolve() {

    int i;

    LL k;

    ifstream I(FIN);
    ofstream O(FOUT);

    I>>k;

    LL A[3][3];
    LL B[3][3];

    A[1][1] = 1; A[1][2] = 0;
    A[2][1] = 0; A[2][2] = 1;

    B[1][1] = 0; B[1][2] = 1;
    B[2][1] = 1; B[2][2] = 1;

    for(i = 0; ((1<<i) <= k); i++) {

          if( k & (1<<i) ) mult(A, B);

          mult(B, B);
    }

    O<<A[2][1];
}

//1,1,2,3,5,8,13,21,33,...

int main() {

    readAndsolve();

    return(0);
}

Answer 20

public static int GetNthFibonacci(int n)
    {
        var previous = -1;
        var current = 1;
        int element = 0;

        while (1 <= n--)
        {
            element = previous + current;
            previous = current;
            current = element;
        }

        return element;
    }

Answer 21

这与之前给出的答案类似，但有一些修改。正如其他答案中所述，记忆是实现此目的的另一种方法，但我不喜欢随着技术变化而无法扩展的代码（unsigned int 的大小因平台而异），因此最高值可以达到的顺序也可能会有所不同，而且在我看来，记忆是丑陋的。

#include <iostream>

using namespace std;

void fibonacci(unsigned int count) {
   unsigned int x=0,y=1,z=0;
   while(count--!=0) {
      cout << x << endl;  // you can put x in an array or whatever
      z = x;
      x = y;
      y += z;
   }
}

int main() {
   fibonacci(48);// 48 values in the sequence is the maximum for a 32-bit unsigend int
   return 0;
}

此外，如果您使用，则可以编写一个编译时常量表达式，该表达式将为您提供序列中任何整数数据类型均可达到的最大索引。

Answer 22

#include<stdio.h>
main()
{
 int a,b=2,c=5,d;
   printf("%d %d ");
do
{
   d=b+c;
     b=c;
    c=d;
   rintf("%d ");
  }