Université Bordeaux 1 Licence Informatique 2007/2008
Exercice 1.1
On considère la fonction suivante:
fonction mystere(ref T : tableau{1..N] d'entier , val N : entier):vide;
var i, j : entier;
debut
i = 1;
j = N;
tant que i < j faire
si T[i] == 0 alors
i = i+1
sinon
echanger(T[i], T[j]);
j = j-1
fsi
ftq
fin;
T ne contient
que des T doit être
examiné au maximum une fois).
K valeurs différentes?
T[1..N] contenant une valeur X en 2 zones:
T[1..I-1] contenant les entrées strictement inférieures à
X, T[I..N] les entrées supérieures ou égales à
X, de façon que X se trouve en position I à la
fin du
traitement.
Exercice 1.2
Suite de Fibonacci. On rappelle que la suite de Fibonacci,
s'obtient de la
façon suivante: à partir du rang 3, chaque terme est la
somme des deux précédents.
Pour calculer le
-ième terme de la suite donner une
fonction :
Calculer la complexité du calcul des nombres de Fibonacci par les
algorithmes récursif et itératif précédents. Il est utile de
savoir que les nombres de Fibonacci sont étroitement liés au
nombre d'or
et à son conjugué
,
qui sont donnés par les formules suivantes:
Plus précisement, si on appelle
le
-ième nombre de
Fibonacci (
), on a
Exercice 1.3
Ecrire un algorithme calculant le
-ième nombre de Fibonacci
en temps
.
Indications :
et exprimer