Suite de Fibonacci (compléxité de l'algo...) Fermé

Question

Bonjour,
j'ai les question de la  Suite de Fibonacci

F(n) = 0 si n=0; =1 si n=1 ; et =F(n-1)+F(n-2);
algo récursif:
funtion Fibo () 
if n<=1 then return n ;
else return Fibo(n-1)+Fibo(n-2) ;
end fibo;


question :
1. soit a(n) le nombre d'additions effectuées pas l'algorithme.Montrer que a(n)=F(n+1)  -1 
2.en déduire la compléxité de l'algorithme récursif
3.Proposer un algorithme itératif de meilleur compéxité 

aide - moi svp 

merci d'avance

samy · Accepted Answer

Bonjour l'ami;

On ce cas on fait apel a la démenstration par récurrence donc tu suit les étape suivantes:

On a la propriété suivante : nombre d'additions effectuer par l'algo  a(n)= F(n+1)-1;

1) on montre que cette propriété est vérifiée pour n=0 et n=1;
    
     n=0:  a(0)=F(1)-1=0 ==> vérifiée
     n=1:  a(1)=F(2)-1=F(1)+F(0)-1=0 ==> vérifiée,

2) on suppose que propriété est verifiée à l'ordre n (c-à-d a(n) vérifiée ) et on montre quelle est vérifiée auusi pour n+1, 
    donc:  pour n : a(n)=F(n+1)-1 ==> vérifiée;

    pour n+1:   a(n+1)= F((n+1)+1)-1
                              .......
                              =a(n)+F(n) comme a(n) est vérifiée donc a(n+1) est vérifiée.

complexité de l'algo est de l'ordre de F(n+1);

pour l'algo itératif essai d'utiliser la question précédente :-*)

Bon courage.

Alex · Answer

merci de votre aide 
mais le question 2 vous pouvez m'expliquer , parce que j'ai pas bien compris compléxité de l'algo recursif 
et quesition 3 aussi 

merci bcp

KX · Answer

Pour l'algorithme va voir ici

Suite de Fibonacci (compléxité de l'algo...)

3 réponses

Discussions similaires