如何更快地生成Fibonacci

Question

我是一名CSE学生,正准备参加编程竞赛.现在我正在研究Fibonacci系列.我有一个大小约为包含正整数的Kilo字节的输入文件.输入甲酸酯看起来像

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

你应该考虑一下memoization.

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

它有一个解释和一个例子

Answer 3

您可以通过矩阵乘法来实现此目的,将矩阵提升为幂n,然后将其乘以向量.您可以在logaritmic时间将其提升到电源.

我想你可以在这里找到问题.它是罗马尼亚语,但你可以用谷歌翻译翻译它.这正是你想要的,以及它在那里列出的解决方案.

Answer 4

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

此问题已在stackoverflow上讨论过: Fibonacci Sequence的计算复杂性

在该特定讨论中还发布了更快的实施.

Answer 5

在维基百科中,有一个公式可以给出Fibonacci序列中的数字,根本没有递归

Answer 6

使用memoization.也就是说,您缓存答案以避免不必要的递归调用.

这是一个代码示例:

#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);
}