ED n°10 --- Algoritmique et Programmation


Objectifs

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

Question 2 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.


-- 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

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

Question 2 Question 3 Question 4 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

Question 2 Question 3 Question 4 Question 5


Solution des exercices