Funzione algoritmo per serie fibonacci

Question

Non sto cercando necessariamente una risposta, ma sto cercando ciò che questa domanda sta chiedendo. Trovato questa domanda studiando per un colloquio, ma non sono sicuro di quello che stanno chiedendo?

Scrive la funzione che attraversa la sequenza di Fibonacci e restituisce l'indice che viene passato come parametro.

Answer 1

in primo luogo, è possibile aggiornare le informazioni matematiche di base su Fibonacci con questo link da wiki. e guarda this formula per calcolare velocemente e puoi leggere tutto su di esso in this link.

Questa è la funzione ricorsiva per calcolare il numero di Fibonacci esimo ed è di O (2^n):

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

Calcolo della sequenza

Si potrebbe obiettare che in termini di realtà calcolo del valori della sequenza di Fibonacci su un computer, è meglio usare la relazione di ricorrenza originale , f [n] = f [n-1] + f [n-2]. Sono propenso a essere d'accordo. Per utilizzare la soluzione di forma chiusa diretta per n grandi, è necessario mantenere un lotto di precisione . Anche con 9 posizioni decimali, fn≈round (0.723606798⋅ (1.618033989) n), ad esempio, è valido solo per fino a n = 38 (osservare here rispetto a here). Inoltre, l'aggiunta di numeri interi è molto meno computazionalmente costoso e più precisa di exponentiating una frazione simbolico o un valore in virgola mobile

questo è meglio idea di calcolare il numero di Fibonacci esimo ed è di 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;} 

e questo è il modo migliore per calcolare il numero di Fibonacci esimo ed è di O (log (n)):

this link:

Come già sospettate, funzionerà in modo molto simile. Utilizzare la potenza n-esima della matrice x * x

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

Questo è facile da capire se si moltiplica questa matrice con il vettore

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

che si traduce in

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

Matrix elevamento a potenza può essere fatto in tempo O (log (n)) (quando x è considerato come costante).

Per la ricorrenza di Fibonacci, esiste anche una soluzione a formula chiusa, vedere qui http://en.wikipedia.org/wiki/Fibonacci_number, cercare la formula di Binet o di Moivre.

e guardare: 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

interpreto la questione in modo diverso .... dato un number come input, qual è la index di quel numero nella serie? per esempio. input=5, quindi indice è 5 (data la sequenza è 0 1 1 2 3 5 dove l'indice inizia con 0)

Questo codice è il seguente (che restituisce l'indice) [Disclaimer: Adattato dal code in 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

Quello che mi sembra è che ti venga chiesto di restituire l'ennesima fibonacci n., Dove n è il parametro passato. È possibile utilizzare vari metodi per rispondere a questa domanda, mentre tutti questi variano in termini di complessità temporale e complessità del codice.

Metodo 1 (Utilizzare la ricorsione) Un metodo semplice che è una relazione di verifica matematica dell'implementazione diretta recusriva sopra riportata.

int fib(int n) 
{ 
    if (n <= 1) 
    return n; 
    return fib(n-1) + fib(n-2); 
} 

Tempo Complessità: T (n) = T (n-1) + T (n-2), che è esponenziale. Possiamo osservare che questa implementazione fa un sacco di lavoro ripetuto (vedere il seguente albero di ricorsione). Quindi questa è una cattiva implementazione per il n ° numero di Fibonacci.

     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) Spazio Extra: O (n) se consideriamo la dimensione dello stack di chiamata di fuinction, altrimenti O (1).

Metodo 2 (Usa programmazione dinamica) È possibile evitare il lavoro ripetuto eseguito con il metodo 1 memorizzando i numeri di Fibonacci calcolati finora.

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

Tempo Complessità: O (n) Spazio Extra: O (n)

Metodo 3 (Spazio Otimized Metodo 2) possiamo ottimizzare lo spazio utilizzato nel metodo 2 memorizzando i due numeri precedenti solo perché questo è tutto ciò che serve per ottenere il prossimo numero di Fibannaci in serie.

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

Tempo Complessità: O (n) Spazio Extra: O (1)

Metodo 4 (Usando il potere della MATRX {{1,1}, {0,1}}) Questa un altro O (n) che si basa sul fatto che se moltiplichiamo n volte la matrice M = {{1,1}, {0,1}} a se stessa (in altre parole calcoliamo il potere (M, n)), allora ottieni il numero (n + 1) di Fibonacci come elemento a riga e colonna (0, 0) nella matrice risultante.

La rappresentazione matriciale dà la seguente espressione chiuso per i numeri di Fibonacci:

/* 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); 
    } 

Tempo Complessità: O (n) spazio aggiuntivo: O (1)

Metodo 5 (ottimizzato metodo 4) Il metodo 4 può essere ottimizzato per lavorare nella complessità del tempo O (Logn). Possiamo fare la moltiplicazione ricorsivo per ottenere il potere (M, N) nel metodo prevous (Simile alla ottimizzazione fatto in questo post)

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

Tempo Complessità: O (log) Spazio Extra: O (log) se consideriamo la funzione stack size delle chiamate, altrimenti O (1).

Driver Program: int main() { int n = 9; printf ("% d", fib (9)); getchar(); return 0; }

Riferimenti: http://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html

Answer 5

E 'una domanda molto mal formulata, ma si deve supporre che chiedono per il n ° numero di Fibonacci in cui n è fornito come parametro.

Oltre a tutte le tecniche elencate da altri, per n > 1 è anche possibile utilizzare golden ratio method, che è più veloce di qualsiasi metodo iterativo. Ma poiché la domanda dice "corri attraverso la sequenza di Fibonacci", questo potrebbe non essere valido. Probabilmente li spaventerai anche a morte.