[C]programma Fibonacci...

[kioccolatino90]

ciao a tutti devo scrivere un programma che inserito un numero intero maggiore o uguale a zero mi calcola la funzione di fibonacci; la funzione di fibonacci è definita $F(N)=F(N-1)+F(N-2)$....io l'ho scritto però non mi funziona e non capisco il perchè.... come prima cosa ho scritto:
si inserisca $N$, se $N<=0$ allora si deve rinserire $N$ quindi ho fatto un do while;
poi se $N$ non è minore di zero allora si deve considerare che per $N=1$ e $N=2$ la funzione restituisce in uscita rispettivamente $-1$, $1$ quindi faccio un for e dico: se $N==1$ $||$ $N==2$ allora $F=1$ altrimenti si esegue, in successione $F=(N-1)+(N-2)$, finchè non viene restituito un numero negativo, quindi un while...devo postare anche il programma o non serve?

[hamming_burst]

questo problema è stato discusso un decinaio di volte, da versioni esponenziali a molto efficienti.
Se ti va prova a cercare nei vecchi post

Se no posta il codice, leggerlo in linguaggio naturale proprio è inguardabile (per me)...

[vict85]

"domy90":ciao a tutti devo scrivere un programma che inserito un numero intero maggiore o uguale a zero mi calcola la funzione di fibonacci; la funzione di fibonacci è definita $F(N)=F(N-1)+F(N-2)$....io l'ho scritto però non mi funziona e non capisco il perchè.... come prima cosa ho scritto:
si inserisca $N$, se $N<=0$ allora si deve rinserire $N$ quindi ho fatto un do while;
poi se $N$ non è minore di zero allora si deve considerare che per $N=1$ e $N=2$ la funzione restituisce in uscita rispettivamente $-1$, $1$ quindi faccio un for e dico: se $N==1$ $||$ $N==2$ allora $F=1$ altrimenti si esegue, in successione $F=(N-1)+(N-2)$, finchè non viene restituito un numero negativo, quindi un while...devo postare anche il programma o non serve?

Questa non mi sembra la normale sequenza di fibonacci...

$-1$ $1$ $0$ $1$ $1$ $2 $... da qui in poi è normale.

Non mi sembra comunque un buon metodo per farlo, anche perché ripete molti calcoli più di una volta. Il metodo matriciale è molto meglio.

[apatriarca]

E' impossibile stabilire il tuo errore da quello che ci hai detto. Il procedimento sembra corretto, ma gli errori si nascondono spesso nei dettagli.

Ci sono in realtà alcuni errori e ambiguità nel tuo procedimento ma ho dato per scontato fossero distrazioni. Il primo numero di fibonacci sembri definirlo prima con -1 e poi correttamente con 1. Inoltre, la seconda volta che hai scritto l'equazione che definisce i numeri di fibonacci ti sei dimenticato di scrivere F. Come è scritta non è infatti corretta. E' probabile che nel tuo codice ci siano errori di distrazione simili che non possiamo trovare senza vederlo.

[kioccolatino90]

il programma è il seguente però mi sono reso conto che l'istruzione dell'if e cioè:

"F==1;
printf("la sequenza fi Fibonacci e': %d",F);" è sbagliato perchè in questo caso deve stampare tutta la sequenza di Fibonacci non solo il primo numero...

questo è il codice...

#include
#include
main () {
int N,F;
do {
printf("inserisci N: ");
scanf("%d",N);
}
while (N<0);
if ( (N==0) || (N==2) ){
F==1;
printf("la sequenza fi Fibonacci e': %d",F);
}
else{
while (N>2){
F==((N-1)+(N-2));
printf("la sequenza di fibonacci e': %d",F);
}
}
system ("PAUSE");
}

chiedo scusa non riesco ad indendare bene il codice, l'ho scritto in modo leggibile ma il sito non considera gli spazi e va accapo...

[Raptorista1]

Usi la sintassi del confronto per l'assegnamento.. Fa' più attenzione!!

[ramy1989]

Perchè non usi la ricorsione?
La sequenza di fibonacci è definita come:
\(f(n)=f(n-1)+f(n-1)\) con \(f(0)=1\) e \(f(1)=1\)
Per cui puoi scriverla in poche righe:

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

[apatriarca]

Prova a calcolare fibonacci(10000) con il tuo metodo ricorsivo e con la versione iterativa.

[ramy1989]

La versione iterativa e ricorsiva della funzione che calcola il numero di fibonacci, hanno la stessa complessità computazionale.Proprio perchè il numero di passi che serve per calcolare f(n-1) e f(n-2) è lo stesso.
Ho scritto la versione iterativa:

int fibonacci(int n)
{
    int temp=n,f[2],t;
    f[0]=1;
    f[1]=1;
    while(temp>1)
    {
        t=f[0];
        f[0]=f[1];
        f[1]=f[1]+t;
        temp--;
    }
    return f[1];
}

Che ad esempio per n=10, compie 9 passi, esattamente come la versione ricorsiva,che anch'essa compie 9 passi.

Ho corretto il codice dell' autore del thread,c he ora è corretto ma non fa quello che si vuole fare:

int main ()    // assegnare un valore di ritorno alla main, la void main non è C standard
{
    int N,F;
    do {
    printf("inserisci N: ");
    scanf("%d",&N);   // La scanf prende l' indirizzo della variabile
    }while (N<0);
        if ( (N==0) || (N==2) ){
        F=1;                         // f==1 non è un assegnamento, è un confronto.In questo caso senza effetto
        printf("la sequenza fi Fibonacci e': %d",F);
    }
    else{
    while (N>2){
        F=((N-1)+(N-2));  // ass
        printf("la sequenza di fibonacci e': %d",F);
        }
    }
return 0; 
}

Ed entra in un loop infinito quando dichiara:

while (N>2)

Senza toccare N.
Ricordarsi che quando si inizia un ciclo, bisogna sempre sapere qual'è la condizione di break.

[hamming_burst]

"ramy1989":La versione iterativa e ricorsiva della funzione che calcola il numero di fibonacci, hanno la stessa complessità computazionale.Proprio perchè il numero di passi che serve per calcolare f(n-1) e f(n-2) è lo stesso.

sicuro sicuro?
Non serve nemmeno conoscere l'analisi degli algoritmi per capire che questo non è affato vero.
Fai una prova come ti ha consigliato il buon apatriarca. Basta un test casereccio, scrivi due file di test una con la versione iterativa ed una ricorsiva, poi eseguili con il comando "time" (se sei in linux).
Se no, metti una print nel ciclo principale se iterativa, o nella chiamata se ricorsiva. Analizza le stampe (basta un f(6) mi sembra o meno) e poi dimmi cosa noti...

[ramy1989]

Versione ricorsiva:
\(T(6)=T(5)+T(4) = T(4) +3T(3) + T(2)=\)
\(= T(3) + 3 \cdot T(2) + 3 \cdot T(1) + T(0) = T(3) + 3 \cdot T(2) +4=\)
\(= T(2) + T(1) +3 \cdot T(1) + 3 \cdot T(0) +4 =13\)
Versione iterativa:
\(T(6)=5\)

Avete ragione, ho provato anche a calcolar eil caso generico \(T(n)\), senza successo.

[itpareid]

tra l'altro l'n-esimo numero della sequenza di Fibonacci è facilmente calcolabile in "forma chiusa" e senza iterazioni o ricorsioni

[apatriarca]

La formula chiusa è meno utile di quanto possa sembrare. Ci vogliono infatti meno di 100 valori della successione per non essere più in grado di rappresentare i numeri della successione correttamente usando dei double. Inoltre è abbastanza raro aver bisogno di accedere alla successione in modo casuale e se si accede in modo sequenziale il metodo iterativo è più efficiente e preciso.

[ramy1989]

In effetti con gli unsigned long si arriva fino a \(2^{64} -1\) sulla mia macchina, mi sono dimenticato di fare il controllo che non gli venga passato un n troppo grande.

[ramy1989]

O puoi fare una funzione ricorsiva inline.

[apatriarca]

Cioé? Che intendi dire?