Algorithmique et Programmation (1/3)

Objectifs :
Approfondir l'algorithmique aborde au premier semestre : nouveaux types de
donnes (numrations, types composs), algorithmes de recherche, algorithmes
de tris, rcursivit
Aborder de nouveaux aspects de l'algorithmique : complexit des algorithmes
Rfrences :
Algorithmes en Java, R. Sedgewick, Pearson Education
Programmation Cours et Exercices, G. Chaty & J. Vicard, Ellipses
Algorithmes et structures de donnes avec ADA, C++ et Java, A. Guerid, P.
Breguet & H. Rothlisberger, PPUR

Page du module : www.u-picardie.fr/~furst/algo_prog.php

Page du module de S1 : http://home.mis.u-picardie.fr/~groult/Enseignement/IntroInfo/
Licence Informatique - Semestre 2 - Algorithmique et Programmation

Algorithmique et Programmation (2/3)

Informatique : sciences et techniques du traitement automatis de l'information,
c'est dire des donnes (information structure).

On doit dfinir quelle information traiter : reprsentation et encodage des

donnes
On doit dfinir comment traiter l'information : algorithme

On doit faire excuter cet algorithme par une machine : programmation

Computer Science is no more about computers than astronomy is about

telescopes. Edsger Dijkstra (prix Turing 1972)

Licence Informatique - Semestre 2 - Algorithmique et Programmation

Algorithmique et Programmation (3/3)

sur le papier

TYPES ABSTRAITS
DE DONNEES
EN ENTREE
implment par

ALGORITHME

implment par

TYPES ABSTRAITS
DE DONNEES
EN SORTIE
implment par
dans des fichiers

TYPES CONCRETS
DE DONNEES
EN ENTREE
implment par

PROGRAMME

implment par

TRAITEMENT
DONNEES

(excution d'un
programme)

Licence Informatique - Semestre 2 - Algorithmique et Programmation

TYPES CONCRETS
DE DONNEES
EN SORTIE
implment par
dans le processeur
et la mmoire

RESULTAT
3

Variable
Dans un programme, les donnes sont manipules via des variables :
- une variable est une case mmoire
- une variable est dsigne par un nom (identifiant)
- une variable a un type de donne (implicite dans certains langages)
- une variable contient une valeur du type et cette valeur peut varier

Cycle de vie d'une variable :

- dclaration de la variable (nom et type)
- affectations de valeurs la variable
- suppression de la variable (souvent automatique)
Licence Informatique - Semestre 2 - Algorithmique et Programmation

Instructions
Dclaration de variable :

entier i;

Affectation de valeur une variable :

i <- 23;

Expressions numriques et logiques :

((i+2) * (j-t/23)) mod 4

(a ou (b et non

Lecture au clavier / Ecriture l 'cran :

Licence Informatique - Semestre 2 - Algorithmique et Programmation

c)) xor d

crire "donnez votre nom";

chaine c;
lire c;

Structures de contrle
Instructions conditionnelles :
si (temprature > 12) alors
crire "je vais me baigner";
finsi

Boucles :

si (a >= 16) alors

crire "mention bien";
sinon
crire "peut mieux faire";
finsi

chaine c <- "";

tantque (c "q") faire
crire "taper une chaine (q pour quitter)";
lire c;
fintantque

pour (i allant de 1 30 pas 1) faire

crire "ceci est le " + i + "me tour de boucle";
finpour
Licence Informatique - Semestre 2 - Algorithmique et Programmation

Algorithme
Un algorithme est une suite d'instructions squentielles, ventuellement
structures par des conditionnelles et des boucles.
algorithme TestPrimalit // nom de l'algorithme (optionnel)
// dclarations des variables
entier x,d;
boolen b;
dbut // dbut des instructions
crire "donnez un entier positif";
lire x;
d <- 2;
b <- false;
tantque (non b et d*d <= x) faire
si ((x mod d) == 0) alors
crire x+" n'est pas premier car il est divisible par "+d;
b <- vrai;
finsi
d <- d+1;
fintantque
si (non b) a=alors
crire x+" est premier";
finsi
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

Comment crire un algorithme (1/3)

Problme : crire un algorithme qui calcule le PGCD de deux nombres
1- Bien comprendre le problme et, si le principe de l'algorithme n'est pas
donn, trouver un principe de rsolution
Mthode d'Euclide (~300 av. JC) : soient deux nombres entiers positifs A et B
tels que A >= B. Si le reste R de la division de A par B est 0, le PGCD de A et B
est B. Sinon, le PGCD de A et B est le PGCD de B et de R.
2- Si on ne comprend pas bien le principe, l'utiliser sur un exemple
Soit calculer le PGCD de 123 et 27.
123 27
15 4

27

15

12 1

15

12

3 1

12

0 4

Le PGCD de 123 et 27 est donc 3.

Licence Informatique - Semestre 2 - Algorithmique et Programmation

Comment crire un algorithme (2/3)

4- Si besoin, raliser un organigramme pour mieux comprendre
entier A,B,R ;
crire ''donner un entier positif'' ;
lire A ;
crire ''donner un entier positif plus petit que le prcdent'' ;
lire B ;

R A mod B ;

FAUX

R=0

AB;
BR;
Licence Informatique - Semestre 2 - Algorithmique et Programmation

VRAI

crire ''le PGCD est '' + B ;

Comment crire un algorithme (3/3)

5- Ecrire l'algorithme
entier A,B,R;
dbut
crire "donner un entier positif";
lire A;
crire "donner un entier positif plus petit que le prcdent";
lire B;
R <- A mod B;
tantque (R 0) faire
A <- B;
B <- R;
R <- A mod B;
fintantque
crire "le PGCD de A et B est " + B;
fin

6- Il peut tre utile, voire ncessaire, de prouver l'algorithme

- l'algorithme va t'il toujours s'arrter ?
- quand l'algorithme s'arrtera, donnera t-il le bon rsultat ?
7- Il peut tre utile d'valuer l'efficacit de l'algorithme
- n'existe t-il pas un algorithme plus rapide pour calculer le PGCD ?
Licence Informatique - Semestre 2 - Algorithmique et Programmation

10

Fonction
Une fonction est un bloc d'instructions qui peut tre appel dans un autre bloc.
- la fonction a un nom (pour pouvoir tre appel)
- la fonction a des paramtres, contenant des valeurs ou des rfrences sur
des variables
- une fonction peut renvoyer une valeur au code qui l'a appele. Le type de
donne de cette valeur est le type de retour de la fonction. Une fonction peut
ne rien renvoyer (on parle alors parfois de procdure).
paramtres

type de retour

entier A
pgcd

entier

entier B

Licence Informatique - Semestre 2 - Algorithmique et Programmation

11

Dclaration de fonction
La dclaration d'une fonction comporte une signature qui indique comment
utiliser la fonction en prcisant son nom et ses entres/sorties, et un corps qui
est le code de la fonction.
signature

corps

fonction avec retour entier pgcd(entier A, entier B)

entier R;
dbut
R <- A mod B;
tantque (R 0) faire
A <- B;
B <- R;
R <- A mod B;
fintantque
retourne B;
fin

Une fonction peut ne pas avoir de retour (et donc de type de retour).
fonction sans retour ecritBonjour()
dbut
crire "Bonjour";
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

12

Appel de fonction
On appelle une fonction par son nom, en lui fournissant les valeurs
correspondant ses paramtres (s'il y en a).
Si la fonction renvoie une valeur, on peut la rcuprer dans une variable ou
l'utiliser directement.
caractre c;
entier A, B;
dbut
c ='O';
tantque (c 'N') faire
crire "voulez vous continuer (O/N)";
lire c;
si (c 'N') alors
crire "donner un entier positif";
lire A;
crire "donner un entier positif plus petit que le prcdent";
lire B;
crire "le PGCD de A et B est " + pgcd(A,B);
finsi
fintantque
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

13

Paramtres et entres/sorties
Attention : les paramtres d'une fonction servent lui transmettre des valeurs.
Il est donc redondant de lire au clavier des valeurs transmises par paramtres.
Il est galement absurde de redfinir les paramtres dans le corps de la
fonction.
fonction avec retour entier pgcd(entier A, entier B)
entier A,B,R;
dbut
crire "donner A";
lire A;
crire "donner B";
lire B;
R <- A mod B;
tantque (R 0) faire
A <- B;
B <- R;
R <- A mod B;
fintantque
retourne B;
fin

Licence Informatique - Semestre 2 - Algorithmique et Programmation

14

Appel de fonction dans une fonction

fonction avec retour entier plusGrand2(entier a, entier b)
dbut
si (a<b) alors
retourne b;
sinon
retourne a;
finsi;
fin

fonction avec retour entier plusGrand3(entier a, entier b, entier c)

dbut
retourne plusGrand2(plusGrand2(a,b),c);
fin

algorithme MonAlgo
entier toto, titi, tutu;
dbut
lire toto;
lire titi;
lire tutu;
crire "le plus grand est " + plusGrand3(toto,titi,tutu);
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

15

Passage de paramtres (1/3)

Un paramtre peut tre transmis une fonction par valeur : la valeur est
clone et la fonction travaille sur une variable interne.
fonction avec retour entier multiplie2(entier x)
dbut
x <- 2*x;
retourne x;
fin

entier x,y;
x <- 12;
y <- multiplie2(x);
crire "x vaut " + x;

x
y

12
?
24
?

12
24

En algorithmique, on supposera que les paramtres de type primitif (entier,

rel, boolen, caractre) sont toujours passs par valeur. C'est le cas en Java.
Licence Informatique - Semestre 2 - Algorithmique et Programmation

16

Passage de paramtres (2/3)

Un paramtre peut tre transmis une fonction par rfrence : la fonction
travaille sur la case mmoire correspondant la variable qui stocke la valeur.
fonction avec retour entier multiplie2(entier x)
dbut
x <- 2*x;
retourne x;
fin

entier x,y;
x <- 12;
y <- multiplie2(x);
crire "x vaut " + x;

x
x
y

12
24
?
24
?

En algorithmique, on supposera que les paramtres de type composs

(tableaux, enregistrements, etc) sont toujours passs par rfrence. C'est le
cas en Java.
Licence Informatique - Semestre 2 - Algorithmique et Programmation

17

Passage de paramtres (3/3)

Les langages de programmation permettent souvent de choisir la faon dont
les paramtres sont passs aux fonctions.

Exemple de passage d'un entier par rfrence en langage C :

void multiplie2(int* i){
*i = (*i)*2;
}

int i;
i = 3;
multiplie2(&i);

Exemple de passage d'un entier par rfrence en langage ADA :

procedure multiplie2(i : in out Integer) is
begin
i := i*2;
end multiplie2

Licence Informatique - Semestre 2 - Algorithmique et Programmation

i : Integer;
i = 3;
multiplie2(i);

18

Types de donnes
Un type de donnes est dfini par un ensemble de valeurs et un ensemble
d'oprations.

On distingue les types de donnes abtraits (au niveau algorithmique) et les types de
donnes concrets (au niveau des langages de programmation).

Exemples :
- le type abstrait entier a pour valeurs tous les entiers positifs ou ngatifs, et
pour oprations +, -, *, / et mod (ainsi que l'opration externe =).
- le type concret int en Java a pour valeurs les entiers compris entre 231-1 et
-231 et pour oprations +, -, *, / et mod (ainsi que l'opration externe ==).

Les types de donnes servent faciliter la programmation et surtout tester la

compilation la correction des programmes.
Licence Informatique - Semestre 2 - Algorithmique et Programmation

19

Cration de types de donnes

Certains langages permettent de crer des sous types de types existants en
restreignant l'ensemble des valeurs et/ou les oprations.
Exemple en ADA :

subtype Age is INTEGER range 0..100;

subtype Lettre is Character range 'a'..'Z';

La plupart des langages permettent de crer de nouveaux types.

- en crant des ensembles de valeurs dfinies par le programmeur :
numrations, ensembles, unions.

- en assemblant des variables au sein de types composs : tableaux,

enregistrement, listes, arbres, graphes, etc.

Licence Informatique - Semestre 2 - Algorithmique et Programmation

20

Types numrs (1/4)

Un type numr (ou numration) est un type dont les valeurs sont donnes in
extenso par le programmeur.
Un type numr permet de dfinir des valeurs n'existant pas dans les types
fournis par le langage.
Un type numr s'utilise comme n'importe quel type pour typer des variables
ou des paramtres.
Exemple : type numr en Java (ou C ou C++ ou C#)
enum ArcEnCiel {rouge, orange, jaune, vert, bleu, indigo, magenta, violet};
ArcEnciel aec = ArcEnCiel.jaune;
enum Primaire {rouge, vert, bleu};
Primaire p = Primaire.rouge;

Remarque : en Java, une valeur d'un type numr doit tre prfixe par le nom
du type, pour viter toute ambiguit. En algorithmique, ce n'est pas ncessaire.
Licence Informatique - Semestre 2 - Algorithmique et Programmation

21

Types numrs (2/4)

Certains langages (dont Java et C) permettent de donner aux types numrs des
valeurs d'autres types stockes dans des variables.
Exemple en Java :

int vrai = 1;
int faux = 0;
String possible = "possible";
enum ValeurDeVerite {vrai, faux, possible};

Tous les langages permettant les types numrs offrent des oprations d'galit
et d'ingalit sur ces types.

Exemple en Java :

ValeurDeVerite vv1, vv2;

...
if ((vv1 == vv2) && (vv1 != ValeurDeVerite.faux))
System.out.println("Tout est possible");

Licence Informatique - Semestre 2 - Algorithmique et Programmation

22

Types numrs (3/4)

Il existe souvent une relation d'ordre sur les valeurs numres.
Exemple : en Java v.ordinal() renvoie le numro d'ordre de v dans le type.
enum ArcEnCiel {rouge, orange, jaune, vert, bleu, indigo, magenta, violet};
ArcEnciel aec1, aec2;
aec1 = ArcEnCiel.rouge; // aec1.ordinal() vaut 0
aec2 = ArcEnCiel.bleu; // aec2.ordinal() vaut 4
if (aec1.ordinal() > aec2.ordinal()) {...}

Il peut exister des oprations de parcours des valeurs d'un type numr.
Exemple en Java :
for (ArcEnCiel aec : ArcEnCiel.values()) {
System.out.println(aec.name());
}

Licence Informatique - Semestre 2 - Algorithmique et Programmation

23

Types numrs (4/4)

Le programmeur peut toujours ajouter des oprations sur un type numr qu'il a
cr, en crivant des fonctions.
fonction avec retour ValeurDeVerite et(ValeurDeVerite vv1, ValeurDeVerite vv2)
dbut
si (vv1 = ValeurDeVerite.vrai) alors
si (vv2 = ValeurDeVerite.vrai) alors retourne ValeurDeVerite.vrai;
sinon
si (vv2 = ValeurDeVerite.possible) alors
retourne ValeurDeVerite.possible;
sinon
retourne ValeurDeVerite.faux;
finsi
finsi
finsi
si (vv1 = ValeurDeVerite.faux) alors retourne ValeurDeVerite.faux;
finsi
si (vv1 = ValeurDeVerite.possible) alors
si ((vv2 = ValeurDeVerite.vrai) ou (vv1 = ValeurDeVerite.possible))
retourne ValeurDeVerite.possible;
sinon
retourne ValeurDeVerite.faux;
finsi
finsi
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

24

Types numrs en algorithmique

En algorithmique, pour les types numrs, on adoptera la syntaxe la plus courante
qui est celle du langage C (syntaxe reprise en C++ et en Java, entre autres).
Les types numrs seront dclars dans la partie dclaration, avec les
dclarations de variables.
algorithme MonAlgorithme
entier vrai, faux;
chaine possible;
enum ValeurDeVerite {vrai, faux, possible};
ValeurDeVerite vv1,vv2;
dbut
vrai <- 1;
faux <- 0;
possible <- "possible";
vv1 <- ValeurDeVerite.possible;
vv2 <- ValeurDeVerite.faux;
fin

Comme en Java, on considre que les valeurs des types numrs sont passs
aux fonctions par rfrence.
Licence Informatique - Semestre 2 - Algorithmique et Programmation

25

Types composs
Les donnes sont souvent complexes et les types primitifs (entier, boolen, ...) ne
suffisent pas les reprsenter de faon efficace.

Exemple : on veut reprsenter dans un programme les notes de 100 tudiants

inscrits dans 5 modules : il faut 500 variables.
rel noteModule1Etudiant1, noteModule1Etudiant2, noteModule1Etudiant3, ...
noteModule2Etudiant1, ...
...
... , noteModule5Etudiant100;

Un type de donnes compos (ou structur) est un type dont les valeurs sont
composes de plusieurs valeurs.
noteModule1Etudiant1

noteModule1Etudiant2

...

noteModule1Etudiant99

noteModule1Etudiant100

noteModule5Etudiant99

noteModule5Etudiant100

...
noteModule5Etudiant1

noteModule5Etudiant2

...

Licence Informatique - Semestre 2 - Algorithmique et Programmation

26

Tableaux
Un type tableau est un type compos dont chaque valeur est compose d'autres
valeurs (les cases du tableau), toutes du mme type, et indices par un type
discret ordonn.
Gnralement, les indices sont des entiers, allant de 0 la longueur du tableau-1.

Exemple : tableau de 100 rels.

notes[0]
notes[1]

notes
notes[99]

12.0
?
7.5
?

...
8.5
12

rel[100] notes;
notes[0] <- 12.0;
notes[1] <- 7.5;
...
notes[99] <- 8.5;

Remarque : un type tableau est un type, un tableau est une valeur du type

Exemple : - tableau de caractres est un type

- le tableau de caractres ['t','o','t','o'] est une valeur de type tableau de
caractres
Licence Informatique - Semestre 2 - Algorithmique et Programmation

27

Dclaration d'un tableau

Comme toute variable, une variable de type tableau possde un nom et un type
(celui de ses lments). Un tableau possde galement un nombre d'lments.
Exemple : dclaration de tableaux dans une syntaxe C ou C++
// dclaration d'un tableau de chaines de 12 cases
char*[12] monTableauDeChaines;
// dclaration d'un tableau d'entiers de 5 cases
int monTableauDEntiers[5];

En algorithmique, on utilisera la mme syntaxe (deux formes possibles) :

<type des lments>[<nombre d'lments>] <nom de la variable>;
<type des lments> <nom de la variable>[<nombre d'lments>];

Remarque : dclarer le tableau entraine la dclaration de toutes les variables

contenues dans le tableau mais pas leur initialisation!
Licence Informatique - Semestre 2 - Algorithmique et Programmation

28

Accs aux cases d'un tableau

On accde une case d'un tableau en prcisant son indice entre crochets.
chaine[3] monTableauDeChaines;
monTableauDeChaines[0] <- "toto";
monTableauDeChaines[1] <- "titi";
montableauDeChaines[2] <- "tutu";
crire monTableauDeChaines[1];
monTableauDeChaines[0] <- monTableauDeChaines[3];

Remarques :
- une tentative d'accs une case qui n'existe pas fera planter le programme!
- accder une case non initialise peut conduire des erreurs d'excution.

Licence Informatique - Semestre 2 - Algorithmique et Programmation

29

Initialisation d'un tableau (1/2)

Exemple : initialisation 1.0 des cases d'un tableau de 38 rels
rel[38] monTableauDeReels;
entier i;
dbut
pour (i allant de 0 37 pas 1) faire
monTableauDeReels[i] <- 1.0;
finpour
fin

Exemple : initialisation d'un tableau de 45 caractres 'a' pour les cases d'indice
pair et 'b' pour les cases d'indice impair.
caractre[45] t;
entier i;
dbut
pour (i allant de 0 44 pas 1) faire
si(i mod 2 = 0) alors
t[i] <- 'a';
sinon
t[i] <- 'b';
finsi
finpour
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

30

Initialisation d'un tableau (2/2)

Beaucoup de langages proposent une syntaxe pour initialiser les valeurs d'un
tableau par numration.
- initialisation et dclaration sont alors regroupes dans la mme instruction
- on ne prcise pas la taille du tableau dans la partie dclaration

Cette mthode n'est utile que pour de petits tableaux.

Exemples :

// dclaration et remplissage d'un tableau de rels

rel[] monTableauDeReels <- {3.2,4.0,3.14,2.78,10.6};
// dclaration et remplissage d'un tableau de chaines
chaine monTableauDeChaines[] <- {"toto","titi","tutu","tete"};

Licence Informatique - Semestre 2 - Algorithmique et Programmation

31

Longueur d'un tableau

L'oprateur longueur (length en Java) permet de connaitre la taille d'un tableau.
chaine[12] monTableauDeChaines;
boolen[monTableauDeChaines.longueur*2] tableauDeBooleens;
dbut
...
crire "le tableau a " + monTableauDeChaines.longueur + " lments";
fin

Remarques :
- la taille d'un tableau ne peut pas varier
- il faut savoir, avant de crer un tableau, de combien de cases on a besoin
- il ne faut pas dclarer plus de cases que ce dont on a besoin, pour viter
d'occuper de la place en mmoire pour rien
- si on ne sait vraiment pas de combien de cases on aura besoin, il existe
des structures linaires dynamiques (listes) dont la taille peut varier (cf. cours
de L2)

Licence Informatique - Semestre 2 - Algorithmique et Programmation

32

Dclaration de types tableau

Certains langages permettent la dclaration des types tableau (et non uniquement
la dclaration des tableaux).
// dclaration d'un type tableau de 5 entiers en ADA
type MonTypeTableau is array(0 .. 5) of Integer;
// utilisation du type tableau pour dclarer un tableau
MonTypeTableau monTableau;

// dclaration d'un type tableau de 5 entiers en Java

class MonTypeTableau{
int[] t = new int[5];
}
// utilisation du type tableau pour dclarer un tableau
MonTypeTableau monTableau = new MonTypeTableau();
MonTableau.t[0] <- 2;
...

En pratique, il est souvent sans intrt de crer des types tableaux.

Licence Informatique - Semestre 2 - Algorithmique et Programmation

33

Tableau paramtre
Rappel : les tableaux passs en paramtres de fonctions le sont par rfrence.
fonction sans retour multiplie2Tab(entier[] t)
entier i;
dbut
pour (i allant de 0 t.longueur-1 pas de 1) faire
t[i] <- t[i]*2;
finpour
fin

entier[] tab <- {1,2,3};

multiplie2Tab(tab);
crire tab[0];

Licence Informatique - Semestre 2 - Algorithmique et Programmation

tab
t
i

[1,2,3]
[2,4,6]
...

34

Tableau dynamique (1/2)

Problmes poss lorsqu'on fixe le nombre d'lments d'un tableau la
dclaration :
- on est oblig de savoir l'avance combien il y aura de cases dans les
tableaux retourns par les fonctions
// fonction retournant le tableau des noms des tudiants d'un groupe
chaine[12] fonction nomsEtudiants(int numeroGroupe) ...
chaine[35] etudiantsDuGroupe2 = nomsEtudiants(2);

- on est oblig de connaitre l'avance le nombre de cases d'un tableau

pass en paramtre d'une fonction
// fonction retournant la moyenne des rels du tableau paramtre
rel fonction calculMoyenne(rel[56] notes) ...
rel[35] notesGroupe3 = ...
rel m <- calculMoyenne(notesGroupe3);

Licence Informatique - Semestre 2 - Algorithmique et Programmation

35

Tableau dynamique (2/2)

Un tableau est dit statique si sa taille est fixe la dclaration et dynamique si sa
taille est fixe plus tard.
chaine[27] monTableauStatique
chaine[] monTableauDynamique
...
redim monTableauDynamique[27]; // redimensionnement

Les tableaux dynamiques permettent aux fonctions de travailler sur des tableaux
de taille arbitraire.

chaine[] fonction nomsEtudiants(int numeroGroupe) ...

chaine[] etudiantsDuGroupe2 = nomsEtudiants(2);
reel fonction calculMoyenne(reel[] notes) ...

Licence Informatique - Semestre 2 - Algorithmique et Programmation

36

Dclaration de tableau en Java

En Java, les tableaux sont toujours dynamiques :
// dclaration d'un tableau de chaines en Java
String[] monTableauDeChaines;
// redimemsionnement du tableau
monTableauDeChaines = new String[12];
// dclaration et redimemsionnement sur la mme ligne
String[] monAutreTableau = new String[12];
// dclaration et redimemsionnement d'un tableau d'entiers
int monTableauDEntiers[] = new int[23];
double tab[12]; // erreur la compilation

Remarque : dans la partie dclaration, les crochets peuvent tre placs avant ou
aprs le nom du tableau, mais attention en cas de dclaration multiple.
int[] t1,t2; // t1 et t2 sont des tableaux d'entiers
int t1,t2[]; // t1 est un entier et t2 un tableau d'entiers
int t1[],t2; // t1 est un tableau d'entiers et t2 un entier

Licence Informatique - Semestre 2 - Algorithmique et Programmation

37

Tableaux dynamiques en algorithmique

Rappel : dclaration d'un tableau statique.
<type des lments>[<nombre d'lments>] <nom de la variable>;
<type des lments> <nom de la variable>[<nombre d'lments>];

Dclaration et redimensionnement d'un tableau dynamique : deux syntaxes

possibles pour la dclaration, une seule pour le redimensionnement.
<type des lments>[] <nom de la variable>;
<type des lments> <nom de la variable>[];

redim <nom de la variable>[<nombre d'lments>];

Licence Informatique - Semestre 2 - Algorithmique et Programmation

38

Tableau vide (1/2)

Pour des raisons pratiques, il peut tre ncessaire de traiter des tableaux vides.
Exemple : fonction qui renvoie le tableau des entiers pairs contenus dans un
tableau d'entiers pass en paramtre.
fonction avec retour entier[] pairs(entier[] t)
entier[] resultat;
entier i,nb;
dbut
nb <- 0;
pour (i allant de 0 t.longueur-1 pas 1) faire
si (t[i] mod 2 = 0) alors
nb <- nb+1;
finsi
finpour
redim resultat[nb];
nb <- 0;
pour (i allant de 0 t.longueur-1 pas 1) faire
si (t[i] mod 2 = 0) alors
resultat[nb] <- t[i];
nb <- nb+1;
finsi
finpour
retourne resultat;
fin
Licence Informatique - Semestre 2 - Algorithmique et Programmation

39

Tableau vide (2/2)

En algorithmique, on s'autorise crer des tableaux vides de toutes les manires
imaginables. On peut tester si un tableau est vide en testant sa longueur.
entier[] titi; // titi est vide
redim titi[0]; // titi est toujours vide
entier[0] tutu; // tutu est vide
entier[] tata <- {}; // tata est vide
entier[] toto <- {3,5,75,231};
entier[] t <- pairs(toto);
si(t.longueur = 0) alors
...

En Java, un tableau qui n'a pas t dimensionn sera gal null.

int[] titi; // le compilateur indiquera une erreur d'initialisation
int[] tete = new int[0]; // tete est vide
int[0] tutu; // interdit en Java, les tableaux sont forcment dynamiques
int[] tata <- {}; // tata est vide
int[] toto <- {3,5,75,231};
int[] t <- pairs(toto);
if(t != null && t.length != 0){
...
Licence Informatique - Semestre 2 - Algorithmique et Programmation

40

Tableaux associatifs
Il est possible d'indicer les tableaux par n'importe quel type numr ordonn, pas
seulement pas des entiers de 0 la longueur du tableau 1.

Exemples : tableau d'entiers indic par les valeurs du type ArcEnCiel en Java

34

123

...

67

rouge

orange

...

violet

enum ArcEnCiel {rouge, orange, jaune, vert, bleu, indigo, magenta, violet};
HashTable<ArcEnCiel,Integer> t = new HashTable<ArcEnCiel,Integer>();
t.put(ArcEnCiel.rouge,34);
t.put(ArcEnCiel.orange,123);
...
t.put(ArcEnciel.violet,67);
...
t.get(ArcEnCiel.orange); // renvoie 123
Licence Informatique - Semestre 2 - Algorithmique et Programmation

41

Enregistrement (1/2)
Exemple : on veut reprsenter dans un programme les donnes dcrivant 50
personnes avec pour chacune un nom, un prnom, un ge et une taille.
chane nom1, prnom1;
entier age1;
rel taille1;
...
chane nom50, prnom50;
entier ge50;
rel taille50;
...
nom1 <- "Duchmol";
prenom1 <- "Robert";
age1 <- 24;
taille1 <- 1.80;

Un enregistrement est un type compos qui permet de regrouper des valeurs de

types diffrents.

Licence Informatique - Semestre 2 - Algorithmique et Programmation

42

Enregistrement (2/2)
Un enregistrement a un nom et un certains nombre de champs, qui sont des
variables types.

L'accs un champ se fait en

prfixant
l'identifiant
du
champ par le nom de la
variable
qui
contient
l'enregistrement.

algorithme monAlgorithme
// dclaration d'un enregistrement
enregistrement Personne
chaine nom;
chaine prenom;
entier age;
rel taille;
finenregistrement
...
Personne p1, p2;
dbut
// Initialisation d'un enregistrement
p1.nom <- "Duchmol";
p1.prenom <- "Robert";
p1.age <- 24;
p1.taille <- 1.80;
...
fin

Remarque : un enregistrement est un type, mais les valeurs du type sont aussi
appeles enregistrement (comme pour les types primitifs).
Licence Informatique - Semestre 2 - Algorithmique et Programmation

43

Enregistrement en Java
public class MonProgramme{
static class Personne{
String nom;
String prenom;
int age;
float taille;
}
public static void main(String arg[]){
Personne p1 = new Personne();
Personne p2 = new Personne();
p1.nom = "Duchmol";
p1.prenom = "Robert";
p1.age = 24;
p1.taille = 1.80;
...
}
}

Rappel : les enregistrements passs en paramtre de fonction le sont par

rfrence (en Java et en algorithmique).
Licence Informatique - Semestre 2 - Algorithmique et Programmation

44