ED n°10 --- Enonçé

ED n°10 --- Algoritmique et Programmation

Objectifs

Généricité

`Le lien sur les corrigés se trouve en bas de page`

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;B:=tmp;
    end if;
end ordre;

Question 1

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

Question 2

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

Question 3

On souhaite trier un tableau de Cartes. Chaque Carte est caractérisée par un numéro (Positif), un nom (chaine de 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.

Ecrire une procédure de tri en ordre croissant d'un tableau de Cartes selon l'algorithme :

-- soit à trier le tableau t(a..b)
-- soit n un 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;

Question 4

Ecrire un programme qui teste cette procédure de tri sur un tableau particulier.

Solution

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,

Question 3

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

Question 4

Instancier cette fonction pour rechercher un caractère dans un tableau indicé par des entiers et écrire un programme client pour tester cette fonction.

Solution (voir lien ci-dessous)

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.

Question 2

Ecrire un client qui utilise le paquetage lesEnsembles pour créer l'Ensemble ={1,2,3,4,5,6} puis l'affiche.

Question 3

Ecrire le corps du paquetage.

Question 4

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

Question 5

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