c - フィボナッチをより速く生成する方法

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

メモリに制限がある場合は、最後の 2 つのフィボナッチ数を返す関数の末尾再帰バージョンを単純に使用できます。

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 で議論されました: Computational complex of Fibonacci Sequence

その特定のディスカッションに投稿されたより高速な実装もあります。

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 は、配列を 1 回だけ初期化し、それを他のすべての呼び出しで再利用します。

2 値スタック配列バージョンは、最適化すると一時変数を使用するバージョンと同じように動作します。

Answer 8

フィボナッチ数列を生成する高速倍増法を使用することもできます リンク:最速の計算方法-フィボナッチ数

実際には、行列指数法の結果から導き出されます。

Answer 9

黄金比を使用する

Answer 10

あなたの例のように、入力が昇順であなたに与えられることが保証されていますか？もしそうなら、メモ化すら必要ありません。最後の2つの結果を追跡し、シーケンスの生成を開始しますが、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 11

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 12

行列の乗算、浮動小数点演算なし、整数の乗算/加算が一定時間で行われると仮定すると、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 13

input.txt ファイルと時間制限を投稿できますか? ところで：このタスクはよく知られています。次のhttp://www.ics.uci.edu/~eppstein/161/960109.htmlを読みましたか?

Answer 14

fibonacci(n) の結果をキャッシュする配列 Answer[100] を作成します。フィボナッチ コードをチェックインして、答えが事前に計算されているかどうかを確認し、その結果を使用します。結果はあなたを驚かせるでしょう。

Answer 15

#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 16

if ステートメントのオーバーヘッドを減らすことができます: C で再帰的にフィボナッチ数を計算する

Answer 17

まず、メモ化または同じアルゴリズムの反復実装を使用できます。

アルゴリズムが行う再帰呼び出しの数を考慮してください。

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];
}

これはすでにあなたのアプローチよりもはるかに高速です。の最大値まで配列を 1 回だけ作成し、配列nの要素を出力して 1 回の操作で正しい数値を出力するだけで、同じ原理でより高速に実行できます。この方法では、すべてのクエリに対して関数を呼び出す必要はありません。

最初の事前計算の時間を確保できない場合 (ただし、これは通常、何かを法とする結果を求められた場合にのみ発生します。それ以外の場合は、大きな数の演算を実装することを期待していない可能性があり、事前計算が最善の解決策です)。他の方法については、フィボナッチ wiki ページを参照してください。マトリックス アプローチに注目してください。これは、コンテストで知っておくと非常に役立ちます。

Answer 18

これらのいずれかを使用します: 再帰の 2 つの例。1 つは for ループ O(n) 時間で、もう 1 つは黄金比 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

関数型プログラミングには、フィボナッチをカウントするための特別なアルゴリズムがあります。このアルゴリズムは累積再帰を使用します。累積再帰は、アルゴリズムで使用されるスタック サイズを最小限に抑えるために使用されます。時間を短縮するのに役立つと思います。必要に応じて試すことができます。

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