3MMALG11 Soutien S05

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

On va travailler dans cette séance sur des tableaux, en écrivant des procédures de recherche et de parcours (notamment des tris).

On complètera au fur et à mesure le programme suivant, à copier-coller dans un fichier s05_e1.adb :

with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;

procedure S05_E1 is

   type Tab is array(Natural range <>) of Character;

   Periode: constant Positive := 6;

   --  remplit le tableau avec A B C D E F A B C...
   procedure Init(T: in out Tab) is
   begin
      for I in T'Range loop
         T(I) := Character'Val(I mod Periode + Character'Pos('A'));
      end loop;
   end Init;

   procedure Affiche(T: Tab) is
   begin
      Put("Tableau (taille = "); Put(T'Length, Width => 0);
      Put(", indices dans ["); Put(T'First, Width => 0);
      Put(".."); Put(T'Last, Width => 0); Put("]) : ");
      for I in T'Range loop
         Put(T(I) & " ");
      end loop;
      New_Line;
   end Affiche;

   --  renvoie l'indice de la premiere occurrence du caractere C
   --    ou -1 s'il est absent du tableau
   --  function IndPremOcc(T: Tab; C: Character) return Integer is

   --  echange les valeurs des cases d'indices I et J du tableau T
   --  pre-condition : le tableau doit etre au moins de taille = 1
   --  procedure Echange(T: in out Tab; I, J: Integer) is

   --  inverse le contenu du tableau T
   --  procedure Inverse(T: in out Tab) is

   --  tri du nain de jardin
   --  procedure TriNain(T: in out Tab) is

   --  tri par selection du minimum
   --  procedure TriMin(T: in out Tab) is

   --  tri par insertion
   --  procedure TriIns(T: in out Tab) is

   procedure Test(T: in out Tab) is
   begin
      Init(T); Affiche(T);
      --  Put("Indice de la premiere occurence de 'A' = ");
      --  Put(IndPremOcc(T, 'A'), Width => 0); New_Line;
      --  Put("Indice de la premiere occurence de 'F' = ");
      --  Put(IndPremOcc(T, 'F'), Width => 0); New_Line;
      --  Put("Indice de la premiere occurence de 'Z' = ");
      --  Put(IndPremOcc(T, 'Z'), Width => 0); New_Line;
      --  Put_Line("Inversion du tableau :");
      --  Inverse(T); Affiche(T);
      --  Put_Line("Tri du nain de jardin :");
      --  Init(T); TriNain(T); Affiche(T);
      --  Put_Line("Tri par selection du minimum :");
      --  Init(T); TriMin(T); Affiche(T);
      --  Put_Line("Tri par insertion :");
      --  Init(T); TriIns(T); Affiche(T);
   end Test;

begin
   for I in Periode - 1 .. Periode - 1 + 10 loop
      declare
         T: Tab(Periode .. I);
      begin
         Put("----- Tableau de taille "); Put(T'Length, Width => 0);
         Put_Line(" -----");
         Test(T); New_Line;
      end;
   end loop;
end S05_E1;

On voit qu'on travaille sur des tableaux de tailles variant entre 0 et 10, et contenant des caractères (ce qui ne change absolument rien par rapport à un tableau d'entiers par exemple). Vous décommenterez au fur et à mesure procédures et fonctions à implanter, ainsi que les tests pertinents dans le programme principal.

Exercice 1 : recherche de la première occurrence d'un élément

Commencer par écrire la fonction IndPremOcc définie comme suis :

function IndPremOcc(T: Tab; C: Character) return Integer;

Exercice 2 : inversion d'un tableau

Ecrire ensuite une procédure Echange qui échange le contenu de deux cases du tableau :

procedure Echange(T: in out Tab; I, J: Integer);

S'en servir pour écrire une procédure Inverse qui inverse le contenu du tableau :

procedure Inverse(T: in out Tab);

Exercice 3 : tri du nain de jardin

Un nain de jardin en train de trier des pots de fleurs.

On va travailler dans cet exercice sur un tri itératif appelé le tri du nain de jardin. Son principe est très simple : un nain de jardin cherche à trier des pots de fleurs par taille croissante. Il regarde le pot devant lui : s'il est plus petit que le pot à sa droite, le nain avance d'un pas vers la droite (s'il n'est pas arrivé à la fin de la file de pots). Si le pot devant lui est plus grand que le pot à sa droite, le nain échange les deux pots, et recule d'un pas vers la gauche (s'il n'est pas revenu au début de la file de pots). Il s'agit d'un tri de complexité en O(n^2) mais qui a la caractéristique intéressante d'avoir un coût linéaire si le tableau initial est déjà trié.

Le prototype de la procédure à écrire est le suivant : procedure TriNain(T: in out Tab);.

Exercice 4 : tri par sélection

On va maintenant implanter une procédure de Tri selon l'algorithme de la sélection du minimum. Le principe est simple :

  • à la Ième itération, on sait que T(T'First .. I - 1) est trié et T(I .. T'Last) n'est pas trié
  • pour passer à la (I + 1)ème itération, on doit :
    • chercher l'élément minimum dans la partie non-triée du tableau
    • l'échanger avec le contenu de T(I)
    • avancer I d'une case

Il s'agit donc d'un tri en O(n^2) vu qu'on va parcourir le sous-tableau non-trié pour chaque élément du tableau. Le prototype de la procédure à implanter est procedure TriMin(T: in out Tab);

Exercice 5 : tri par insertion

Finalement on va implanter le tri par insertion, donc le principe est le suivant :

  • à la Ième itération, on sait que T(T'First .. I - 1) est trié et T(I .. T'Last) n'est pas trié
  • pour passer à la (I + 1)ème itération, on doit :
    • sauvegarder la valeur V contenue dans T(I)
    • rechercher l'indice J tel que T'First <= J < I et T(J) <= V , en décalant au passage tous les T(K) > V d'une case vers la droite
    • recopier V dans la case T(J + 1)
    • avancer I d'une case.

Il s'agit là-aussi d'un tri en O(n^2). La procédure a implanter est donc procedure TriIns(T: in out Tab);