ED n°10-corriges

ED n°10 -- Algorithmique et Programmation --- Corrigé

Objectifs

La Généricité

Exercice 1

Soit la procédure ordre

procedure ordre(A,B: in out Integer) is
-- A la fin de l'exécution, A contient la plus grande valeur
    tmp:Integer:=A;
begin
    if (A>B)
    then A:=B;
    else B:=tmp;
    end if;
end ordre;

Question 1

Généraliser cette procédure pour un type générique discrêt.

-- Déclaration de la procédure générique
generic
type T is (<>);
procedure ordre(A,B: in out T);

-- Déclaration du corps de la procédure générique
procedure ordre(A,B: in out T) is
-- A la fin de l'exécution, A contient la plus grande valeur
    tmp:T:=A;
begin
    if (A>B)
    then A:=B;
    else B:=tmp;
    end if;
end ordre;

Question 2

Généraliser cette procédure pour un type générique quelconque.

-- Déclaration de la procédure générique
generic
type T is private;
with function ">"(X,Y:T) return boolean is <>;
procedure ordre(A,B: in out T);

-- Déclaration du corps de la procédure générique
procedure ordre(A,B: in out T) is
-- A la fin de l'exécution, A contient la plus grande valeur
    tmp:T:=A;
begin
    if (A>B)
    then A:=B;
    else B:=tmp;
    end if;
end ordre;

Question 3

On souhaite trier un tableau de cartes (type Carte). Chaque Carte est caractérisée par un numéro (positif), un nom (chaine de 10 caractères) et une catégorie dont les valeurs possibles sont : poussin, minime, cadet, junior, senior, veteran. On trie les cartes selon leur numéro.
Appliquer la procédure ordre générique au tri en ordre décroissant dont l'algorithme suit :

-- soit à trier le tableau t(a..b)
-- soit nun indice du tableau
début
n <- b;
tant que n>a faire
    pour i dans a..n-1 faire
        ordre(t(i),t(i+1));
    fin pour;
    n <- n-1;
fin tant que;
fin;

type Categorie is (poussin,minime,cadet,junior,senior,veteran);
type Carte is
    record
        num:Positive;
        nom:String(1..10);
        cat:Categorie;
    end record;
type TabCartes is array(Positive range <>) of Carte;
function ">"(X,Y:Carte) return Boolean is
begin
    return X.num>Y.num;
end ">";

pocedure ordreCarte is new ordre(Carte,">");

procedure triCartes(t:in out TabCartes) is
    n:=t'last;
begin
    loop
    exit when n<=t'first;
        for i in t'first..n-1 loop
            ordreCarte(t(i),t(i+1));
        end loop;
    n:=n-1;
end triCartes;

Exercice 2

Soit la procédure de recherche par dichotomie de l'indice d'un élément dans un tableau d'entiers :

type tabEntiers is array(positive range <>) of integer;
nonTrouve:exception;

function rechercheDicho (x:integer;t:tabEntiers) return positive is
    i:positive:=t'first;
    j:positive:=t'last;
    milieu:positive;
begin
    if j<i
    then
       raise nonTrouve;
    else -- j>=i
        milieu:=(i+j)/2;
       if t(milieu) = x
       then
       return milieu;
       elsif t(milieu) > x
       then
           return rechercheDicho(x,t(i..milieu-1));
       else
           return rechercheDicho(x,t(milieu+1,j));
       endif;
    endif;
end rechercheDicho;

Question 1

Comprendre cette fonction

Question 2

Généraliser cette fonction pour un tableau d'éléments de type quelconque;

generic
type Elt is private;
type Tableau is array(Positive range <>) of Elt;
with function ">"(A,B:Elt) return Boolean is <>;
function recherche_dicho (x:Elt;t:Tableau) return Positive;

function recherche_dicho (x:Elt;t:Tableau) return Positive is
    i:positive:=t'first;
    j:positive:=t'last;
    milieu:Positive;
    nonTrouve:exception;
begin
    if j<i
    then
       raise nonTrouve;
    else -- j>=i
        milieu:=(i+j)/2;
       if t(milieu) = x
       then
        return milieu;
       elsif t(milieu) > x
        then
            return recherche_dicho(x,t(i..milieu-1));
        else
            return recherche_dicho(x,t(milieu+1..j));
       end if;
    end if;
end recherche_dicho;

Question 3

Généraliser cette fonction pour un tableau indicé par un type discrêt quelconque d'éléments de type quelconque;

generic
type Elt is private;
type Indice is (<>);
type Tableau is array(Indice) of Elt;
with function ">"(A,B:Elt) return Boolean is <>;
function recherche_dicho (x:Elt;t:Tableau) return Positive;

function recherche_dicho (x:Elt;t:Tableau) return Positive is
    i:Indice:=t'first;
    j:Indice:=t'last;
    milieu:Indice;
    nonTrouve:exception;
begin
    if j<i
    then
       raise nonTrouve;
    else -- j>=i
        milieu:=Indice'val(Indice'pos(i)+Indice'pos(j)/2);
       if t(milieu) = x
       then
       return milieu;
       elsif t(milieu) > x
       then
           return recherche_dicho(x,t(i..Indice'pred(milieu));
       else
           return recherche_dicho(x,t(Indice'succ(milieu)..j));
       end if;
    end if;
end recherche_dicho;

Question 4

Instancier cette fonction pour rechercher un caractère dans un tableau indicé par des entiers.

type TabEntiers is array(Integer Range <>) of Character;
function ">"(X,Y:Character) return Boolean is
begin
return Character'pos(X)>Character'pos(Y);
end ">";
function recherche_car is new recherche_dicho(Character,Integer,TabEntiers,">");

Question 5

Instancier cette fonction pour rechercher l'indice d'un produit, représenté par sa référence (String) et son prix (float) dans un tableau indicé par des enitiers positifs.

with Ada.Integer_Text_io;use Ada.Integer_Text_io;
with Ada.Text_io;use Ada.Text_io;
with recherche_dicho;

procedure exo2_q4 is

type Produit is
    record
        ref: String(1..5);
        prix:Float;
    end record;

type TabProduit is array(Positive range <>) of Produit;

function ">"(X,Y:Produit) return Boolean is
begin
return X.prix>Y.prix;
end ">";

-- instanciation de la fonction recherche_dicho
function recherche_produit is new recherche_dicho(Produit,Positive,TabProduit,">");

unTab:TabProduit(5..9):=(("aaaaa",45.7),("bbbbb",67.8),("ccccc",87.2),("ddddd",48.9),("eeeee",56.8));

begin
put("indice du produit ccccc dans le tableau :");
put(recherche_produit(("ccccc",87.2),unTab));
end exo2_q4;

Question 6

Ecrire une procédure cliente pour la question 5.

Exercice 3

On veut représenter un ensemble d'entiers ( au sens mathématique du terme) par un paquetage. Ce paquetage traduira le type abstrait de données Ensemble . Les opérations définies sur ce TAD sont :

    ensembleVide : -> Ensemble              -- crée un Ensemble
    estVide : Ensemble -> Boolean           -- teste si un Ensemble est vide
    cardinal : Ensemble -> Natural           -- retourne le nombre d'éléments de l'Ensemble
    unElement : Ensemble -> Integer           -- retourne un élément quelconque de l'Ensemble sans l'enlever de l'Ensemble
    appartient : Integer*Ensemble -> Boolean     -- teste si l'élément appartient à l'Ensemble
    ajoute : Integer*Ensemble -> Ensemble        -- ajoute un élément à l'Ensemble si celui-ci n'appartient pas déjà à l'Ensemble
    enleve : Integer*Ensemble -> Ensemble        -- enlève l'élément de l'Ensemble si celui-ci appartient à l'Ensemble;
                                            -- ne fait rien sinon.

On choisit de représenter un Ensemble par un article contenant le tableau de ses éléments et sa taille.

Question 1

Ecrire la spécification du paquetage lesEnsembles qui exporte le type Ensemble muni de ses opérations.

package ensembles is
-- ensemble d'entiers (Integer)
type Ensemble is private;
TAILLE_MAX: constant Positive:=100;
function ensembleVide return Ensemble;
function estVide(E:Ensemble) return Boolean;
function cardinal(E:Ensemble) return Natural;
function unElement(E:Ensemble) return Integer;
function appartient(X:Integer;E:Ensemble) return Boolean;
procedure ajouter(X:in Integer;E:in out Ensemble);
procedure enlever(X:in Integer;E:in out Ensemble);
private
type Tableau is array(Positive range 1..TAILLE_MAX) of Integer;
type Ensemble is
record
taille:Natural;
tab:Tableau;
end record;
end ensembles;

Question 2

Ecrire un client qui utilise le paquetage ensembles pour créer l'Ensemble ={1,2,3,4,5,6}, l'affiche , retire tous les éléments jusqu'à l'élément 4 et enfin affiche l'ensemble.

with ensembles; use ensembles;
with Ada.Integer_Text_io; use Ada.Integer_Text_io
procedure exo3_q2 is

ens:Ensemble:=ensembleVide;

begin
-- Création de l'ensemble
for i in 1..6 loop
ajouter(i,ens);
end loop;
-- Affichage des éléments de l'ensemble
declare
ensBis:Ensemble:=ens;
begin
for i in reverse 1..cardinal(ensBis) loop
put(i);put(" eme element : ");put(unElement(ensBis));
new_line;
enlever(unElement(ensBis),ensBis);
end loop;
end;
-- Suppression des éléments jusquà l'élément 4
loop
exit when unElement(ens)=4;
exit when estVide(ens);
enlever(unElement(ens),ens);
end loop;
-- Affichage des éléments du nouvel ensemble
declare
ensBis:Ensemble:=ens;
begin
for i in reverse 1..cardinal(ensBis) loop
put(i);put(" eme element : ");put(unElement(ensBis));
new_line;
enlever(unElement(ensBis),ensBis);
end loop;
end;

end exo3_q2;

Question 3

Ecrire le corps du paquetage.

package body ensembles is

ensembleVideEx,ensemblePleinEx : exception;

function ensembleVide return Ensemble is
begin
return (taille=>0,tab=>(others=>0));
end ensembleVide;

function estVide(E:Ensemble) return Boolean is
begin
return E.taille=0;
end estVide;

function cardinal(E:Ensemble) return Natural is
begin
return E.taille;
end cardinal;

function unElement(E:Ensemble) return Integer is
-- on retourne le dernier élément
begin
if E.taille>0
then
raise ensembleVideEx;
else
return E.tab(E.taille);
end unElement;

function appartient(X:Integer;E:Ensemble) return Boolean is
begin
for i in 1..E.taille loop
   if E.tab(i)=X
   then
    return true;
   end if;
end loop;
return false;
end appartient;

procedure ajouter(X:in Integer;E:in out Ensemble) is
begin
if not appartient(X,E)
then
   if E.taille<=TAILLE_MAX
   then
    raise ensemblePleinEx;
   else
    E.taille:=E.taille+1;
    E.tab(E.taille):=X;
   end if;
end if;
end ajouter;

procedure enlever(X:in Integer;E:in out Ensemble) is
begin
for i in reverse 1..E.taille loop
   if E.tab(i)=X
   then
    -- on décale
    for j in i..E.taille-1 loop
     E.tab(j):=E.tab(j+1);
    end loop;
    -- on modifie la taille
    E.taille:=E.taille-1;
    exit;
   end if;
end loop;
end enlever;

end ensembles;

Question 4

Généraliser le paquetage aux Ensemble dont les éléments sont de type quelconque.

generic
    type T is private;
package ensembles_generic is
-- ensemble d'entiers (Integer)
type Ensemble is private;
TAILLE_MAX: constant Positive:=100;
function ensembleVide return Ensemble;
function estVide(E:Ensemble) return Boolean;
function cardinal(E:Ensemble) return Natural;
function unElement(E:Ensemble) return T;
function appartient(X:T;E:Ensemble) return Boolean;
procedure ajouter(X:in T;E:in out Ensemble);
procedure enlever(X:in T;E:in out Ensemble);
private
type Tableau is array(Positive range 1..TAILLE_MAX) of T;
type Ensemble is
record
   taille:Natural;
   tab:Tableau;
end record;
end ensembles_generic;

package body ensembles_generic is
ensembleVideEx,ensemblePleinEx : exception;

function ensembleVide return Ensemble is
E:Ensemble;
begin
E.taille:=0;
return E;
end ensembleVide;

function estVide(E:Ensemble) return Boolean is
begin
return E.taille=0;
end estVide;

function cardinal(E:Ensemble) return Natural is
begin
return E.taille;
end cardinal;

function unElement(E:Ensemble) return T is
-- on retourne le dernier élément
begin
if E.taille>0
then
raise ensembleVideEx;
else
return E.tab(E.taille);
end unElement;

function appartient(X:T;E:Ensemble) return Boolean is
begin
for i in 1..E.taille loop
   if E.tab(i)=X
   then
    return true;
   end if;
end loop;
return false;
end appartient;

procedure ajouter(X:in T;E:in out Ensemble) is
begin
if not appartient(X,E)
then
   if E.taille<=TAILLE_MAX
   then
    raise ensemblePleinEx;
   else
    E.taille:=E.taille+1;
    E.tab(E.taille):=X;
   end if;
end if;
end ajouter;

procedure enlever(X:in T;E:in out Ensemble) is
begin
for i in reverse 1..E.taille loop
   if E.tab(i)=X
   then
    -- on décale
    for j in i..E.taille-1 loop
     E.tab(j):=E.tab(j+1);
    end loop;
    -- on modifie la taille
    E.taille:=E.taille-1;
    exit;
   end if;
end loop;
end enlever;

end ensembles_generic;

Question 5

Reécrire le client qui utilisera cette fois le paquetage générique.

with ensembles;
with Ada.Integer_Text_io; use Ada.Integer_Text_io;
with Ada.Text_io; use Ada.Text_io;
procedure exo3_q5 is

package ensembleEntiers is new ensembles_generic(Integer);
use ensembleEntiers;
ens:Ensemble:=ensembleVide;

begin
for i in 1..6 loop
ajouter(i,ens);
end loop;

declare
ensBis:Ensemble:=ens;
begin
for i in reverse 1..cardinal(ensBis) loop
   put(i);put(" eme element : ");put(unElement(ensBis));
   new_line;
   enlever(unElement(ensBis),ensBis);
end loop;
end;

loop
exit when unElement(ens)=4;
exit when estVide(ens);
enlever(unElement(ens),ens);
end loop;

declare
ensBis:Ensemble:=ens;
begin
for i in reverse 1..cardinal(ensBis) loop
put(i);put(" eme element : ");put(unElement(ensBis));
new_line;
enlever(unElement(ensBis),ensBis);
end loop;
end;

end exo3_q5;