next up previous
suivant: Problème récurrent ( notre

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;

  1. Que fait-elle en supposant que le tableau T ne contient que des 0 et des $ 1$?
  2. Modifier l'algorithme de façon à l'appliquer à des tableaux contenant au plus trois valeurs différentes: par exemple 0, $ 1$ et $ 2$ (rappel: chaque élément de T doit être examiné au maximum une fois).
    Peut-on l'étendre aisément à K valeurs différentes?
  3. Donner une version récursive de l'algorithme général.
  4. Ecrire une procédure séparant un tableau d'entiers 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.
    Etudier l'occupation en mémoire.
    Donner le principe d'un algorithme de tri utilisant cette dernière procédure.

Exercice 1.2 Suite de Fibonacci
On rappelle que la suite de Fibonacci, $ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ s'obtient de la façon suivante: à partir du rang 3, chaque terme est la somme des deux précédents.
Pour calculer le $ n$-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 $ \phi$ et à son conjugué $ \overline{\phi}$, qui sont donnés par les formules suivantes:

$\displaystyle \phi=\frac{1+\sqrt{5}}{2}= 1,61803 \ldots$

et

$\displaystyle \overline{\phi} =\frac{1-\sqrt{5}}{2}=-0,61803\ldots$

Plus précisement, si on appelle $ F(n)$ le $ n$-ième nombre de Fibonacci ($ n \geq 0$), on a

$\displaystyle F(n)=
\frac{\phi^n-\overline{\phi}^n}{\sqrt{5}}$

(ce qu'on peut prouver par récurrence).

Exercice 1.3 
Ecrire un algorithme calculant le $ n$-ième nombre de Fibonacci en temps $ log_2(n)$.
Indications :

  1. Construire le vecteur \begin{displaymath}\vec{FIBO}(n)=\left(%
\begin{array}{c}
F(n)\\
F(n-1)\\
\end{array}%
\right)\end{displaymath} et exprimer $ \vec{FIBO}(n)$ en fonction de $ \vec{FIBO}(n-1)$ à l'aide d'une matrice de dimension $ 2 \times 2$ à déterminer.
  2. Calculer les puissances d'une matrice en utilisant la méthode alexandrine.

    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.




next up previous
suivant: Problème récurrent ( notre
Maylis Delest 2008-09-11