14

我是一名 CSE 学生,正在为编程比赛做准备。现在我正在研究斐波那契数列。我有一个大小约为一些包含正整数的 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;
}

该代码适用于样本输入并提供准确的结果,但问题是对于我的真实输入集,它花费的时间超过了我的时间限制。谁能帮我吗。

4

23 回答 23

20

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

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

这是O(n)并且需要一个恒定的空间。

于 2010-07-26T18:30:46.130 回答
14

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

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

它在那里有一个解释和一个 fib 示例

于 2010-07-26T17:49:49.353 回答
13

您可以通过矩阵乘法来做到这一点,将矩阵提升到 n 次方,然后将其乘以向量。您可以在对数时间内将其提高到幂。

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

于 2010-07-26T18:03:48.917 回答
10

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

这个问题之前已经在stackoverflow上讨论过: 斐波那契数列的计算复杂度

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

于 2010-07-26T17:50:06.020 回答
8

查看维基百科,有一个公式可以给出斐波那契数列中的数字,根本没有递归

于 2010-07-26T18:09:09.287 回答
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);
}
于 2010-07-26T17:49:58.783 回答
4

没有人提到 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 值堆栈数组版本在优化时与具有临时变量的版本执行相同。

于 2016-06-16T17:18:54.127 回答
3

也可以使用快速倍增法生成斐波那契数列链接:fastest-way-to-compute-fibonacci-number

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

于 2013-01-09T06:25:08.923 回答
2

Use the golden-ratio

alt text

alt text

于 2010-07-26T18:12:58.767 回答
1

Are you guaranteed that, as in your example, the input will be given to you in ascending order? If so, you don't even need memoization; just keep track of the last two results, start generating the sequence but only display the Nth number in the sequence if N is the next index in your input. Stop when you hit index 0.

Something like this:

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

I leave exit conditions and actually generating the sequence to you.

于 2010-07-26T18:10:49.030 回答
1

In 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);
        }
于 2014-04-25T15:05:14.193 回答
1

矩阵乘法,无浮点运算,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
于 2014-04-03T08:09:23.597 回答
1

您可以发布 input.txt 文件和时间限制吗?顺便说一句:这个任务是众所周知的。您是否阅读了以下http://www.ics.uci.edu/~eppstein/161/960109.html

于 2010-07-26T17:49:56.317 回答
1

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

于 2010-07-26T17:50:31.037 回答
0

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

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);
}
于 2010-07-26T18:47:35.420 回答
0

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

于 2010-07-26T17:51:38.350 回答
0

首先,您可以使用记忆化或相同算法的迭代实现。

考虑您的算法进行的递归调用的数量:

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,然后通过打印数组的元素在单个操作中打印正确的数字。这样您就不会为每个查询调用该函数。

如果您负担不起初始的预计算时间(但这通常仅在您被要求对结果取模时才会发生,否则他们可能不希望您实现大数算术并且预计算是最好的解决方案),请阅读其他方法的斐波那契维基页面。专注于矩阵方法,这是在比赛中很好了解的方法。

于 2010-07-26T17:54:29.820 回答
0

使用其中任何一个:递归的两个示例,一个使用 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;
}
于 2012-06-13T08:28:45.977 回答
0
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);
}
于 2014-09-22T15:51:37.263 回答
0
#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;
   }
于 2010-07-26T18:18:40.077 回答
0
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;
    }
于 2015-07-13T21:20:10.693 回答
0

这类似于之前给出的答案,但有一些修改。正如其他答案中所述,记忆是另一种方法,但我不喜欢不会随着技术变化而扩展的代码(an 的大小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;
}

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

于 2015-12-13T15:33:20.867 回答
-1
#include<stdio.h>
main()
{
 int a,b=2,c=5,d;
   printf("%d %d ");
do
{
   d=b+c;
     b=c;
    c=d;
   rintf("%d ");
  }
于 2013-08-27T18:03:50.910 回答