フィボナッチシリーズのアルゴリズム関数

Question

私は必ずしも答えを探しているわけではありませんが、私はこの質問が何を求めているのか探しています。インタビューのために勉強しているが、彼らが何を求めているのかはっきりしないこの質問を見つけましたか？

フィボナッチシーケンスを実行し、パラメータとして渡されるインデックス を返す関数を書く。

Answer 1

まず、フィボナッチについての基礎数学の情報をwikiのlinkで更新することができます。あなたは速い計算のためにthis formulaを見てください。そして、あなたはそれについてのすべてをthis linkで読むことができます。

これは、n番目のフィボナッチ数を計算する再帰関数であり、Oである（2^n）の時間：

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

が

あなたが実際のコンピューティングの面でそれを主張するかもしれないシーケンスを計算コンピュータ上の フィボナッチシーケンスの値を使用する場合は、元の の反復関係f [n] = f [n-1] + f [n-2]を使用する方がよいでしょう。私は同意する傾向がある。大きなnに対してダイレクトクローズフォームソリューション を使用するには、 の精度を維持する必要があります。たとえば、 fn≒around（0.723606798⋅（1.618033989）n）は、小数点以下9桁であっても、 までのn = 38（hereとhereの間を観察する）にのみ有効です。また、整数を加えることははるかに 少ない計算コストと シンボリック画分または浮動小数点値

これがn番目のフィボナッチ数を計算するために、良いアイデアであり、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））は、時間n番目のフィボナッチ数を計算するための最良の方法であり、Oである。

this link:

あなたがすでに疑っているように、これは非常によく似た働きをします。あなたは

f(n), f(n-1), ... , f(n-x+1) 

行列の累乗になり、ベクトル

f(n-1), f(n-2), ... , f(n-x+1), f(n-x) 

でこの行列を掛ける場合は理解してこれは簡単です

|1 0 0 0 .... 1 1| 
|1 
| 1 
| 1 
|  1 
|  1 
................... 
................... 
|   ... 1 0| 

x * x行列のn乗を使用することができますO（log（n））時間（xが一定とみなされる時）で行われる。

フィボナッチ再発については、閉鎖式ソリューションもあります。http://en.wikipedia.org/wiki/Fibonacci_numberを参照してください。Binet'sまたはMoivreの式を探します。

と見て：私は、入力として与えられたnumber ....違った質問を解釈 の1- nth fibonacci number in sublinear time

Answer 2

public static int fibonacci(int i){ 
if(i==0) 
    return 0; 

if(i==1) 
    return 1; 
return fib(--i,0,1); 
} 


public static int fib(int num,int pre,int prepre){ 
    if(num==0){ 
    return prepre+pre; 
    } 
    return fib(--num,pre+prepre,pre); 
} 

Answer 3

、シリーズでその数のindexは何ですか？例えばinput=5、インデックスが（シーケンスインデックスが0始まる0 1 1 2 3 5ある所与）5ある

この（インデックスを返す）は、以下のようにコードは[免責事項：http://talkbinary.com/programming/c/fibonacci-in-c/で与えられたコードから適応]

int Fibonacci(int n) 
{ 
    if (n == 0) 
    return 0; 
    if (n== 1) 
    return 1; 

    int fib1 = 0; 
    int fib2 = 1; 
    int fib = 0; 
    int i = 0; 

for (i = 2; ; i++) 
{ 

    fib = fib1 + fib2; 
    if (n == fib) 
     break; 
    fib1 = fib2; 
    fib2 = fib; 
} 


    return i; 
} 

Answer 4

私には、n番目に渡されたパラメータであるn番目のフィボナッチ数を返すように求められているようです。さまざまな方法を使用してこの質問に答えることができますが、これらはすべて時間の複雑さとコードの複雑さの点で異なります。

方法1（再帰を使用する） 上記の与えられた直接的な再学習の実装の数学的な関係です。 T（n）= T（n-1）+ T（n-2）（指数関数的）である。 この実装では、多くの繰り返し作業が行われることがわかります（次の再帰ツリーを参照）。だから、これはn番目のフィボナッチ数の悪い実装です。

     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は）、それ以外の場合は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（空間Otimized方法2） 我々は、以前の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}}のパワーを使用して）行列M = {{1,1}、{0,1}}をそれ自身に（即ち、パワー（M、n）を計算する）掛け合わせると、結果の行列の行と列（0、0）の要素として（n + 1）番目のフィボナッチ数を取得します。

行列表現は、フィボナッチ数については、次の閉じた式を与える：

/* 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）時間の複雑さで働くように最適化することができる。場合O（LOGN）：O（LOGN） 余分なスペース：我々は（この記事で行われる最適化と同様に）prevous方法

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

時間計算にパワー（M、N）を取得するために、再帰的な乗算を行うことができます我々は、関数呼び出しのスタックサイズ、それ以外の場合はO（1）を考慮する。

ドライバプログラム： int main（） { int n = 9; printf（ "％d"、fib（9））; getchar（）; return 0; }

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

Answer 5

それは非常に悪い表現の質問ですが、あなたは彼らがnがパラメータとして提供されたn 番目Fibonnaci番号を求めていると仮定しなければなりません。

n > 1については、他のすべての手法に加えて、任意の反復方法よりも速いgolden ratio methodを使用することもできます。しかし、問題が「フィボナッチシーケンスを実行する」と言えば、これは適格ではないかもしれません。あなたは恐らくそれらを恐れて死に至らせるでしょう。