3MMALG11 Soutien S10 : Différence entre versions

Version du 10 avril 2017 à 13:40

On va travailler sur des listes chainées d'entiers. On testera les différences procédures à écrire grâce au squelette ci-dessous (à copier-coller dans un fichier s10_e1.adb) :

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

procedure S10_E1 is

   type Cellule;
   type Liste is access Cellule;
   type Cellule is record
      Val: Positive;
      Suiv: Liste;
   end record;

   procedure Liberer is new Ada.Unchecked_Deallocation(Cellule, Liste);

   procedure Afficher(L: Liste) is
      Cour: Liste;
   begin
      Cour := L;
      while Cour /= null loop
         Put(Cour.Val, Width => 0); Put(" -> ");
         Cour := Cour.Suiv;
      end loop;
      Put_Line("FIN");
   end Afficher;

   procedure Detruire(L: in out Liste) is
      Tmp: Liste;
   begin
      while L /= null loop
         Tmp := L;
         L := L.Suiv;
         Liberer(Tmp);
      end loop;
   end Detruire;

   procedure Generer(N: Natural; L: out Liste) is
   begin
      null; --  A COMPLETER !
   end Generer;

   procedure SupprimerMultiples(L: Liste) is
   begin
      null; --  A COMPLETER !
   end SupprimerMultiples;

   procedure SeparerUnDeux(L: in out Liste; L1, L2: out Liste) is
   begin
      null; --  A COMPLETER !
   end SeparerUnDeux;

   procedure FusionnerTriees(L1, L2: in out Liste; L: out Liste) is
   begin
      null; --  A COMPLETER !
   end FusionnerTriees;

   procedure SeparerLievreTortue(L: in out Liste; L1, L2: out Liste) is
   begin
      null; --  A COMPLETER !
   end SeparerLievreTortue;

   L, L1, L2: Liste;

begin
   for I in 1 .. 15 loop
      Put("N = "); Put(I, Width=>0); New_Line;
      Put("Liste initiale : "); Generer(I, L); Afficher(L);
--      Put("Liste des nombres premiers : "); SupprimerMultiples(L); Afficher(L);
--      Put_Line("Decoupage :");
--      SeparerUnDeux(L, L1, L2); Afficher(L1); Afficher(L2);
--      Put("Fusion triee : "); FusionnerTriees(L1, L2, L); Afficher(L);
--      Put_Line("Autre decoupage : ");
--      SeparerLievreTortue(L, L1, L2); Afficher(L1); Afficher(L2);
--      Detruire(L1); Detruire(L2);
      New_Line;
   end loop;
end S10_E1;

Génération de la liste initiale

Compléter la procédure Générer qui doit générer la liste ordonnée de tous les entiers supérieurs ou égaux à 2 et inférieurs ou égaux au paramètre N.

Par exemple, l'appel Generer(9) produira la liste :

2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

Suppression des multiples

Compléter la procédure SupprimerMultiples qui doit supprimer tous les éléments multiples d'un nombre premier élément précédent de la liste. On pose comme hypothèse que la liste initiale est une liste triée par ordre croissant et commençant par 2 (si elle n'est pas vide).

Par exemple, si la liste initiale est : 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

• le nombre premier courant est 2 et la première itération supprime tous les éléments multiples de 2 (4, 6, 8) ;
• le nombre premier suivant est 3 et la deuxième itération supprime les multiples de 3 (uniquement 9 car 6 a déjà été supprimé) ;
• le nombre premier suivant est 5 mais la troisième itération n'a pas de multiples à supprimer ;
• le nombre premier suivant est 7 mais la quatrième itération n'a pas de multiples à supprimer ;
• on arrive à la fin de la liste, qui ne contient plus que des nombres premiers : 2 -> 3 -> 5 -> 7.

On rappelle qu'on peut tester facilement si un nombre X est multiple de Y en regardant si le reste de la division entière X mod Y est nul.

Cet algorithme très classique s'appelle le Crible d'Ératosthène, d'après Ératosthène de Cyrène, mathématicien grec, -276 – -194.

Découpage d'une liste

Compléter la procédure SeparerUnDeux qui découpe la liste initiale L en deux listes L1 et L2, en repartissant les éléments dans chaque liste tour à tour (e.g. le premier élément va dans L1, le deuxième dans L2, le troisième dans L1, etc.).

La procédure doit travailler uniquement par modification du chainage, sans allocation ou suppression de cellule (à l'exception d'éléments fictifs).

Fusion triée

Compléter la procédure FusionnerTriee qui fusionne deux listes triées par ordre croissant L1 et L2 en une liste L également triée.

Exercice complémentaire

Pour vous entrainer, refaite la procédure de découpage en coupant la liste initiale en deux sous-listes de taille égale (à un près) en un seul parcours.

Indication : utiliser deux pointeurs, un qui avance à chaque tour de boucle et l'autre une fois sur deux.

procedure SeparerLievreTortue(L: in out Liste; L1, L2: out Liste);