TP D’ALGORITHMIQUE
BUT DE TP :
Le but de ce TP est de traiter la suite de FIBONNACI
,en réalisant un algorithme regroupant les trois algorithmes qui donnent la valeur de
cette suite .
LES ALGORITHMES :
1-Algorithme Récursif :
Function Fib1(n)
int Fib1 (int n)
{
if
(n<=2) return n;
else return Fib1 (n-1)+ Fib1 (n-2) ;
}
On remarque que le nombre d'appels récursifs est très élevé. Et le temps
d’exécution t1(n) de cet algorithme vérifie l’équation suivante :
t1(0)=t1(1)=1 .
t1(n)=1+t1(n-1)+t1(n-2) .
* Ainsi le
temps d’exécution de la suite de Fibonacci par la fonction Fib1 est un Θ(kn) ,en sachant que k est un nombre
bien spécifique dit le nombre d’or et
qui est égal à : (1+√5 )/2
On peut
remarquer dans le cas de cet algorithme que la valeur de cette fonction croit
d’une façon très rapide en fonction de n ,ce qui nous créé un problème de
dépassement de mémoire .D’où
la conclusion que cet algorithme ne peut être utilisé que pour des valeurs
minimes de n.
2-Algorithme Fib2 :
L’algorithme de cette fonction est le suivant :
Debut
u ß 0
v ß 1
pour 1 ß1 jusqu
‘a n faire
w ß u+v
u ß v
v ß w
fin pour
imprimer w
Fin
On a remarqué dans le premier
algorithme que le temps est agrandi par le recalcul perpétuel des Fib2(k) avec
k<n . C’est d’ou venu l’idée de stocker les deux valeurs précédentes
,nécessaires au calcul de la valeur présente
de Fib 2 ,afin d’éviter de les recalculer .Et l’algorithme précédent
exprime cette idée de stockage, ainsi on a le temps d’exécution est une
fonction linéaire de n:
t2(n)=O(n)
D’où le calcul des Fib2 ne nécessite qu’une
quantité constante de mémoire.
3-Algorithme Fib3 :
L’algorithme de cette fonction est le
suivant :
Début
i ß1; jß0; kß0; hß 1 ;
while (n > 0) do
begin 
if n mod (2)=1
then
begin
t ß j * h
j ß i * h +j *k +t
i ß i * k +t
end
t
ß h2
h ß 2 k *n + t
k ß k2 +t
n ß n div 2
endif
end
Fin
Cet
algorithme a un temps d’exécution qui
évolue d’une façon logarithmique en
fonction de n : t3( n)=O (log(n))