Exercice 1.1
On considère la procédure suivante:
procedure mystere(ref T : tableau, val N : entier)
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 0 et 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
procedure exp_rapide(ref A : tableau, val n : entier)
var B, C: tableau ;
debut
B = A;
C = I();
tant que n > 1 faire
si (n mod 2) == 1 alors C = produit(B,C) fsi
B = produit(B, B);
n= n div 2;
ftq
si n == 1 alors C = produit(B,C) fsi
retourne(C);
fin;
Exercice 1.4
On voudrait stocker un ensemble de cercles de dimension quelconque, dans un premier temps dans l'ordre de leur stockage, ensuite de manière
ordonnée( du plus petit au plus grand).
Pour rappel, un cercle est la donnée
d'un point et d'un rayon.
On pourra utiliser le type abstrait containeur et les primitives correspondantes comme défini en cours
pour représenter et manipuler l'ensemble de cercles.