Exercice algorithmique tri, boucle par récurrence et fonctions
Objectifs
- Construction de boucle par récurrence
- Tris
- Fonctions et procédures
Exercice
On souhaite inverser un tableau de valeurs boursières. Une valeur boursière est caractérisée par sa dénomination (un sigle de 5 caractères) et sa cotation. Le tableau est préalablement trié selon l'ordre croissant des cotations, on veut le ranger selon l'ordre décroissant.
Question 1
- Ecrire l'algorithme de l'inversion
-- Invariant :
-- T(a..i-1) et T(j+1..b) sont déjà inversés
-- Condition d'Arrêt de l'Itération :
-- si longueur(T) est impaire alors i=j
-- si longueur(T) est paire alors i=j+1
-- donc la CAI est : i>=j
-- Corps de boucle :
-- permuter(T(i) et T(j); incrémenter i; décrémenter j;
-- Initialisation :
-- le tableau T(a..b) est initialement non inversé, donc i=a et j=b
-- Algorithme
début
i
j
-- T(a..i-1) et T(j+1..b) sont déjà inversés
tant que non(i>j) faire
permuter(T(i) et T(j);
incrémenter i;
décrémenter j;
fin tant que;
fin.
Question 2
- Déclarer et définir les types permettant de représenter des tableaux de valeurs boursières.
subtype Cotation is Float range 0.0..Float'last;
type Sigle is String(1..5);
type ValeurBoursiere is
record
cote:Cotation;
nom:Sigle;
end record;
type Bourse is array(Natural range ) of ValeurBoursiere;
Question 3
- Déclarer la procédure d'inversion
procedure inverser(T: in out Bourse);
Question 4
- Définir la procédure d'inversion
procedure inverser(T: in out Bourse) is
i:Integer:=T'first;
j:Integer:=T'last;
begin
loop
exit when i>=j;
permuter(T(i),T(j));
i:=i+1;
j:=j-1;
end loop;
end inverser;
Question 5
- Ecrire un programme de test.
with Ada.Text_io;use Ada.Text_io;
with Ada.Float_Text_io;use Ada.Float_Text_io;
procedure inversion is
subtype Cotation is Float range 0.0..Float'last;
type Sigle is String(1..5);
type ValeurBoursiere is
record
nom:Sigle;
cote:Cotation;
end record;
type Bourse is array(Natural range ) of ValeurBoursiere;
procedure permuter(x,y:in out ValeurBoursiere) is
z:ValeurBoursiere:=x;
begin
x:=y;
y:=z;
end permuter;
procedure inverser(T: in out Bourse) is
i:Integer:=T'first;
j:Integer:=T'last;
begin
loop
exit when i>=j;
permuter(T(i),T(j));
i:=i+1;
j:=j-1;
end loop;
end inverser;
procedure put(T:in Bourse) is
begin
put("(");new_line;
for i in T'range loop
put("(");
put(T(i).cote);
put(T(i).nom);
put(")");
new_line;
end loop;
put(")");
end put;
tab:Bourse(1..5):=(("BULL#",78.91),("accor",275.17),("valeo",406.69),("rexel",511.65),("Dexia",939.33));
begin
put(tab);
new_line;
inverser(tab);
put(tab);
new_line;
end inversion;