Suite de Fibonacci (compléxité de l'algo...)
Alex
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
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
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
A voir également:
- Algorithme fibonacci complexité
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
3 réponses
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.
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.
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
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
