Suite de Fibonacci (compléxité de l'algo...)
Fermé
Alex
-
28 oct. 2008 à 11:51
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 - 28 oct. 2008 à 16:41
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 - 28 oct. 2008 à 16:41
A voir également:
- Algorithme fibonacci complexité
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Code ascii algorithme - Guide
- Suite de fibonacci algorithme - Forum Programmation
- Remplir une matrice algorithme - Forum Pascal
- Algorithme qui calcule le carré d'un nombre - Forum Algorithmes / Méthodes
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
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
28 oct. 2008 à 16:41
28 oct. 2008 à 16:41
Pour l'algorithme va voir ici
