3MMALG11 Soutien S04 : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
m (A déprotégé « 3MMALG11 Soutien S04 »)
 
Ligne 1 : Ligne 1 :
 +
{{Maintenance uniquement par enseignants}}
 
== Programmation d'une pile bornée d'entiers ==
 
== Programmation d'une pile bornée d'entiers ==
  

Version actuelle en date du 11 avril 2017 à 09:06

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)

Programmation d'une pile bornée d'entiers

On va travailler dans cet exercice sur une structure de données très classique : une pile. On considère ici que cette pile contiendra des entiers, mais les algorithmes que l'on va implanter ne changeraient bien sûr pas si on travaillait sur d'autres types de données.

Une pile est une structure de donnée implantant une politique "premier entré, dernier sorti" : si on empile des assiettes les unes au dessus des autres, on doit d'abord enlever les assiettes du dessus (celles empilées en dernier) avant d'accéder à celles du dessous (celles empilées en premier).

On va définir un module de gestion de pile bornées sous la forme d'un type abstrait de données. Cette notion est légèrement différente de la notion de machine à états que l'on a déjà utilisé par exemple pour le module de gestion des suites d'entiers :

  • dans une machine à état, toutes les variables manipulées sont internes au module, et on ne peut donc manipuler qu'une seule instance de la machine ;
  • dans un type abstrait de données, on défini un type qui peut être instancié autant de fois que nécessaire : on peut donc par exemple ici définir plusieurs variables de type « pile » et les manipuler séparément.

L'interface du module que l'on va implanter est la suivante (code à copier-coller dans le fichier pilebornee.ads) :

package PileBornee is

   type Pile is private;

   --  Initialise la pile a vide
   procedure Initialiser(P: out Pile);

   --  Insere l'element X au sommet de la pile
   procedure Empiler(P: in out Pile; X: Integer);

   --  Retire l'element en sommet de pile et renvoie sa valeur
   procedure Depiler(P: in out Pile; X: out Integer);

   --  Recopie le contenu de la pile Src dans la pile Dst
   procedure Recopier(Src: Pile; Dst: out Pile);

   --  Affiche le contenu de la pile dans l'ordre d'empilement
   procedure Afficher(P: Pile);

   --  Exception levee ssi on empile un element dans une pile deja pleine
   ExcPleine: exception;

   --  Exception levee ssi on depile un element d'une pile deja vide
   ExcVide: exception;

private

   --  En Ada, un tableau peut etre indice par des valeurs scalaires
   --    quelconques : on choisi donc un intervalle original pour tester
   type Tableau is array (-5 .. 4) of Integer;

   type Pile is record
      --  Tableau stockant les valeurs contenues dans la pile
      Tab: Tableau;
      --  Indice du sommet de pile, c'est a dire de la case contenant la
      --    derniere valeur empilee
      Som: Integer;
   end record;

end PileBornee;

On définit donc via ce module le type abstrait Pile et des primitives (fonctions et procédures) qui permettent de manipuler des instances de ce type. La partie privée du module précise comment est implanté concretement une pile bornée d'entiers, mais n'est pas accessible aux programmes utilisant le module : par exemple, il serait impossible pour un programme d'accéder directement à un des éléments du tableau Tab.

On pourra tester le module implanté grâce au programme principal ci-dessous (à copier-coller dans le fichier s04_e1.adb) :

with Ada.Text_IO, PileBornee;
use Ada.Text_IO, PileBornee;

procedure S04_E1 is

   P1, P2: Pile;
   X: Integer;

   procedure Remplir(P: in out Pile) is
   begin
      Initialiser(P);
      Afficher(P);
      for I in -2 .. 7 loop
         Empiler(P, I);
         Afficher(P);
      end loop;
      --  On va volontairement provoquer une ExcPleine
      Empiler(P, -5);
   exception
      when ExcPleine =>
         Put_Line("La pile etait bien pleine.");
   end Remplir;

   procedure Vider(P: in out Pile) is
   begin
      --  On va volontairement provoquer une ExcVide
      Afficher(P);
      loop
         Depiler(P, X);
         Put_Line(" Valeur depilee = " & Integer'Image(X));
         Afficher(P);
      end loop;
   exception
      when ExcVide =>
         Put_Line("La pile est maintenant vide.");
   end Vider;

begin
   Put_Line("Remplissage de P1...");
   Remplir(P1);
   Put_Line("Recopie de P1 dans P2...");
   Recopier(P1, P2);
   Put_Line("Vidage de P1...");
   Vider(P1);
   Put_Line("Contenu de P2 :");
   Afficher(P2);
   Put_Line("Fin normale du programme.");
end S04_E1;

Implantez donc le module de gestion de pile bornées dans le fichier pilebornee.adb. Pour rendre ce module flexible, pensez à utiliser les attributs 'First et 'Last pour rendre votre code indépendant de l'intervalle des indices du type Tableau.

Par exemple, vous pouvez implanter la fonction d'affichage du contenu de la pile comme suit :

   procedure Afficher(P: Pile) is
   begin
      for I in Tableau'First .. P.Som loop
         Put(P.Tab(I), Width => 3);
         Put(" ");
      end loop;
      for I in P.Som + 1 .. Tableau'Last loop
         Put("  X ");
      end loop;
      New_Line;
   end Afficher;

Programmation d'une file bornée d'entiers

On va maintenant implanter de façon très similaire un module de gestion de files bornées. Une file implante la politique « premier entré, premier sorti » : on insère les éléments d'un côté et on les retire de l'autre.

L'interface du module à implanter est la suivante (à copier-coller dans le fichier filebornee.ads) :

package FileBornee is

   type File is private;

   --  Initialise la File a vide
   procedure Initialiser(F: out File);

   --  Insere l'element X dans la file
   procedure Inserer(F: in out File; X: Integer);

   --  Retire l'element le plus ancien de la file et renvoie sa valeur
   procedure Retirer(F: in out File; X: out Integer);

   --  Affiche le contenu de la File dans l'ordre d'insertion
   procedure Afficher(F: File);

   --  Exception levee ssi on insere un element dans une File deja pleine
   ExcPleine: exception;

   --  Exception levee ssi on retire un element d'une File deja vide
   ExcVide: exception;

private

   type Tableau is array (-5 .. 4) of Integer;

   type File is record
      --  Tableau stockant les valeurs contenues dans la File
      Tab: Tableau;
      --  Indice de la case contenant l'element le plus ancient
      Prem: Integer;
      --  Nombre d'elements contenus dans la file
      Taille: Natural;
   end record;

end FileBornee;

Le module pourra être testé grâce au programme suivant (à copier-coller dans le fichier s04_e2.adb) :

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

procedure S04_E2 is

   F: File;
   C: Character;
   X: Integer;

begin
   Initialiser(F);
   loop
      Put_Line("Contenu actuel de la file :");
      Afficher(F);
      Put("> I pour inserer, R pour retirer et Q pour quitter : ");
      Get(C);
      if (C = 'i') or (C = 'I') then
         Put("Valeur a inserer : ");
         Get(X);
         Inserer(F, X);
      elsif (C = 'r') or (C = 'R') then
         Retirer(F, X);
         Put("Valeur retiree : ");
         Put(X);
         New_Line;
      elsif (C = 'q') or (C = 'Q') then
         exit;
      else
         Put_Line("Commande '" & C & "' inconnue");
      end if;
   end loop;
end S04_E2;

Vous devez implanter le module de gestion de files bornées de façon indépendante de l'intervalle des indices du tableau stockant les valeurs, et sans déplacer les valeurs contenus dans celui-ci lors d'une insertion ou d'une suppression. Pour cela, le plus simple est de gérer le tableau de façon circulaire (i.e. si on insère une valeur dans la dernière case à la fin du tableau, et s'il y a des cases libres au début de celui-ci, alors la prochaine insertion se fera au début du tableau).

Pour afficher le contenu de la file, vous pourrez utiliser la procédure Afficher ci-dessous :

   procedure Afficher(F: File) is
      Reste, I: Integer;
   begin
      Reste := F.Taille - (Tableau'Last - F.Prem + 1);
      I := Tableau'First;
      while Reste > 0 loop
         Put(F.Tab(I), Width => 3);
         Put(" ");
         I := I + 1;
         Reste := Reste - 1;
      end loop;
      while I < F.Prem loop
         Put("  X ");
         I := I + 1;
      end loop;
      while (I <= Tableau'Last) and (I < F.Prem + F.Taille) loop
         Put(F.Tab(I), Width => 3);
         Put(" ");
         I := I + 1;
      end loop;
      while I <= Tableau'Last loop
         Put("  X ");
         I := I + 1;
      end loop;
      New_Line;
   end Afficher;

Indices pour le calcul des indices dans un tableau circulaire

Lorsque l'on va vouloir insérer ou retirer des éléments de la file, il va falloir calculer l'indice de la case du tableau où insérer ou d'où retirer l'élément, ce qui est significativement plus difficile pour un tableau circulaire que pour un tableau classique.

Supposons qu'à un certain point de l'exécution du programme, le tableau soit dans l'état suivant :

<--------- Tableau'Length = 10 --------->

Tableau'First              F.Prem    Tableau'Last
  |                           |       |
  v                           v       v
-----------------------------------------
| 5 | 0 | 3 | ? | ? | ? | ? | 7 | 2 | 1 |
-----------------------------------------

et F.Nb = 6

où ? indique une case vide.

Pour l'insertion, on veut donc calculer l'indice Ind qu'on utilisera pour copier la valeur X dans le tableau : F.Tab(Ind) := X.

On dispose de l'indice de l'élément le plus ancien de la file (F.Prem) et du nombre d'éléments dans la file (F.Nb). Si on travaillait sur un tableau non-circulaire, il serait très facile de calculer l'indice de la case où insérer X, par Ind := F.Prem + F.Nb.

L'opérateur mod (qui calcule le reste de la division entière entre ses deux opérandes) nous permet de gérer facilement le côté circulaire du tableau : SI ET SEULEMENT SI Tableau'First = 0, alors on peut calculer Ind := (F.Prem + F.Nb) mod Tableau'Length pour trouver l'indice de la case où insérer l'élément (dans l'exemple du tableau ci-dessus, on voudrait insérer X dans la 4ème case du tableau, donc la case d'indice 3 puisqu'on commence à compter à partir de 0, et on a bien Ind := (7 + 6) mod 10 = 13 mod 10 = 3).

Mais en pratique, les indices du tableau ne commencent pas forcément à partir de 0 (dans l'exemple de l'exercice 2, on a décidé arbitrairement qu'ils commençaient à -5). On doit donc « recaler » l'indice de début du tableau sur 0 avant de faire le modulo, puis le recaler dans l'autre sens après. Plus précisément, on doit donc calculer Ind := ((F.Prem - Tableau'First + F.Nb) mod Tableau'Length) + Tableau'First.

Si on suppose comme dans l'exercice que les indices commencent à -5, on vérifie que la formule est correcte : Ind := ((2 - -5 + 6) mod 10) + -5 = (13 mod 10) - 5 = 3 - 5 = -2 ce qui correspond bien à l'indice de la 4ème case du tableau si les indices commencent à -5.

Le même raisonnement peut bien sûr être appliqué dans le cas de la suppression d'un élément de la file.