3MMALG11 Soutien S11 : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
(Algorithmes récursifs sur des tableaux)
(Insertion d'un élément à sa place)
Ligne 127 : Ligne 127 :
 
Cas de base : si le tableau est de taille 0, on renvoie simplement le tableau composé de la valeur <tt>V</tt> : en Ada, cela s'écrit <tt>return (T'First => V);</tt>.
 
Cas de base : si le tableau est de taille 0, on renvoie simplement le tableau composé de la valeur <tt>V</tt> : en Ada, cela s'écrit <tt>return (T'First => V);</tt>.
  
 +
Hypothèse de récurrence : à vous de la trouver !
  
 +
Indice : là-encore, il faut raisonner avec le premier élément du tableau et sa fin.
 +
 +
Vous aurez besoin de savoir concatener des tableaux, on rappelle donc que :
 +
* si <tt>X</tt> est un caractère et <tt>T</tt> un tableau de caractères de taille N, alors <tt>X & T</tt> est le tableau de taille N + 1 composé de <tt>X</tt> comme premier élément et du contenu de <tt>T</tt> ensuite :
 +
* si <tt>T1</tt> et <tt>T2</tt> sont des tableaux de caractères, alors <tt>T1 & T2</tt> est le tableau de caractères contenant tous les éléments de <tt>T1</tt> puis tous les éléments de <tt>T2</tt>.
 +
 +
Note : on ne se préoccupera pas de performances dans cet exercice, les tableaux étant des structures de données statiques, ils se prêtent assez mal à la programmation fonctionnelle, mais on verra à la prochaine séance comment implanter ce même types d'algorithmes sur des structures de données dynamiques (listes chainées).
  
 
[[Catégorie:Première Année]]
 
[[Catégorie:Première Année]]
 
[[Catégorie:Informatique]]
 
[[Catégorie:Informatique]]
 
[[Catégorie:Ada]]
 
[[Catégorie:Ada]]

Version du 27 décembre 2013 à 15:17

On va travailler pendant cette séance sur des algorithmes récursifs appliqués à des tableaux. On testera les différences procédures à écrire grâce au squelette ci-dessous (à copier-coller dans un fichier s11_e1.adb) :

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

procedure S11_E1 is

   function Mult(X, Y: Positive; Decal: Natural := 0) return Positive is
      procedure Aff_Decal is
      begin
         for I in 1 .. Decal loop
            Put(" ");
         end loop;
      end Aff_Decal;

      Res: Positive;
   begin
      Aff_Decal; Put("X = "); Put(X, Width => 0);
      Put(", Y = "); Put(Y, Width => 0); New_Line;
      if Y = 1 then
         Res := X;
      else
         Res := X + Mult(X, Y - 1, Decal + 2);
      end if;
      Aff_Decal; Put("-> "); Put(Res, Width => 0); New_Line;
      return Res;
   end Mult;

   subtype Majuscules is Character range 'A' .. 'Z';

   type Tab is array(Integer range <>) of Majuscules;

--  A COMPLETER !
--   procedure Affiche(T: Tab) is

--  A COMPLETER !
--   procedure Affiche_Inv(T: Tab) is

--  A COMPLETER !
--   function Recherche(V: Majuscules; T: Tab) return Boolean is

--  A COMPLETER !
--   function Insere(V: Majuscules; T: Tab) return Tab is

--  A COMPLETER !
--   function Trie(T: Tab) return Tab is

--   T0: Tab(1 .. 0);
--   T1: constant Tab(1 .. 1) := (1 => 'A');
--   T2: constant Tab(1 .. 2) := ('B', 'A');
--   T3: constant Tab(1 .. 3) := ('A', 'B', 'C');
--   T4: constant Tab(1 .. 4) := ('D', 'C', 'B', 'A');
--   T5: constant Tab(1 .. 5) := ('C', 'A', 'E', 'D', 'B');

begin
   Put(Mult(3, 4), Width => 0); New_Line; New_Line;
   Put(Mult(3, 1), Width => 0); New_Line; New_Line;
   Put(Mult(1, 4), Width => 0); New_Line; New_Line;

--   Put("T0 : "); Affiche(T0); New_Line;
--   Put("T1 : "); Affiche(T1); New_Line;
--   Put("T2 : "); Affiche(T2); New_Line;
--   Put("T3 : "); Affiche(T3); New_Line;
--   Put("T4 : "); Affiche(T4); New_Line;
--   Put("T5 : "); Affiche(T5); New_Line; New_Line;

--   Put("T0i: "); Affiche_Inv(T0); New_Line;
--   Put("T1i: "); Affiche_Inv(T1); New_Line;
--   Put("T2i: "); Affiche_Inv(T2); New_Line;
--   Put("T3i: "); Affiche_Inv(T3); New_Line;
--   Put("T4i: "); Affiche_Inv(T4); New_Line;
--   Put("T5i: "); Affiche_Inv(T5); New_Line; New_Line;

--   Put_Line("Recherche de C :");
--   Put_Line("T0 : " & Boolean'Image(Recherche('C', T0)));
--   Put_Line("T1 : " & Boolean'Image(Recherche('C', T1)));
--   Put_Line("T2 : " & Boolean'Image(Recherche('C', T2)));
--   Put_Line("T3 : " & Boolean'Image(Recherche('C', T3)));
--   Put_Line("T4 : " & Boolean'Image(Recherche('C', T4)));
--   Put_Line("T5 : " & Boolean'Image(Recherche('C', T5))); New_Line;

--   Put("T0t: "); Affiche(Trie(T0)); New_Line;
--   Put("T1t: "); Affiche(Trie(T1)); New_Line;
--   Put("T2t: "); Affiche(Trie(T2)); New_Line;
--   Put("T3t: "); Affiche(Trie(T3)); New_Line;
--   Put("T4t: "); Affiche(Trie(T4)); New_Line;
--   Put("T5t: "); Affiche(Trie(T5)); New_Line;
end S11_E1;

Exercice préliminaire

Exécutez le squelette fourni et déroulez sur papier l'exécution de la fonction Mult pour comprendre l'arbre des appels récursifs.

Algorithmes récursifs sur des tableaux

On travaille sur des tableaux de caractères (majuscules) de tailles comprises entre 0 et 5. Toutes les fonctions et procédures à écrire doivent être récursives.

On fournit en général le ou les cas de base et l'hypothèse de récurrence des fonctions ou procédures à écrire, mais l'idée est que vous appreniez à les trouver par vous-mêmes, car c'est cette analyse du problème qui est le plus important dans l'écriture de primitives récursives.

Affichage d'un tableau de caractères

Ecrivez la procédure Affiche qui doit afficher le contenu du tableau dans l'ordre de ses indices croissants.

Cas de base : si le tableau est de taille 0 (c'est à dire si T'Length = 0), on ne fait rien.

Hypothèse de récurrence : si T(T'First) est le premier élément du tableau alors on affiche T(T'First) puis on affiche la fin du tableau (c'est à dire T(T'First + 1 .. T'Last)).

Affichage en sens inverse

Ecrivez maintenant la procédure Affiche_Inv qui affiche le tableau en sens inverse (c'est à dire dans le sens de ses indices décroissants).

Cette procédure est quasi-identique à la procédure Afficher : à vous de trouver l'hypothèse de récurrence qui change très légèrement le code à écrire.

Recherche d'une valeur

Ecrivez la fonction Recherche qui renvoie Vrai ssi la valeur V passée en paramètre est présente dans le tableau.

Cas de base : V n'est jamais présente dans un tableau de taille 0.

Hypothèse de récurrence : si le tableau contient au moins 1 élément, alors soit V est égale au premier élément du tableau, soit elle est présente dans la fin du tableau.

Insertion d'un élément à sa place

Ecrivez la fonction Insere qui insère la valeur V passée en paramètre à sa place dans le tableau T supposé trié par ordre croissant.

Cas de base : si le tableau est de taille 0, on renvoie simplement le tableau composé de la valeur V : en Ada, cela s'écrit return (T'First => V);.

Hypothèse de récurrence : à vous de la trouver !

Indice : là-encore, il faut raisonner avec le premier élément du tableau et sa fin.

Vous aurez besoin de savoir concatener des tableaux, on rappelle donc que :

  • si X est un caractère et T un tableau de caractères de taille N, alors X & T est le tableau de taille N + 1 composé de X comme premier élément et du contenu de T ensuite :
  • si T1 et T2 sont des tableaux de caractères, alors T1 & T2 est le tableau de caractères contenant tous les éléments de T1 puis tous les éléments de T2.

Note : on ne se préoccupera pas de performances dans cet exercice, les tableaux étant des structures de données statiques, ils se prêtent assez mal à la programmation fonctionnelle, mais on verra à la prochaine séance comment implanter ce même types d'algorithmes sur des structures de données dynamiques (listes chainées).