3MMALG11 Soutien S11 : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
 
(4 révisions intermédiaires par 2 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
On va travailler aujourd'hui sur l'examen de TP de janvier 2013, dont vous pouvez récupérer [[Media:3MMALG11_soutien_s11.pdf|l'énoncé]] et les [[Media:3MMALG11_soutien_s11.zip|sources de départ]].
+
{{Maintenance uniquement par enseignants}}
  
Le but de l'exercice est de pratiquer un véritable examen de TP, donc il n'y a pas d'explications supplémentaires : à vous de traiter le sujet comme s'il s'agissait d'une véritable épreuve !
+
== Correction de la procédure <tt>FusionnerTriees</tt> ==
<!--
+
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 <tt>s11_e1.adb</tt>) :
+
 
<pre>
 
<pre>
with Ada.Text_IO, Ada.Integer_Text_IO;
+
  procedure FusionnerTriees(L1, L2: in out Liste; L: out Liste) is
use Ada.Text_IO, Ada.Integer_Text_IO;
+
       Fictif: Liste;
 
+
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
 
   begin
       Aff_Decal; Put("X = "); Put(X, Width => 0);
+
       Fictif := new Cellule; L := Fictif;
       Put(", Y = "); Put(Y, Width => 0); New_Line;
+
       while L1 /= null and L2 /= null loop
       if Y = 1 then
+
        if L1.Val <=  L2.Val then
         Res := X;
+
            L.Suiv := L1;
 +
            L := L1;
 +
            L1 := L1.Suiv;
 +
        else
 +
            L.Suiv := L2;
 +
            L := L2;
 +
            L2 := L2.Suiv;
 +
        end if;
 +
      end loop;
 +
      --  C'est forcement L1 XOR L2 qui est null en sortie
 +
       if L1 /= null then
 +
         L.Suiv := L1;
 +
        L1 := null;
 
       else
 
       else
         Res := X + Mult(X, Y - 1, Decal + 2);
+
         L.Suiv := L2;
 +
        L2 := null;
 
       end if;
 
       end if;
       Aff_Decal; Put("-> "); Put(Res, Width => 0); New_Line;
+
       L := Fictif.Suiv;
       return Res;
+
       Liberer(Fictif);
   end Mult;
+
   end FusionnerTriees;
 +
</pre>
  
  subtype Majuscules is Character range 'A' .. 'Z';
+
== Examen de TP 2013-2014 ==
  
  type Tab is array(Integer range <>) of Majuscules;
+
On va travailler aujourd'hui sur l'examen de TP de janvier 2013, dont vous pouvez récupérer [[Media:3MMALG11_soutien_s11.pdf|l'énoncé]] et les [[Media:3MMALG11_soutien_s11.zip|sources de départ]].
  
--  A COMPLETER !
+
Le but de l'exercice est de pratiquer un véritable examen de TP, donc il n'y a pas d'explications supplémentaires : à vous de traiter le sujet comme s'il s'agissait d'une véritable épreuve !
--  procedure Affiche(T: Tab) is
+
  
--  A COMPLETER !
+
Pour tester la procédure <tt>Echanger_Cellules</tt>, vous pouvez ajouter le bout de code suivant dans le programme principal :
--  procedure Affiche_Inv(T: Tab) is
+
<pre>
 
+
  declare
--  A COMPLETER !
+
      T: Tab(1..5);
--  function Recherche(V: Majuscules; T: Tab) return Boolean is
+
      L: Liste;
 
+
  begin
--  A COMPLETER !
+
      for I in T'Range loop
--  function Insere(V: Majuscules; T: Tab) return Tab is
+
        T(I) := I;
 
+
      end loop;
--  A COMPLETER !
+
      Afficher_Tableau(T);
--  function Trie(T: Tab) return Tab is
+
      Init_Liste(L, T);
 
+
      Afficher_Liste(L, False);
--  T0: Tab(1 .. 0);
+
      Echanger_Cellules(L.Tete.Suiv.Suiv);
--  T1: constant Tab(1 .. 1) := (1 => 'A');
+
      Afficher_Liste(L, False);
--  T2: constant Tab(1 .. 2) := ('B', 'A');
+
  end;
--  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;
+
 
</pre>
 
</pre>
  
== Exercice préliminaire ==
 
 
Exécutez le squelette fourni et déroulez sur papier l'exécution de la fonction <tt>Mult</tt> 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 <tt>Affiche</tt> 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 <tt>T'Length = 0</tt>), on ne fait rien.
 
 
Hypothèse de récurrence : si <tt>T(T'First)</tt> est le premier élément du tableau alors on affiche <tt>T(T'First)</tt> puis on affiche la fin du tableau (c'est à dire <tt>T(T'First + 1 .. T'Last)</tt>).
 
 
=== Affichage en sens inverse ===
 
 
Ecrivez maintenant la procédure <tt>Affiche_Inv</tt> 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 <tt>Afficher</tt> : à 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 <tt>Recherche</tt> qui renvoie Vrai ssi la valeur <tt>V</tt> passée en paramètre est présente dans le tableau.
 
 
Cas de base : <tt>V</tt> 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 <tt>V</tt> 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 <tt>Insere</tt> qui insère la valeur <tt>V</tt> passée en paramètre à sa place dans le tableau <tt>T</tt> '''supposé trié par ordre croissant'''.
 
 
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 type d'algorithmes sur des structures de données dynamiques (listes chainées).
 
 
=== Tri par insertion ===
 
 
Ecrivez enfin la procédure <tt>Trie</tt> qui trie le tableau par ordre croissant selon l'algorithme du tri par insertion.
 
 
Cas de base : un tableau de taille 0 ou 1 est déjà trié.
 
 
Hypothèse de récurrence : si on appelle <tt>T'</tt> le tableau obtenu en triant la fin de T, alors il suffit d'insérer le premier élément de <tt>T</tt> à sa place dans <tt>T'</tt>.
 
-->
 
 
[[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 actuelle en date du 11 avril 2017 à 09:30

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)


Correction de la procédure FusionnerTriees

   procedure FusionnerTriees(L1, L2: in out Liste; L: out Liste) is
      Fictif: Liste;
   begin
      Fictif := new Cellule; L := Fictif;
      while L1 /= null and L2 /= null loop
         if L1.Val <=  L2.Val then
            L.Suiv := L1;
            L := L1;
            L1 := L1.Suiv;
         else
            L.Suiv := L2;
            L := L2;
            L2 := L2.Suiv;
         end if;
      end loop;
      --  C'est forcement L1 XOR L2 qui est null en sortie
      if L1 /= null then
         L.Suiv := L1;
         L1 := null;
      else
         L.Suiv := L2;
         L2 := null;
      end if;
      L := Fictif.Suiv;
      Liberer(Fictif);
   end FusionnerTriees;

Examen de TP 2013-2014

On va travailler aujourd'hui sur l'examen de TP de janvier 2013, dont vous pouvez récupérer l'énoncé et les sources de départ.

Le but de l'exercice est de pratiquer un véritable examen de TP, donc il n'y a pas d'explications supplémentaires : à vous de traiter le sujet comme s'il s'agissait d'une véritable épreuve !

Pour tester la procédure Echanger_Cellules, vous pouvez ajouter le bout de code suivant dans le programme principal :

   declare
      T: Tab(1..5);
      L: Liste;
   begin
      for I in T'Range loop
         T(I) := I;
      end loop;
      Afficher_Tableau(T);
      Init_Liste(L, T);
      Afficher_Liste(L, False);
      Echanger_Cellules(L.Tete.Suiv.Suiv);
      Afficher_Liste(L, False);
   end;