Fibonacci serie - sommatoria ricorsivo

Question

Ok, inizialmente ho scritto un semplice codice per restituire il numero di Fibonacci dalla serie basata sull'input dell'utente ..

n = 5 produrrà 3 ..

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

Stavo pensando di modificare il codice per restituire la somma della serie piuttosto che semplicemente restituire il valore dalla serie e mentre cercavo di fare la somma ho accidentalmente aggiunto 1 alla dichiarazione di reso e con mia sorpresa, ha restituito la somma correttamente.

Il codice seguente restituirà 7 per n = 5.

Non sono sicuro se questo è un modo giusto per calcolare la somma ...

io ancora non riuscivo a capire come la somma della serie funziona se aggiungo 1. Qualcuno può spiegare ??

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

EDIT:

Per Fibonacci series..0,1,1,2,3,5,8,13,21,34,55,89,144 ....

I provato per qualche n casuale

n = 13

La funzione restituisce 376

0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 + 144 = 376

n = 10

La funzione restituisce 88

0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88

Answer 1

La modifica al programma fibonacci funziona effettivamente per calcolare le somme. Tuttavia, il modo in cui hai usato la ricorsione è inefficiente. Un modo per affrontarlo è con un approccio di "programmazione dinamica", in cui i valori calcolati vengono memorizzati nella cache in modo che possano essere riutilizzati dalla seconda chiamata ricorsiva.Tuttavia, il n-esimo numero di Fibonacci può essere calcolato in avanti dalla base. Un'implementazione ricorsiva di questo sarebbe:

public static int fib_r (int a, int b, int n) { 
    if (n == 1) return a; 
    if (n == 2) return b; 
    return fib_r(b, a+b, n-1); 
} 

public static int fib (int n) { 
    return fib_r(0, 1, (n > 0) ? n : 1); 
} 

Il codice corrispondente per la somma sarebbe:

public static int sumfib_r (int a, int b, int n) { 
    if (n == 1) return a; 
    if (n == 2) return b; 
    return sumfib_r(b, a+b+1, n-1); 
} 

public static int sumfib (int n) { 
    return sumfib_r(0, 1, (n > 0) ? n : 1); 
} 

coda ricorsione sarà spesso modificato dal compilatore/interprete in un semplice ciclo come parte di tail call rimozione.

ti ha chiesto:

io ancora non riuscivo a capire come la somma della serie funziona se aggiungo 1. Qualcuno può spiegare ??

Questa domanda riguarda davvero la comprensione dell'algoritmo, che suppongo sia di attualità su SO. Ma è richiesta la matematica per descrivere perché l'algoritmo funziona. Quindi, questa è davvero una domanda di matematica. C'è un well known theorem regarding the sum of Fibonacci numbers. Se F[i] è il numero di Fibonacci i-esimo, e S[n] è la somma dei primi n numeri di Fibonacci, poi il teorema afferma sopra:

S[n] = F[n+2] - 1 

Quindi, se si considera che per definizione di S[n+2],

S[n+2] = S[n+1] + F[n+2] 

Poi, sostituendo S[n] + 1 per F[n+2]:

S[n+2] = S[n+1] + S[n] + 1 

che si dovrebbero riconosce è la tua funzione "aggiungi 1 modificato" fibonacci.

---

Di seguito è una prova per induzione che il tuo programma calcola la somma che ho fornito nella mia risposta originale. Lascia che F rappresenti la tua funzione fibonacci e che sia S la funzione "aggiungi 1 modificato" fibonacci.

F[1] = 0 
F[2] = 1 
F[i] = F[i-1] + F[i-2] for i > 1 

S[1] = 0 
S[2] = 1 
S[i] = S[i-1] + S[i-2] + 1 for i > 1 

Quindi, si vuole una prova che per k > 0:

  k 
     .--- 
S[k] = > F[i] 
     `--- 
     i = 1 

Si noti che quanto sopra sommatoria è vero se e solo se:

S[1] = F[1] 
S[k] = F[k] + S[k-1] for k > 1 

La prova è abbastanza semplice. I casi base sono banalmente veri.

S[1] = F[1] = 0 
S[2] = F[2] + F[1] = 1 
S[3] = S[2] + S[1] + 1 = F[3] + F[2] + F[1] = 2 

Il passo induzione è: Dato che per alcuni k > 2, S[j+1] = F[j+1] + S[j] per 0 < j < k+1, dimostrano che l'uguaglianza vale se j = k+1, cioè: S[k+2] = F[k+2] + S[k+1].

S[k+2] = S[k+1] + S[k] + 1 
=> S[k+2] = (F[k+1] + S[k]) + (F[k] + S[k-1]) + 1 
=> S[k+2] = (F[k+1] + F[k]) + (S[k] + S[k-1] + 1) 
=> S[k+2] = F[k+2] + S[k+1] 

Questo completa la prova.

Answer 2

No non. La seconda versione del codice fa non calcola la somma di tutti i valori della funzione Fibonacci fino al valore specificato. E anche i casi base sono sbagliati!

Se si vuole calcolare la somma in modo ricorsivo, dividere il problema in due parti, in questo modo:

public static int fib(int n) { 
    return n < 2 ? n : fib(n-1) + fib(n-2); 
} 

public static int sumfib(int n) { 
    return n < 0 ? 0 : fib(n) + sumfib(n-1); 
} 

La prima funzione calcola Fibonacci, la seconda si occupa di aggiungere i valori fino a un dato numero.

Answer 3

Il codice ha bisogno di test per n<1 - se si passa un argomento di 0 o meno, si andrà avanti per sempre ...

Diverso da quello che - se si chiama fib(5), ecco cosa succede:

... 
return(fib(4) + fib(3)) 

fib(4): 
return(fib(3) + fib(2)) 

fib(3): 
return(fib(2) + fib(1)) 

now fib(2) == 1 by your definition, and fib(1) == 0 

so fib(3) == 1 

then fib(4) == 1 + 1 = 2 

and fib(5) = fib(4) + fib(3) = 2 + 1 = 3 

Now if you add the '+1', the following happens: 

fib(1) and fib(2) are unchanged 
fib(3) = 1 + 0 + 1 = 2 
fib(4) = fib(3) + fib(2) + 1 = 4 
fib(5) = fib(4) + fib(3) + 1 = 4 + 2 + 1 = 7 

Il metodo originale è buono, ma dipende da come si considera "l'ordine" di un numero di Fibonacci (quale deve essere il primo numero).

Answer 4

Il modo giusto per farlo è utilizzare l'accumulatore.

il codice dovrebbe essere simile a questo (non ho controllato, è solo l'idea)

static int fibonacci(int n, int accumlator) { 
    if (n == 1) 
     return 0; 
    else if (n == 2) 
     return 1; 
    else 
     accumlator = (fibonacci(n - 1, accumlator) + fibonacci(n - 2, accumlator)); 
     return accumlator; 
} 

Answer 5

è ricorsivo un modo molto inefficiente per calcolare il Fibonacci number.After il numero 43 ci vorrà più di 30 secondi finché non avrai la risposta. Ho cercato di scoprire quanto tempo ci vorrà per calcolare il numero 52 e ci sono voluti circa 47 minuti. Quindi il tempo cresce molto velocemente.

Il codice ricorsivo:

private int calculateRecursivelyInt(int fnum) 
    { 
     if (fnum == 0) 
      return 0; 
     if (fnum == 1) 
      return 1; 

     return calculateRecursivelyInt(fnum - 1) + calculateRecursivelyInt(fnum - 2); 
    } 

Loops sono molto più efficienti

//This method will be able to calculate till the F46 because int can't hold a 
    // bigger number. You can calculate till 92 with a type long and till 93 with 
    // unsigned long in C#. 

    private int calculateLoopInt(int num) 
    { 
     int fnum = 0; 
     int val1 = 0; 
     int val2 = 1; 

     for (int i = 0; i < num; i++) 
     { 
      if (num == 1) 
       fnum = 1; 
      else if (i > 0) 
      { 
       fnum = val1 + val2; 
       val1 = val2; 
       val2 = fnum; 
      } 
     } 
     return fnum; 
    } 

Answer 6

un altro approccio per stampare serie di Fibonacci utilizzando la funzione ricorsiva.

#include <iostream> 

// 0 1 1 2 3 5 8 13... 
// 

void fibb (int idx, int curr = 0, int next = 0) 
{ 
     std::cout << curr << ", "; 
     if(!idx) return; 
     if(curr == 0) { 
       curr = 1; 
       fibb(--idx, curr, next); 
       return; 
     } 
     next += curr; 
     fibb(--idx, next, curr); 
} 


int main() 
{ 
     fibb(10); 
}