Institut Supérieur des Sciences Appliquées et Technologie de

Sousse

Cours

Algorithmique & Structures des Données 1

1ère année Préparatoire

Année universitaire : 2014/2015

 Algorithmique & Structures de Données 1 Ch 1 : Introduction à l’algorithmique

CH I : INTRODUCTION A L’ALGORITHMIQUE
L’ALG

1. Démarche pourr la résolution d’un problème

Pour résoudre un problème, en informatique,
i plusieurs étapes sont nécessaires :
a) Environnement : la connaissance précise de l’environnement (machine utilisée,
processeur,...)
b) Problème : la définition précise du problème.
c) Analyse : l’analyse du problème et sa décomposition en sous-problèmes
sous problèmes simples et
distinctes.
d) Algorithme : laa formulation de la solution sous une forme textuelle. Description de des
opérations à mettre en œuvre expliquant comment obtenir un résultat à partir de données. Il
s'agit d'une description compréhensible par un être humain de la suite des opérations à
effectuer pour résoudre le problème.
roblème.
e) Programme : laa traduction de la solution, de la forme textuelle à un langage informatique,
compréhensible par la machine utilisée.

2. Définition d’un Algorithme

Un algorithme peut être définit comme suit :
« Etant donné un environnement
nvironnement bien défini et un problème à résoudre dans cet
environnement, un algorithme est l’énoncé d’une séquence finie d’actions élémentaires à
exécuter afin d’obtenir la résolution du problème posé. »
A noter que le mot algorithme vient du nom du mathématicien
mathématicien arabe El Khowarismi,
originaire de la ville de Khowarism.
La formulation d’une solution d’un problème sous forme d’un algorithme, est une phase
très importante, et les résultats souhaités en dépendent principalement. En effet, toute erreur
de logique qui y serait commise,ise, nécessitera, lorsqu’elle est découverte, de recommencer en
grande partie les étapes suivantes.

3. Exemple
On va donner l’algorithme permettant de trouver le PGCD (Plus
(Plus Grand Commun
Diviseur)) de deux entiers naturels a et b.

Début
données de a et b
si (a,b) premiers entre eux alors pgcd(a,b) = 1
• sinon
- décomposer a en facteurs premiers
- décomposer b en facteurs premiers
• pgcd(a,b) = produit des facteurs premiers communs à a et b, avec les
exposants les moins forts.
Fin
Algorithmique & Structures de Données 1 Ch 1 : Introduction à l’algorithmique

Un organigramme est une méthode, de moins en moins utilisée pour représenter

schématiquement un algorithme. L’organigramme de l’exemple précédent peut être représenté
de la façon suivante :

Début

lire(a,b)

a et b
oui non
premiers
entre
eux ?

pgcd(a,b)=1 décomposer a

décomposer b

Fin

calculer P =
produit des facteurs
premiers communs à a et
b avec les exposants les
moins forts.

pgcd(a,b) = P

Fin
4. La codification
La codification est l’objet de l’étape e) décrite au paragraphe 1). Une fois l’algorithme,
réalisant le traitement, est déterminé, la codification consiste à adapter cet algorithme à la
machine utilisée, c’est à dire la traduction dans un langage donné, compréhensible par cette
dernière.

ISSAT 2
Algorithmique & Structures de Données 1 Ch 1 : Introduction à l’algorithmique

En effet, la majorité des ordinateurs ne sont pas en mesure d’exécuter directement les
algorithmes sous leur forme littérale, d’ou la nécessité de les codifier dans un langage
approprié, appelé langage de programmation.
5. La compilation
C’est la transformation en langage machine d'un programme écrit en langage évolué :
JAVA, C, COBOL, BASIC, FORTRAN, ....
Il existe deux types de langages :
Les langages de programmation de haut niveau, ou langages évolués. Ce sont des
langages dont l’utilisation ne nécessite pas la connaissance des caractéristiques
physiques de l’ordinateur sur lequel le programme va être exécuté.
Citons chronologiquement les plus connus :
• FORTRAN crée par IBM en 1956
• COBOL (1960)
• BASIC (1965)
• PASCAL (1969)
• Le langage C
• ADA,
• Java, etc...
Les langages d’assemblage ou assembleur. Ce sont des langages pour lesquels
chaque instruction correspond à un une instruction-machine. Ces langages sont
spécifiques d’un ordinateur donné, et leur utilisation nécessite une bonne
connaissance des caractéristiques de la machine.
6. Conclusion
Nous résumons la démarche nécessaire pour la résolution d’un problème donné par le
schéma suivant :

Problème à ANALYSE CODIFICATION Programme en

Algorithme un langage
résoudre donné

COMPILATION

INCORRECTS

EXECUTION Programme en
Résultats langage machine

CORRECTS

FIN

ISSAT 3
 Algorithmique & Structures de Données 1 Ch 1 : Introduction à l’algorithmique

Exemple :
Ecrire une méthode claire permettant de résoudre l’équation du second degré dans IR
2
(ax + bx +c = 0). Etudiez tous les cas possibles (a=0, etc.) et représenter la solution sous
forme d’un organigramme.

Lecture de (a,b,c)

oui oui oui non

cc==00 bb == 0 a=0

non non

impossible x = -c/b
d = b*b – 4*a*c
infinité
de
solutions
fin fin
x1 = (-b - sqrt(d))/(2*a) oui
x2 = (-b +sqrt(d))/(2*a) d >= 0

fin
non

fin pas de solutions

réelles

fin

ISSAT 4
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

CH II : LES DONNEES ET STRUCTURE D’UN ALGORITHME

1. Introduction
Un ordinateur manipule des objets. Chaque objet a besoin de trois qualificatifs pour sa
définition.

Type Objet Identificateur

nom (ni opérant ni espace)
Entier Réel
Booléen Caractère
Chaîne
Valeur (sinon constante)
- Identificateur (le nom de l’objet)
- Type (ensemble possible de valeurs de l’objet)
- Valeur (constante ou variable)
Remarque : Variables constantes
Une constante est un objet dont la valeur ne varie pas tout au long du programme. Un objet
dont la valeur change est nommé variable.
Un identificateur est une lettre ou groupe de lettres et des chiffres commençant par une lettre
ni espace ni opérant.
2. Type
Un type de donnée définit un ensemble dans lequel les variables prennent leur valeur.
Chacune des variables d’un algorithme doit être associée à un type de donnée et un seul.
A chaque type de donnée est associé un ensemble d’opérateurs qui sont possibles sur les
variables et les constantes de ce type. Il y a cinq types élémentaires standard :
- Entier
- Réel
- Booléen
- Caractère
- Chaîne

2.1. Le type entier

Une variable de type entier prend ses valeurs l’ensemble des nombres entiers. Les opérateurs
qui, appliqués à des entiers, donnent un résultat entier sont :
• Addition (+)
• Soustraction (-)
• Multiplication (*)
• Division entière (DIV)
• Reste de la division entière (MOD).
En plus des opérateurs ci-dessus, on peut utiliser les fonctions telles que :
ABS(-10) = 10 SQR(5) = 25 SQRT(36)= 6

2.2. Le type réel

Une variable de type réel fait partie des nombres réels.

ISSAT 5
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

a. Les opérateurs réels

Le résultat des opérateurs suivants est réel, si au moins l’un des opérandes est réel (l’autre
pouvant être entier) :
• Addition (x+y)
• Soustraction (x-y)
• Multiplication (x*y)
• Division (x/y)

b. Les fonctions sur les réels

Les fonctions suivantes donnent un résultat réel, pour un argument entier ou réel :
sin(x), cos(x), exp(x), ln(x), sqrt(x), arctan(x), etc.
L’argument des fonctions suivantes est réel, et le résultat est entier :
trunc(x) : partie entière de x, trunc(1.25)=1, trunc(0.89)=0
round(x) : entier le plus proche de x, round(20.49)=20, round(20.5)=21

2.3. Le type booléen

Une variable booléenne ou de type logique doit prendre pour valeurs la constante TRUE (pour
VRAI) ou la constante FALSE (pour FAUX). Ces valeurs pouvant être obtenues par
l’évaluation d’une expression logique. Les booléens se représentent sur un seul bit, en général
avec le codage « 0 » pour false et « 1 » pour true.
a. Les opérateurs booléens
ET / OU Logique
Les opérateurs booléens (ou logiques) sont : a b a ET b a OU b
• NOT (Non : Négation)
0 0 0 0
• AND (ET logique)
0 1 0 1
• OR (OU logique)
1 0 0 1
Négation 1 1 1 1
a Non a
0 1
1 0
b. Propriétés des opérateurs logiques
Quelques propriétés des opérateurs logiques sont importantes, notons les plus utilisées :
• a ET (b OU c) = (a ET b) OU (a ET c)
• a OU (b ET c) = (a OU b) ET (a OU c)
• NON(a ET b) = NON(a) OU NON(b)
• NON(a OU b) = NON(a) ET NON(b)

c. Les opérateurs relationnels

Une expression logique contient un ou plusieurs opérateurs relationnels et/ou un ou plusieurs
opérateurs logiques. Les opérateurs relationnels sont :
• = : égal à
• <> : différent de

ISSAT 6
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

• < : inférieur à
• > : supérieur à
• <= : inférieur ou égal à
• >= : supérieur ou égal à
La priorité des opérateurs logiques est : NOT – AND – OR, cet ordre peut être modifié par
l’utilisation de parenthèses.

2.4. Le type caractère

Le type caractère est l’ensemble fini et ordonné de tous les signes qui peuvent être représentés par la
machine : lettres minuscules, lettres majuscules, chiffres et signes spéciaux. En règle générale, cet
ensemble correspond à celui des caractères qui sont représentés sur le clavier d’un ordinateur.
Un caractère est représenté sur 8 bits, ce qui donne 256 combinaisons possibles. Le code, couramment
utilisé, est le code ASCII (American Standard Code for Information Interchange).
Les opérateurs relationnels définis précédemment s’appliquent également sur les caractères avec les
conventions :
‘A’ < ‘B’ < … < ‘Z’
‘0’ < ‘1’ < ... < ‘9’
Les fonctions suivantes sont utiles pour les opérations sur les caractères :
• SUCC : pour successeur
• PRED : pour prédécesseur
• ORD : pour rang
• CHR : la fonction CHR n’admet pour paramètre qu’un nombre entier. Elle fournit
comme résultat le caractère dont le numéro d’ordre est spécifié comme paramètre.
• Les fonctions CHR et ORD sont des fonctions inverses.
Exemples :
ORD(‘A’) = 65 CHR(65) = ‘A’ SUCC(‘X’) = ‘Y’ PRED(‘G’) = MAJUS(‘c’)=’C’
‘F’

2.5. Le type chaîne de caractères

Le type chaîne de caractères est l’ensemble des chaînes de caractères que l’on peut former.
Une chaîne vide est une chaîne qui ne contient aucun caractère. Une chaîne peut contenir au
maximum 256 caractères.
2.5.1. Déclaration d’une chaîne
variables
c : caractère
ch : chaîne
chn : chaîne[20]
La variable ch peut contenir jusqu’à 255 caractères, alors que chn peut contenir au maximum 20.
2.5.2. Opérations sur les chaînes de caractères
a- La concaténation
C’est l’assemblage de deux chaînes de caractères en utilisant l’opérateur « + ».
Exemple
chn1 ← "Turbo"
chn2 ← "Pascal"
chn3 ← chn1 + " " + chn2
chn3 contiendra "Turbo Pascal"

ISSAT 7
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

b- Les opérateurs relationnels

Il est possible d’effectuer une comparaison entre deux chaînes de caractères, le résultat est de type
booléen. La comparaison se fait caractère par caractères de la gauche vers la droite selon le code
ASCII.
Exemple
o L’expression ("a" > "A") est vraie puisque le code ASCII de "a" (97) est supérieur à celui de
"A"(65).
o L’expression ( "programme" < "programmation" ) est fausse puisque "e" > "a".
o L’expression ( "" = " " ) est fausse ( le vide est différent du caractère espace).
c- Accès à un caractère
Pour accéder à un caractère de la chaîne, il suffit d’indiquer le nom de la chaîne suivi d’un entier
entre crochets qui indique la position du caractère dans la chaîne.
Exemple
chn ←"Turbo Pascal "
c = chn[7]
la variable c contiendra le caractère "P"
En général ; ch[i] indique l’ième caractère de la chaîne ch.
2.5.3. Procédures et fonctions standards sur les chaînes
a- Procédures standards
Procédure Rôle Exemple
efface(ch,p,n) Enlève n caractères de la chn ←"Turbo Pascal"
chaîne ch à partir de la efface(chn,6,7)
position p chn contiendra "Turbo"

insert(ch1,ch2,p) Insert la chaîne ch1 dans la ch1 ←"D"

chaîne ch2 à partir de la ch2 ←"AA"
position p insert(ch1,ch2,2)
ch2 contiendra "ADA"

convch(nbr,ch) Converti le nombre nbr en n=1665

une chaîne de caractère ch convch(n,chn)
chn contiendra la chaîne
"1665"
b. Fonctions standards
Fonction Rôle Exemple
long(ch) Retourne la longueur de la chn ← "Turbo Pascal"
chaîne ch n ← long(chn)
n contiendra 12
copy(ch,p,n) copie n caractères de la chaîne ch1 ← "Turbo Pascal"
ch à partir de la position p ch2 ← copy(ch1,7,6)
ch2 contiendra "Pascal"
position(ch1,ch2) Retourne la position de la1ère ch1 ← "as"
occurrence de la chaîne ch1 ch2 ← "Turbo Pascal"
dans la chaîne ch2 n← position(ch1,ch2)
n contiendra 8

ISSAT 8
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

3. Les opérateurs
Dans un algorithme, on utilise des opérateurs pour construire des formules.
Opérateurs arithmétiques Opérateurs relationnels Opérateurs logiques
* : la multiplication, < : strictement inférieur à, ET, OU, NON.
/ : la division, <= : inférieur ou égal à,
+ : l'addition, > : strictement supérieur à,
- : la soustraction. >= : supérieur ou égal à,
= : égal à,
<> : différent de.
Une formule est une suite d'objets séparés par des opérateurs.
4. Les prédicats
Lorsque le résultat d'évaluation d'une formule est de type booléen (vrai ou faux), cette
formule est alors appelée prédicat. En programmation, plusieurs opérations sont dépendantes
de l'évaluation d'une condition, c'est à dire de la valeur d'un prédicat.
Pour composer un algorithme, nous aurons souvent à exprimer des prédicats qui seront
par la suite évalués au moment de l'exécution. Pour écrire un prédicat, nous écrirons très
souvent une comparaison entre deux valeurs de même type. Une telle comparaison est appelée
prédicat élémentaire. Lorsque le prédicat élémentaire ne suffit pas pour exprimer une
situation, nous utilisons des prédicats composés à partir de prédicats élémentaires par l'emploi
de connecteurs logiques.
Exemples :
Si X et Y sont deux variables numériques de valeurs respectives 5 et 10, nous aurons :

Prédicat Valeur Evaluez les deux prédicats suivants

x=y faux lorsque x, y et z ont pour valeurs
x>2 vrai respectives 1, 3 et 2 :
x<y vrai (x = 1 OU y = 2) ET z > 3
x = 1 OU (y = 2 ET z > 3)

Il est parfois nécessaire d'utiliser des parenthèses dans l'expression d'un prédicat
composé. Les expressions entre parenthèses sont alors évaluées en premier.
5. Hiérarchie entre les opérateurs
Nous présentons dans le tableau ci-dessous la hiérarchie entre les différents opérateurs.
En effet, c'est la priorité d'évaluation dans l'ordre décroissant (du plus prioritaire au moins
prioritaire) :
Opérateur Intitulé
() les parenthèses
NON() la négation
*, / la multiplication et la division
+, - l'addition et la soustraction
<, <=, >, >=, =, <> les opérateurs relationnels
ET ET logique
OU OU logique

ISSAT 9
 Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

Dans l'évaluation d'une expression sans parenthèses, les opérations sont effectuées par
ordre de priorité. Les opérations de même priorité sont effectuées de la gauche vers la droite.
Ainsi, pour effectuer B + C/D – E*F, on calcule d'abord C/D puis E*F. Nous pouvons
évidemment modifier les priorités en utilisant des parenthèses. Dans l'expression B + C/(D-E),
nous calculerons d'abord D-E.
Opérateurs arithmétiques Opérateurs arithmétiques
* : la multiplication, * : la multiplication,
/ : la division, / : la division,
+ : l'addition, + : l'addition,
- : la soustraction. - : la soustraction.
Opérateurs relationnels Opérateurs logiques
< : strictement inférieur à, ET, OU, NON.
<= : inférieur ou égal à,
> : strictement supérieur à,
>= : supérieur ou égal à,
= : égal à,
<> : différent de.
Hiérarchie entre les opérateurs
Opérateur Intitulé
() les parenthèses
NON() la négation
*, / la multiplication et la division
+, - l'addition et la soustraction
<, <=, >, >=, =, <> les opérateurs relationnels
ET ET logique
OU OU logique

6. Structure d’un algorithme

Pour construire un algorithme, on doit mettre en évidence les 3 parties suivantes :

Nom de l’algorithme Algorithme Nom_algorithme

Déclarations de constantes
Déclarations de types
Déclarations Déclarations de variables
Début
Instructions
Instructions Fin

• Nom de l’Algorithme : c’est l’identification ou le nom.

• Déclarations : description de tous les objets utilisés dans l'algorithme, définition de constantes,
de types et de variables.

ISSAT 10
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

• Instructions: séquence d'actions à exécuter sur l'environnement afin de résoudre le problème.

Cette partie est également appelée le corps de l’algorithme.

7. Les déclarations
Pi = 3,14159
ch = “calcul” affectation de constantes
C = 'R'
test = TRUE

a, b, c : entier ⇔ a : entier
b : entier
c : entier
x, y, z : réel déclaration de variables
n, v : booléen
mot : chaîne
c : caractère

Dans le 1er bloc de l'algorithme, on doit énumérer :

- La liste des constantes, en leur affectant leurs valeurs.
- Les types qui ne sont pas standards.
- La liste des variables, tout en précisant leurs types respectifs.
8. Les instructions élémentaires

8.1. L’action d’affectation

Dans un environnement donné, pour attribuer à une variable (V) une valeur (E), nous
conviendrons d'utiliser la notation suivante : V ← e
Où :
V : le nom de la variable à laquelle on doit attribuer la valeur,
← : symbole, caractérisant l'action d'affectation,
e : représente la valeur à affecter et peut être :
• Une constante.
• Le nom d'une autre variable qui contient la valeur.
• Une expression de même type que V : expression logique ou arithmétique.
Exemples :
a) ENTIER ←1
b) NOM ← 'mohamed'
c) TOTAL ← SOMME
d) NB ← A+B
L'action (a) affecte à la variable numérique ENTIER la valeur 1.
L'action (b) affecte à la variable nom la chaîne ‘mohamed’; pour que cette action soit
correcte, il faut que NOM soit de type chaîne.
dans ces 2 premières actions, la valeur à affecter est indiquée à l'aide d'une constante.
dans (c), la valeur à affecter est une variable. TOTAL et SOMME doivent être de
même type.
Dans (d), on affecte à NB, le résultat d'un calcul numérique. NB, A et B doivent être
de même type. L'action (d) s'exécute en deux temps :
- calcul de la valeur de l'expression arithmétique (A+B)
- affectation de cette valeur à la variable NB.
Dans une action d'affectation, seule la variable dont le nom apparaît à gauche du signe ←
change de valeur.

ISSAT 11
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

8.2. L’action lire (introduction des données)

Cette action permet d'affecter, à une variable, une valeur saisie au clavier. Cette action est
validée par la frappe de la touche (entrée).
lire(v) : saisit une valeur au clavier et la mettre dans la variable v.
8.3. L'action écrire (sortie des résultats)
Il est possible de faire afficher une information à l'écran. Cette information peut être une
constante, la valeur d'une variable, une suite de valeurs, ou encore la combinaison de valeurs et de
messages.
Exemples :
écrire (i)
écrire ('Calcul de la somme des n premiers entiers')
écrire ('Résultat du calcul = ', S)
8.4. Les commentaires
Un commentaire est un texte qui aide à la compréhension et à la clarté lors de la lecture d'un
algorithme. Il est par contre ignoré par le processeur lors de l'exécution du programme.
Généralement ce texte est inséré entre { et } ou bien (* et *) ou encore entre /* et */.
8.5. Les instructions
Le corps d'un algorithme se compose d'instructions. Elles agissent sur l'environnement afin
de résoudre le problème posé. On distingue les instructions simples (une seule action) et les
instructions composées (un bloc contenant des séquences d'instructions et comptant pour une seule
instruction).
8.6. Exemple d’algorithme
Ecrire un algorithme intitulé « calculs » qui permet de saisir trois réels quelconques, de
calculer ensuite leur somme, leur produit et leur moyenne et d’afficher les résultats obtenus.
Méthode (ou analyse) : nous distinguerons trois étapes :
- Obtention des trois nombres : il nous faudra trois objets de type réel pour recevoir ces
nombres.
- Calcul des différents résultats : il nous faudra déclarer trois objets de type réel qui
reçoivent le résultat de chacune des opérations : somme, produit et moyenne.
- Edition des résultats.
Solution :
Algorithme calculs
Variable
Somme, Produit, Moyenne, nb1, nb2, nb3 : réel
Début
(* saisie des trois nombres *)
écrire ('entrez les trois nombres')
lire (nb1, nb2, nb3)

(* réalisation des différentes opérations *)

Somme ← nb1 + nb2 + nb3
Produit ← nb1 * nb2 * nb3
Moyenne ← somme / 3

(* édition des résultats *)

écrire ('la somme des trois nombres est : ', Somme)
écrire ('le produit des trois nombres est : ', Produit)
écrire ('la moyenne des trois nombres est : ', Moyenne)
Fin

ISSAT 12
Algorithmique & Structures de Données 1 Ch 2 : Les données et structure d’un algorithme

Remarque : Nous pouvons afficher directement le résultat des opérations sans passer par les
variables Somme, Produit et Moyenne. Ce qui donne une seconde version de l’algorithme
(calculs_v2) plus compacte et plus optimisée :

Algorithme calculs_v2
Variable
nb1, nb2, nb3 : réel
Début
(* saisie des trois nombres *)
écrire ('entrez les trois nombres')
lire (nb1, nb2, nb3)

(* réalisation des différentes opérations et édition des résultats *)

écrire ('la somme des trois nombres est : ', nb1+nb2+nb3)
écrire (‘le produit des trois nombres est : ‘, nb1 * nb2 * nb3)
écrire ('la moyenne des trois nombres est : ', (nb1 + nb2 + nb3) / 3)
Fin

ISSAT 13
Algorithmique & Structures de Données 1 Ch 3 : Les structures conditionnelles et répétitives

CH III : LES STRUCTURES CONDITIONNELLES ET REPETITIVES

1. Les structures conditionnelles
1.1. L’instruction conditionnelle SI
1.1.1. L’instruction conditionnelle SI à un choix

Une instruction conditionnelle à un choix à la syntaxe suivante :

si condition alors
suite d'instructions
finsi

Où :
condition : expression logique ayant pour valeur Vrai ou Faux.

Si la condition est vraie, la suite d'instructions est effectuée, si elle est fausse on ne fait rien.
1.1.2. L’instruction conditionnelle SI à deux choix
Une instruction conditionnelle à deux choix à la forme (ou la syntaxe) suivante :

si condition alors
suite d'instructions 1
sinon
suite d'instructions 2
finsi

Si la condition est vraie, la suite d'instructions 1 est effectuée, si elle est fausse c'est la suite
d'instructions 2 qui est effectuée.
Notons que les deux suites d'instructions peuvent comporter à leur tour des instructions
d'itération ou encore d'autres instructions conditionnelles.
Remarques :
Les règles suivantes doivent être toujours respectées dans un schéma conditionnel :
- A chaque si doit correspondre un finsi
- Un finsi revient au dernier si qui n’a pas de finsi
Exemple :
1) Reprendre l’exemple de l’organigramme vu au chapitre 1, et traduisez cet organigramme en un
algorithme en utilisant les instructions conditionnelles SI.
2) Ecrire un algorithme qui permet d’afficher à l’écran le classement, dans l’ordre croissant, de
deux réels quelconques, saisis au clavier par l’utilisateur.
Indication : les deux nombres sont lus dans les variables Inf et Sup. Ensuite, si Inf n’est pas la plus
petite valeur, on échange les deux valeurs pour avoir Inf < Sup.
Solutions :
Algorithme Exemple1
Variable
a, b, c : réel (* les coefficients de l'équation *)
x1, x2 : réel (* les racines si elles existent *)
d : réel (* le discriminant *)
Début
écrire(‘’entrez les 3 coefficients : ‘’)

ISSAT 14
Algorithmique & Structures de Données 1 Ch 3 : Les structures conditionnelles et répétitives

lire(a,b,c)
si a <> 0
alors
d ← -b – 4*a*c
si d >= 0
alors
x1 ← (-b + sqrt(d) ) / (2*a)
x2 ← (-b - sqrt(d) ) / (2*a)
écrire(‘’deux solutions réelles : x1 = ‘’, x1, ‘’et x2 = ‘’, x2)
sinon
écrire(‘’pas de solutions réelles‘’)
finsi
sinon
si b <> 0
alors
x1 ← -c/b
écrire(‘’une solution : ‘’, x1)
sinon
si c <> 0
alors
écrire(‘’équation impossible’’)
sinon
écrire(‘’tout réel est solution’’)
finsi
finsi
finsi
Fin

Algorithme Exemple2
Variable
Inf, Sup : réel (* les 2 nombres à classer *)
aux : réel (* une variable auxiliaire *)
Début
écrire(‘’entrez un premier nombre : ‘’)
lire(Inf)
écrire(‘’entrez un deuxième nombre : ‘’)
lire(Sup)
si Inf > Sup
alors (* échange des 2 valeurs *)
aux ← Inf
Inf ← Sup
Sup ← aux
finsi
écrire(‘’Le classement est : ’’, Inf, ‘’et’’, Sup)
Fin
1.2. L’instruction conditionnelle à choix multiple (selon)
Une généralisation supplémentaire de l'instruction if est l'instruction à choix multiple ou
sélective selon. Cette dernière se trouve implémentée dans beaucoup de langages de programmation
évolués. Elle est fréquemment utilisée en programmation s'il faut faire le choix entre plus de deux
alternatives.
Une instruction conditionnelle à choix multiple à la forme suivante :

ISSAT 15
Algorithmique & Structures de Données 1 Ch 3 : Les structures conditionnelles et répétitives

selon (variable) faire

valeur 1 : suite d'instructions 1
valeur 2 : suite d'instructions 2
…..
valeur n, valeur n+1 : suite d'instructions n
…..
autre : suite d'instructions 0
finselon

Si variable est égale à valeur i, on exécute la suite d’instruction i, et on passe à la suite de

l'algorithme, sinon on exécute la suite d'instructions 0 et on passe à la suite de l’algorithme.
Exemple :
Ecrire un algorithme permettant d’afficher le jour d’inscription d’un étudiant suivant le niveau
d’étude saisit au clavier :
1ère année 03/09/2004
2ème année 04/09/2004
ème
3 année 05/09/2004
4ème et 5ème année 06/09/2004
L’instruction conditionnelle SI à un choix

L’instruction conditionnelle SI à deux choix

L’instruction conditionnelle à choix multiple (selon)

selon (variable) faire

valeur 1 : suite d'instructions 1
valeur 2 : suite d'instructions 2
…..
valeur n, valeur n+1 : suite d'instructions n
…..
autre : suite d'instructions 0
finselon

ISSAT 16
Algorithmique & Structures de Données 1 Ch 3 : Les structures conditionnelles et répétitives

2. Les Structures répétitives

Nous appelons itération toute répétition de l’exécution d’une action ou d’une séquence
d’actions.

2.1. La boucle Pour

La boucle « POUR » est une boucle fixe, c’est à dire, nous connaissons d’avance le nombre
d’itérations que nous allons effectuer à l’aide de cette boucle. Sa syntaxe est la suivante :
pour v de vi à vf faire
<A>
finpour
Où :
v : variable de contrôle, ou compteur,
vi : valeur initiale de la variable v,
vf : valeur finale de la variable v,
A : action ou séquence d’actions à répéter.

Cette structure permet de répéter <A> un nombre connu de fois, d’où l’appellation boucle
fixe.
- si vi < vf : le mode de variation, lorsqu’il n’est pas précisé, suppose implicitement une
augmentation de 1 entre deux valeurs successives.
- si vi > vf : parcours décroissant de la variable v de pas –1.

Exercice :
i =100
1) Ecrire un algorithme permettant de calculer la somme S définie par : S = ∑ 1
i =1 i
2) Ecrire un algorithme permettant d’afficher les nombres paires dans les 100 premiers entiers
naturelles.
2.2. La boucle Répéter
Contrairement à la boucle « Pour », le nombre d’itérations dans la boucle « Répéter » n’est
pas prédéterminé. Sa syntaxe est la suivante :

répéter
<A>
jusqu’à <C>
Où :
A : action ou séquence d’actions à répéter.
C : condition logique (ou prédicat), servant de contrôle de l’itération.

Cette structure permet de répéter <A> jusqu’à ce que la condition <C> soit vraie. <C>
exprime la condition qui fait sortir le processeur de l’itération. La condition n’est testée qu’après
une première exécution de <A>. <A> est donc exécutée au moins une fois.
Exemple :
lire (a)
répéter
b  a DIV 3
a  a DIV 2
jusqu'à b < 2
écrire (a, b)

ISSAT 17
Algorithmique & Structures de Données 1 Ch 3 : Les structures conditionnelles et répétitives

Soit a = 18; le tableau ci-dessous reprend les différentes valeurs de b, a, et b<2 :

a b b<2
18 - -
9 6 faux
4 3 faux
2 1 vrai
Et la boucle se termine. Donc, a = 2 et b = 1.
2.3. La boucle Tant que faire
La syntaxe de la boucle « tant que » est la suivante :

Tant que <C> faire

<A>
fintanque
Où :
C : condition logique (ou prédicat), servant de contrôle de l’itération,
A : action ou séquence d’actions à répéter.

Cette structure permet de répéter <A> tant que la condition <C> est satisfaite. La condition
<C> est testée avant l’exécution de <A>. <A> peut alors ne jamais être exécutée.

Exemple :
lire (a)
b5
tant que b >= 2 faire
b  a DIV 3
a  a DIV 2
fintantque
écrire (a, b)

Soit a = 18; le tableau ci-dessous reprend les différentes valeurs de b, a, et b<2 :

a b b >= 2
18 5 vrai
9 6 vrai
4 3 vrai
2 1 faux
Et la boucle se termine. Donc, a = 2 et b = 1.

ISSAT 18
Algorithmique & Structures de Données 1 Ch 3 : Les structures conditionnelles et répétitives

Remarque :
Dans le corps d’une boucle, on peut avoir une ou plusieurs autres boucles. L’imbrication des
boucles doit suivre les règles suivantes :

ISSAT 19
Algorithmique & Structures de Données 1 Ch 4 : Les tableaux

CH IV : LES TABLEAUX
L'objet de ce chapitre est l'étude de quelques outils permettant de mieux structurer les
informations (ou les données). Un objet structuré (ou structure de données) est un groupe d'objets
que l'on considère comme un tout et auquel on peut, par exemple, donner un nom collectif.
1. Tableaux simples (à une dimension)
1.1. Définition
Un tableau à une dimension, appelé aussi vecteur, est une structure de données formée de
données de même type pouvant être accédé avec un indice. Il nous permet de manipuler plusieurs
valeurs en utilisant un seul nom de variable.
Pour définir un tableau, il faut préciser :
L'identificateur du tableau (son nom),
Le type des indices (entier),
Le type des éléments du tableau (composants).
1.2. Notations et déclarations
Un tableau T est déclaré de la façon suivante :

Variable Nom : tableau [min..max] de <Type>

Avec :
Nom : nom du tableau (caractère ou chaîne de caractère).
Type : le type des éléments du tableau.
Nous prendrons souvent min = 1 et max désignera alors le nombre des éléments du tableau,
qu'on appelle également longueur ou taille du tableau.
Exemple :
Moyenne : tableau [1..30] de réel
Absence : tableau [1..30] d’entier
Dans un tableau :
Tous les composants sont de même type.
Les indices des éléments d'un tableau peuvent varier dans n'importe quel intervalle
d'entiers naturels.
Le type des indices est entier.
Le nombre des composants est défini à la déclaration du tableau et ne change plus par la
suite.
Lors de la déclaration, le tableau est crée, mais les composants n'ont encore aucune valeur;
on dit qu'ils ne sont pas initialisés.
1.3. Identification d'un élément du tableau
D'une façon générale, T[i] identifie l'élément de position i dans le tableau T. Cela traduit
l'accès direct aux éléments du tableau. Il faut que : min< i <max.
Exemple :
Moyenne[13] = 13.40
Absence[27] = 4
1.4. Opérations sur les éléments d’un tableau
Nous pouvons effectuer sur les éléments d'un tableau toutes les opérations définies sur ceux-
ci, comme l'addition, la multiplication, la division, etc.
Exemples
1. Calculs divers :

ISSAT 20
Algorithmique & Structures de Données 1 Ch 4 : Les tableaux

Soit le tableau Tab suivant :

indice 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
contenu 11 12 11 10 15 12 13 16 17 18 20 13 15 12 17

- Quelle est la taille du tableau Tab ?

- A quel(s) indice(s) se trouve la valeur 18 ?
- A quel(s) indice(s) se trouve la valeur 12 ?
- Quelle valeur se trouve à l'indice 12 ?
- Quelle est la moyenne des 3 valeurs situées aux indices 7, 9 et 13 ?
- A quel indice se trouve la plus petite valeur du tableau ?
- A quel indice se trouve la plus grande valeur du tableau ?

Remarques :
- Ce tableau serait déclaré de la manière suivante :
Variable Tab : tableau [1..15] d’entier
- Le nom d'un tableau n'est jamais utilisé seul. Dans toutes les instructions (lecture,
écriture, calcul, test, etc.), il est toujours suivi d'un indice entouré de crochets.
2. Lecture d'un tableau :
Pour lire les éléments d’un tableau T, de taille N, on procède généralement de la façon ci-
dessous :

Début
……….
lire(N) /* lire la taille du tableau */
pour i de 1 à N faire /* lire les éléments du tableau */
lire ( T[i] )
finpour
……….
Fin
3. Ecriture d'un tableau :
Pour écrire (c’est à dire afficher) les éléments d’un tableau T, de taille N, on procède
généralement de la façon ci-dessous :
Début
……….
lire(N) /* lire la taille du tableau */
……….
pour i de 1 à N faire /* afficher les éléments du tableau */
écrire ( T[i] )
finpour
……….
Fin
2. Tableaux à deux dimensions
2.1. Définition
Si un traitement utilise plusieurs tableaux à une dimension, subissant le même traitement, on
utilise souvent un seul tableau à deux dimensions (ou matrice). Chaque élément du tableau est alors
identifié par deux indices : l’un désignant la ligne et l’autre la colonne.
2.2. Déclaration
Un tableau T à deux dimensions est déclaré de la façon suivante :

ISSAT 21
Algorithmique & Structures de Données 1 Ch 4 : Les tableaux

Variable Nom : tableau [min1..max1 , min2..max2] de <Type>

Avec :
Nom : nom du tableau (caractère ou chaîne de caractère).
Type : le type des éléments du tableau.
max1 – min1 + 1 = nombre d’éléments d’une ligne.
max2 – min2 + 1 = nombre d’éléments d’une colonne.
2.3. Exemple

variable tab : tableau [1..2 , 1..5] de char

colonne
ligne
1 2 3 4 5
1 a c x f n
2 ? ] & % Q

Le caractère ‘&’ est situé à ligne 2 et à la colonne 3, nous notons :

tab[2, 3] = ‘&’.

ISSAT 22
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

CH V : LES SOUS-PROGRAMMES, LES PROCEDURES ET LES

FONCTIONS
1. Les sous-programmes

Pour être lisible et efficace, un algorithme ne doit pas être excessivement long. D’autre part,
nous rappelons qu’une action au sein d’un algorithme peut-être elle-même un algorithme. Sa
description doit être faite en dehors des limites de l’algorithme qui l’utilise, en respectant les règles
syntaxiques habituelles.

D’une façon générale, la réalisation d’un programme peut amener le programmeur à

distinguer, au moment de la description du traitement, différentes parties dont l’assemblage
constituera l’algorithme principal, comme le montre le schéma ci-dessous :

Algorithme Principal Algorithme A Algorithme B Algorithme C Algorithme D

Début Début Début Début Début
appel de A …………. …………. …………. ………….
appel de B …………. appel de A appel de B appel de B
appel de C …………. …………. …………. appel de C
Fin Fin Fin Fin ………….
Fin

On peut alors décrire un algorithme sous une forme modulaire, afin de structurer son
architecture d’une manière claire. On peut également vouloir définir un sous-programme (ou un
module) lorsque le même type de traitement doit être répété plusieurs fois, à différents endroits du
programme.

Le module (ou de sous-programme), est décris qu’une seule fois et on effectue un appel pour
chaque demande d’exécution dans l’algorithme principal.

Nous parlerons alors d’algorithme appelant et d’algorithme appelé. L’appelant est celui qui
contient l’appel à un sous-programme (ou module) défini séparément, qui est lui-même l’appelé.

Appelant Appelé

Début Sous-programme Max_Min

….. Début
Saisir un tableau …..
Recherche du min et du max : Max_Min /* Recherche du maximum et du
Afficher le max et le min minimum d’un tableau /*
….. …..
Fin Fin

Les variables déclarées dans l’algorithme principal appelant sont appelées des variables
globales. L’appelé peut déclarer ses propres variables qu’il est le seul à utiliser. Dans ce cas, nous
parlerons de variables locales.
Il y a deux parties dans la définition d'un sous-programme :
- La spécification (QUOI ou nom du sous-programme).
- La réalisation (COMMENT ou regroupement d'actions).

ISSAT 23
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

Syntaxiquement, la partie spécification constitue l'en-tête du sous-programme et la partie

réalisation constitue le corps du sous-programme.

2. Les procédures
2.1. Définition

Un module auquel sont associés un nom et une liste de paramètres formels est appelé action
paramétrée ou procédure. Pour utiliser cette procédure, il faut lui fournir une liste de paramètres
réels (ou effectifs).

2.2. Déclaration d’une procédure

Une procédure est déclarée de la façon suivante :

PROCEDURE < nom_procédure > (< liste des paramètres formels >)
(* Les déclarations *)
Début
(* Les instructions de la procédure *)
Fin

2.3. Les paramètres formels et effectifs

- Un paramètre formel est une variable choisie comme paramètre à la définition d’un algorithme
(ou d’une procédure).
- Un paramètre effectif (ou réel) est une valeur utilisée dans un appel d’une procédure à la place
d’un paramètre formel.
- A l’exécution d’un appel, la correspondance entre un paramètre effectif et un paramètre formel
est définie par la position : le premier paramètre effectif correspond au premier paramètre
formel, le deuxième au deuxième, etc.
- Chaque appel doit comprendre autant de paramètres effectifs que la définition de la procédure
comporte de paramètres formels.
- Chaque paramètre effectif doit être du même type que le paramètre formel correspondant.
- Lors de l’exécution d’un appel, l’algorithme appelant travaille directement sur les paramètres
effectifs à la place des paramètres formels.

2.4. Exemple

Ecrire un algorithme « classer », permettant d’effectuer le classement, dans l’ordre croissant

de 3 nombres réels quelconques n1, n2 et n3 saisis au clavier par l’utilisateur. Cet algorithme doit
effectuer des classements 2 par 2 des 3 nombres, pour déduire le classement souhaité.
Indications et plan de l’algorithme :
− Lecture des 3 nombres (n1, n2, n3).
− Classement de n1 et de n2 (n1 < n2, par exemple).
− Classement de n2 et de n3 (n2 < n3 et n1 < n3 : mais il se peut qu’on ait n1 > n3, dans le
cas où n3 est le plus petit des trois réels ; ce qui exige le reclassement de n1 et de n2).
− Classement de n1 et de n2 (n1 < n2 < n3).
− Affichage des résultats.

Nous constatons que l’action de classement de 2 nombres sera répétée 3 fois dans
l’algorithme demandé. Pour cela, il est évident que l’écriture d’un module indépendant, permettant

ISSAT 24
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

d’effectuer le classement de 2 nombres et l’appel de ce module dans un programme principal serait

bien plus efficace. Ce module est la procédure Classer_2réels ci-dessous :

PROCEDURE Classer_2réels (x, y : réel)

Variables aux : réel
Début
Si x > y alors (* échange des 2 variables par l’intermédiaire de aux *)
aux  x
xy
y  aux
Finsi
Fin
Par la notation Classer_2réels(x, y), nous indiquons que les objets x et y ne sont pas des
variables, mais des paramètres qui représentent des objets ou valeurs sur lesquels on peut souhaiter
faire travailler l’algorithme classer_2réels.
L’algorithme effectuant le classement de 3 nombres s’écrira alors, en utilisant classer_2réels
comme suit :

Algorithme Classer_3réels
variable
n1, n2, n3 : réel
Début
écrire (‘’Saisir les 3 réels à classer’’)
lire(n1, n2, n3)
Classer_2réels(n1, n2)
Classer_2réels(n2, n3)
Classer_2réels(n1, n2)
écrire (‘’Le classement est : ‘’, n1 , n2 , n3)
Fin

Dans l’algorithme principal, l’écriture Classer_2réels(n1, n2) est un appel de la procédure

Classer_2réels par lequel on indique au processeur d’exécuter cet appel en faisant jouant à n1, le
rôle de x, et à n2, le rôle de y.
Les variables x et y sont les paramètres formels de la procédure Classer_2réels : ils servent
de modèle pour désigner les objets qui leurs seront substitués lors d’un appel de Classer_2réels.
Les variables n1 et n2 sont les paramètres effectifs d’un appel. Ce sont des variables sur
lesquelles s’exécute un appel qui emploi ces objets en lieu et place des paramètres formels.
3. Les fonctions
3.1. Définition
Une fonction est une procédure particulière. En effet, une fonction présente la particularité
de générer (retourner) une valeur d’un type déterminé, appelée résultat. Ce résultat peut être
exploité directement dans une instruction au sein de l’algorithme principal.
3.2. Déclaration d’une fonction
Une fonction est déclarée de la façon suivante :
FONCTION < nom_fonction > (< liste des paramètres formels >) : <type du résultat >
Début
(* les instructions de la<fonction *)
nom_fonction  ……… (* valeur que retourne la fonction *)
Fin
- Le type de la valeur que retourne une fonction est déclaré dans la première ligne de la
fonction, à la suite de la liste des paramètres formels.

ISSAT 25
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

- La valeur que retourne la fonction (le résultat) est déterminée par une ou plusieurs instructions
retour (affectation d’une valeur au nom de la fonction).
- Une fonction peut retourner une valeur booléenne (vrai ou faux). Elle est alors appelée
prédicat.
3.3. Appel d’une fonction
L’appel d’une fonction est contenu dans une instruction :
A  nom_fonction (< paramètres effectifs >)
si nom_fonction (< paramètres effectifs >) > valeur alors < action >
tantque nom_fonction (< paramètres effectifs >) = valeur faire < action >
Lors de l’utilisation d’une fonction, le système vérifie la comptabilité des types de variables traitées,
ainsi que le type du résultat retourné par la fonction.
3.4. Exemples
a. Ecrire une fonction, qui permet de déterminer si une personne est majeure à partir de son âge.
On suppose que l’âge de majorité est 18 ans.
FONCTION majeur (âge : entier) : booléen
début
si âge >= 18 alors
majeur  vrai
sinon
majeur  faux
finsi
fin
Une autre version, beaucoup plus simple, et tout aussi correcte, strictement équivalente à la
précédente serait :
FONCTION majeur_2 (âge : entier) : booléen
début
majeur_2  (âge >= 18)
fin
b. Ecrire une fonction qui retourne vrai, si et seulement si les 3 entiers a, b et c (qui sont les
paramètres de cette fonction) peuvent être les mesures des côtés d’un triangle rectangle.
FONCTION triangle_rectangle (a, b, c : entier) : booléen
début
triangle_rectangle  (a*a = b*b + c*c) OU (b*b = a*a + c*c) OU (c*c = a*a + b*b)
fin
3.5. Les variables globales et locales
3.5.1. Variables Globales
Une variable globale est une variable déclarée en entête de l’algorithme, c’est à dire dans le
programme principal, ou appelant. Dans ce cas, elle est accessible dans tout l’algorithme, y compris
les sous-programmes.
3.5.2. Variables locales
Par contre, une variable locale est une variable déclarée à l’intérieure d’une procédure. Dans ce cas,
elle ne peut être utilisée (ou connue) que par le sous-programme où elle a été déclarée.
3.5.3. Remarques
- Les variables locales sont des outils nécessaires à un sous-programme, que lui seul utilise pour
effectuer ses tâches.
- Les variables locales résident dans une zone mémoire appelée « la pile » et n’existent que
pendant la durée de l’exécution du sous-programme. Au retour dans le programme principal (ou
appelant), la pile est vidée.

ISSAT 26
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

- Si dans un algorithme, une variable locale a le même identificateur qu’une variable globale, alors
il s’agit pour le compilateur de deux variables différentes. De ce fait, les modifications de l’une
n’ont aucune conséquence sur l’autre.
- Un paramètre formel est toujours une variable locale et ne peut être utilisé en dehors de la
procédure où il est défini. Par contre, un paramètre effectif peut être une variable globale.
3.5.4. Exemple
L’exemple ci-dessous illustre l’utilisation des différentes variables dans un algorithme :

Variables
ALGORITHME Prog_principal Globales
VARIABLE
A, B : entier
Variables
Locales

PROCEDURE proc1 (Z : entier)

VARIABLE proc1 peut travailler avec ses
A, X, Y : entier variables locales A, X et Y, le
Début paramètre formel Z et la variable
globale B. La variable globale A
(* Instructions de proc1 *)
est inaccessible pour proc1.
Fin

PROCEDURE proc2 (M : entier)

VARIABLE proc2 peut travailler avec ses
A, B, Y : entier variables locales A, B et Y, le
paramètre formel M. Les
Début variables globales A et B sont
(* Instructions de proc2 *) inaccessibles pour proc2.
Fin

Début
(* Instructions de prog_principal *)
Fin
Les deux variables locales Y de proc1 et Y de proc2 ne sont accessibles que dans leurs
procédures respectives.
Un sous-programme peut appeler un sous-programme qui le précède ou s’auto appeler.
proc1 ne peut appeler que proc1, tandis que proc2 peut appeler proc1 et proc2.

A RETENIR :
Un sous-programme connaît :
- Ses propres objets : variables, constantes, type, etc. (variables locales).
- Ses paramètres formels (des données transmises par l'appelant).
- Les variables globales qui ne sont pas redéfinies dans sa partie déclaration.
- Tous les sous-programmes définis avant lui.
- Lui-même.

4. Les paramètres d’appel

La définition d’une procédure peut se faire avec ou sans paramètres d’appel.

ISSAT 27
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

4.1. Procédure sans paramètres d’appel

Certaines procédures sans paramètres d’appel effectuent un certain travail indépendamment
du reste du programme, c’est à dire sans aucun échange d’informations. C’est le cas pour beaucoup
de procédures qui servent à l’affichage de message, ou de menus.
Exemple :
Algorithme Exemple
Variable n : entier (* déclaration des variables du programme principal *)

PROCEDURE ERR
Début
écrire(‘’Vous vous êtes trompé ; recommencez’’)
Fin

PROCEDURE Lignes_Etoiles
Variable i : entier
Début
pour i de 1 à 80 faire
écrire(‘’*’’)
finpour
Fin

Début (* programme principal *)

Lignes_Etoiles
écrire(‘’Nom du programme’’)
Lignes_Etoiles
écrire(‘’Donnez un entier > 0’’)
Répéter
lire(n)
si n <= 0 alors ERR finsi
jusqu’à n > 0
………………….. (* suite des instructions *)
Fin (* programme principal *)

Lors de l’appel de la procédure ERR, le message « Vous vous êtes trompé ; recommencez »
sera affiché à l’écran. L’appel de la procédure Lignes_Etoiles provoquera le tracé à l’écran d’une
ligne de 80 étoiles.
4.2. Procédure avec paramètres d’appel
Une procédure a souvent besoin d’avoir des informations pour exécuter sa tâche. Lors de la
définition de la procédure, il est possible de choisir entre deux modes de passage (ou la
transmission) des paramètres : le passage par valeur et le passage par adresse.
4.2.1. Passage par valeur
Lors de l’appel d’une procédure, un emplacement dans la PILE est réservé pour chaque
paramètre formel. De même, un emplacement mémoire (SEGMENT DE DONNEES) est également
réservé pour chaque paramètre réel lors de la déclaration.
Pendant l’appel de la procédure, les valeurs des paramètres réels sont copiées dans les
paramètres formels. Ainsi, l’exécution des instructions de la procédure se fait avec les valeurs des
paramètres formels. Ainsi toute modification des paramètres formels ne peut affecter en aucun
cas celles des paramètres réels.
Les valeurs des paramètres réels sont connues avant le début de l’exécution de la procédure
et jouent le rôle uniquement d’entrées de la procédure.
Pour spécifier, dans une procédure, qu’il s’agit du mode « passage par valeur », il suffit
d’écrire simplement les noms des paramètres formels.

ISSAT 28
Algorithmique et Structures de Données Ch 5 : Les sous-programmes

Exemple :
Algorithme passage_par_valeur
variable r : entier
PROCEDURE ajouter ( k : entier ) (* k : paramètre formel *)
Début
écrire(‘’valeur de k = ’’, k)
k  k+1
écrire(‘’résultat dans la procédure = ’’, k )
Fin
Début (* programme principal *)
r  20 (* initialisation de r *)
ajouter ( r ) (* appel de la procédure "ajouter" par passage de la valeur 20 *)
écrire(‘’résultat dans l’algorithme = ’’, r )
Fin
4.2.2. Passage par adresse (ou variable)
La différence principale entre le passage de paramètres par valeur et le passage de
paramètres par adresse est que pour ce dernier mode un emplacement mémoire est réservé pour le
paramètre formel et le paramètre réel correspondant. Dans ce cas, le paramètre formel utilise
directement l’emplacement mémoire du paramètre réel. Par conséquent, toute modification du
paramètre formel entraîne la même modification du paramètre réel correspondant.
Pour spécifier, dans une procédure, qu’il s’agit du mode « passage par adresse », il suffit de
mettre devant le nom du paramètre formel la mention « variable ».
Exemple :
Algorithme passage_par_variable
variable r : entier
PROCEDURE ajouter ( variable k : entier) (* k : paramètre formel *)
Début
écrire(‘’valeur de k = ’’, k)
k  k+1
écrire(‘’résultat dans la procédure = ’’, k)
Fin
Début (* programme principal *)
r  20 (* initialisation de r *)
ajouter ( r ) (* r est appelé paramètre effectif ; r et k forment un alias *)
écrire(‘’résultat dans l’algorithme = ’’, r)
Fin

La variable globale r est modifiée au même titre que le paramètre formel k.

Rq :
- Une fonction renvoie une seule valeur au programme principal, alors qu’une procédure ne
retourne rien au programme principal. Par contre, une procédure avec passage d’adresse peut
retourner plusieurs valeurs.
- Toute fonction peut être alors convertie en procédure, mais l’inverse n’est pas vrai.

ISSAT 29
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

CH VI : ALGORITHMES DE RECHERCHE ET TRI

1. Les algorithmes de recherche
Les tableaux sont des structures statiques contigües, il est facile de rechercher un élément fixé dans
cette structure. Nous exposons ci-après des algorithmes élémentaires de recherche. Essentiellement
nous envisagerons la recherche séquentielle qui convient lorsqu'il y a peu d'éléments à consulter
(quelques centaines), et la recherche dichotomique dans le cas où la liste est triée.
1.1. Recherche séquentielle
La recherche séquentielle consiste à tous les éléments d’un tableau afin de trouver l’élément
concerné par la recherche.
Fonction recherche_sequentielle(T :Tab ; n,x :entier) :entier
variable
i:entier
Début
i←1
Tantque(i<=n et T[i]<> x)faire
i←i+1
FinTantque
si(i=(n+1))alors
recherche_sequentielle ←i
sinon
recherche_sequentielle ←-1
finSi
Fin

L’ordre des conditions est significatif car le compteur i peut atteindre la valeur n et T[n] n’existe
pas.
La version sentinelle
La technique sentinelle consiste à ajouter l’élément x à la fin du tableau. De cette façon, il est sûr
que x sera trouvé.
Fonction recherche_sequentielle_sentinelle(T :Tab ;n,x :entier) :entier
Variable
i:entier
début

i←1
T[n+1] ←x
Tantque(T[i]<>x)faire
i←i+1
Fin Tantque
si(i=(n+1)) alors
recherche_sequentielle_sentinelle←i
sinon
recherche_sequentielle_sentinelle← −
finSi
Fin

1.2. Recherche dichotomique

Soit t un tableau de n entiers rangés par ordre croissant par exemple.
On recherche le rang (la place) de l'élément x dans ce tableau. L'algorithme renvoie le rang (la
valeur -1 est renvoyée lorsque l'élément x n'est pas présent dans le tableau T). Au lieu de rechercher

ISSAT 30
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

séquentiellement du premier jusqu'au dernier, on compare l'élément x à chercher au contenu du

milieu du tableau. Si c'est le même, on retourne le rang du milieu, sinon l'on recommence sur la
première moitié (ou la deuxième) si l'élément recherché est plus petit (ou plus grand) que le
contenu du milieu du tableau.
Fonction recherche_dichotomique(T : Tab ; n,x :entier) : entier
variable
g,d,m:entire
début
g ←1
d← n
m ← (g + d)/2
répéter
si (T[m] = x) alors
recherche_dichotomique ← m
sinon
si (x < T[m]) alors
d ← m - 1
sinon
g← m + 1
finSi
finSi
m ← (g + d)/2
jusqu’à(g>d);
recherche_dichotomique ← -1
Fin

2. Les tris

Les algorithmes de tri servent principalement à ordonner les données, mais ils participent aussi à la
conception d’autres algorithmes, comme les recherches, en organisant préalablement les données.
2.1. Le tri par sélection
C’est l’un des tris les plus simples à mettre en œuvre. Il s’inspire d’une méthode empirique qui
consiste à rechercher la plus petite valeur et à l’inverser avec la première position, puis à rechercher
la deuxième plus petite valeur et à l’inverser avec la deuxième position, et ainsi de suite.
L’inversion de deux valeurs est souvent employée dans les algorithmes de tri.
Le tri par sélection est basé sur deux boucles POUR imbriquées. La première boucle parcourt la
liste des valeurs du début à la fin. La deuxième boucle recherche la plus petite valeur de la position
courante (compteur de la première boucle), à la fin du tableau, puis l’inverse avec la position
courante. La partie gauche de la liste est triée au fur et à mesure de l’avancement de la première
boucle. La figure 1 présente les étapes du tri, lorsque la boucle principale pointe sur la troisième
case du tableau tab.

ISSAT 31
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri
Boucle principale
Figure 1
Tri Sélection. Boucle recherchant la plus petite valeur

1 2 3 4 5 6 7
tab 3 4 78 45 5 9

Partie triée

k
1 3
78

1 2 3 4 5 6 7
tab 3 4 78 45 5 9

1 2 3 4 5 6 7
tab 3 4 5 45 78 9

Partie triée

Ce tri minimise le déplacement des données. Chaque valeur minimale sélectionnée est placée
directement à sa position finale, ce qui en fait un algorithme de choix dans le traitement de données
volumineuses, et donc coûteuses en termes de déplacements.
La réalisation du tri sélection passe par les sous traitements suivants :
Enoncé :
Ecrire une fonction permettant de chercher le plus petit entier dans un tableau T contenant N entier.
Solution :
Fonction minimum (T :Tab ; n :entier) :entier
variable
j,min :entier
début
min←T[1];
Pour j de 2 à n faire
si(T[j]<min) alors
min←T[j]
finSi
FinPour
minimum← min;
Fin

Enoncé :
Modifier la fonction précédente pour qu’elle retourne l’indice du plus petit entier dans un tableau T
contenant N entiers.

ISSAT 32
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

Solution:
Fonction indice_minimum (T :Tab ;n :entier) :entier
variable
j,indice_min :entier
Début
indice_min←1
Pour j de 2 à n faire
si(T[j]<T[indice_min]) alors
indice_min←j
finSi
FinPour
indice_minimum ← indice_min
Fin

Tri Sélection :

On suppose que le tableau contient N éléments (ai avec 1≤ i ≤N)

On cherche le minimum dans a1…aN et on le place dans la case 1
On cherche le minimum dans a2…aN et on le place dans la case 2
…
On remarque que l’ensemble diminue jusqu’à ce qu’il contient un seul élément aN. Donc ce n’est
pas important de chercher le minimum dans un ensemble qui contient un seul élément. Ce qui
explique la première boucle :
Pour i de 1 à N-1
On obtient donc le pseudo code suivant :
Pour i de 1 à N-1 faire
Chercher la position du minimum dans l’ensemble ai…aN
Permuter le minimum avec l’élément à la position i
Fin Pour
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

Algorithme Tri_Sélection :
Procédure Tri_Selection(var T :Tab ;n :entier)
variable
i,m,j,inter:entier
début
Pour i de 1 à n-1 faire
m←i
Pour j de i+1 à n faire
si(T[j]<T[m])alors
m←j
finSi
FinPour
si(m<>i)alors
inter←T[i]
T[i] ←T[m]
T[m] ←inter
finSi
FinPour
Fin

2.2. Le tri par insertion

Le tri par insertion s’inspire d’un processus naturel utilisé dans le tri des cartes qu’un joueur
possède dans sa main. Pour organiser son jeu, le joueur prend chaque carte et l’insère à sa place en
décalant les autres. Le tri par insertion n’est pas le plus performant pour un grand ensemble de
données, mais il devient intéressant quand il faut insérer une seule donnée dans un ensemble déjà
trié.
Le tri par insertion utilise le processus élémentaire d’insertion d’un élément dans la liste des
valeurs. Ce processus de base, est présenté à la figure 2. Il décale vers la droite les données situées à
droite de la position d’insertion en partant de la fin, pour libérer la case d’insertion. La dernière case
est copiée dans la case suivante, puis c’est au tour de l’avant-dernière case, et de proche en proche,
on remonte jusqu’à la case à libérer. Une fois cette case libre, on y copie la donnée à insérer.
Figure 2 Sens de progression

Insertion d’un élément par décalage

des cases d’un tableau.
1 2 3 4 5 6 7
4
tab 3 4 78 45

1 2 3 4 5 6 7
tab 3 4 5 78 45

Dans le cas du tri sur place (dans un seul tableau de données), une première boucle POUR parcourt
chaque élément du tableau, et l’insère à sa place dans la partie gauche du tableau. Pour effectuer
cette insertion, on conserve la valeur indiquée par le compteur de la boucle principale (étape 1),
puis on effectue une boucle de décalage des cases précédentes d’une case vers la droite, tant que la

ISSAT 34
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

valeur à insérer est plus petite que la valeur précédente (étape 2). Quand cette boucle interne
s’arrête, la valeur d’insertion a trouvé sa position. Il suffit de la copier dans la case libérée (étape 3).
La figure 3 présente ce traitement.

Boucle principale
Figure 3
Tri Insertion. 1 2 3 4 5 6 7
Etape 1 tab 3 4 45 78 5
Partie triée
5 val

Boucle de décalage

1 2 3 4 5 6 7
Etape 2 tab 3 4 45 78 5

1 2 3 4 5 6 7
Etape 3 tab 3 4 45 45 78

5 val

1 2 3 4 5 6 7
Etape 4 tab 3 4 5 45 78
Partie triée

Il effectue un peu moins de comparaisons que le précédent mais plus d’échanges, ce qui peut être
pénalisant avec des données volumineuses. La performance de cet algorithme s’améliore nettement
avec des données globalement triées.
Nous présentons dans ce qui suit les sous traitements nécessaires afin de pouvoir comprendre le
principe du tri insertion
Enoncé :
Ecrire une procédure permettant d’insérer un entier X dans un tableau T contenant N entiers
ordonnés dans l’ordre croissant tout en conservant l’ordre.

ISSAT 35
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

Solution :
Procédure Inserer_Element(var T :Tab ; n,x :entier)
variable
j : entier
Début
j←n
Tantque (j>=1 et T[j]>x)faire
T[j+1] ← T[j]
j←j-1
finTantque
T[j+1] ←x
Fin

Lors de l’élaboration de cet algorithme on peut laisser la condition (j>=1) à déduire après un
tournage à la main (exemple : 5 10 12 14 et X=2). Le débordement du compteur j nécessite la
condition j>=1 pour limiter la décrémentation du j. Après avoir déduit la manque de cette
condition on peut l’ajouter de cette façon (while (T[j]>x && j>=1)) et on refait le tournage
à la main avec le même exemple. On comprend bien que l’ordre des conditions est significatif de
plus les opérations logiques « et » et « ou » sont progressives c'est-à-dire lorsqu’on a plusieurs
conditions liées avec l’opération « et » il suffit qu’une condition est fausse donc toute l’expression
sera évaluée à faux et ce n’est pas la peine d’évaluer les conditions restantes et c’est le même pour
l’opération « ou » il suffit qu’une condition sera évaluée à vrai alors toute l’expression sera vrai.
On arrive maintenant au Tri Insertion :

L’idée de ce tri consiste à supposer qu’un tableau contenant un seul élément est un tableau trié.
Donc lorsque on a une suite de a1…aN avec N le nombre d’éléments présents dans le tableau, le
singleton a1 est un tableau trié. On insère a2 dans le tableau trié qui contient a1 on obtient donc un
tableau qui contient deux éléments triés, après on passe à insérer a3, etc...
Ce qui vérifie la première boucle

ISSAT 36
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

pour i de 2 à n faire : car on commence l’insertion à partir du deuxième élément.

On déduit donc le pseudo code suivant :
Pour i de 2 à n faire
Insérer l’élément T[i] dans le tableau trié (T[1]…T[i-1])
Fin pour
Algorithme Tri_Insertion :
Procédure tri_insertion(var T :Tab ; n :entier)
variable
i,j,v: entier
Pour i de 2 à n faire
v ← T[i];
j←i-1;
Tantque(j>=1 et T[j]>v)faire
T[j+1] ←T[j];
j←j-1;
FinTantque
T[j+1] ←v;
FinPour
Fin

2.3. Le tri à bulles

Le tri à bulles propose une approche assez bizarre. On peut même se demander comment la
méthode proposée aboutie au tri des données. Il est construit à partir de deux boucles imbriquées
qui évoluent, et d’un processus d’inversion des éléments successifs qui ne sont pas ordonnés.
La figure 4 présente le tri à bulles. La première boucle indique le nombre d’éléments qui ont arrivés
à leurs places finales et sert comme une limite pou le compteur de la deuxième boucle. La deuxième
boucle interne progresse du début du tableau jusqu’à la case pointée par le premier compteur (celui
de la boucle principale). A l’intérieur de cette deuxième boucle, qui ne gère que la partie gauche du
tableau, on compare les éléments situés dans les deux cases successives, et on les inverse s’ils ne
sont pas dans l’ordre. Ainsi, sur la figure 4, la première valeur (9) est plus grande que la deuxième
(5), donc on les inverse. Ensuite, on compare la deuxième valeur (qui est 9 à la suite de première
inversion) avec la troisième (12). Elles sont dans l’ordre, donc on ne les inverse pas. On effectue le
même traitement avec le troisième élément (12) et le quatrième (45), qui sont déjà ordonnés. Le
quatrième élément (45) est inversé avec le cinquième (4). Le cinquième élément (45 à la suite de
l’inversion précédente) est inversé avec le sixième (3). Le sixième élément (45 à la suite de
l’inversion précédente) est inversé avec le septième (41). La boucle interne s’arrête enfin, car la
partie gauche du tableau (du début jusqu’à la case indiquée par l’indice de la première boucle) a été
totalement parcourue. La boucle interne a pour effet de faire remonter vers la fin du tableau les
éléments de poids fort. La figure montre que la valeur 45 remonte jusqu’à la fin du tableau et vient
se « coller » à la partie droite déjà triée. Quand la boucle interne est terminée, la boucle principale
effectue une nouvelle itération en régressant d’une case, ce qui fait passer le dernier élément (la
valeur 45) dans la partie droite du tableau, qui ne contient que les données à leur place finale. La

ISSAT 37
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

boucle interne est à nouveau déroulée sur la partie gauche du tableau, moins une case, et le
processus recommence.

Figure 4 Boucle principale

Tri A Bulles.
1 2 3 4 5 6 7 8
tab 9 5 12 45 4 3 41 78

Partie triée

Boucle interne

1 2 3 4 5 6 7 8
tab 9 5 12 45 4 3 41 78

Partie triée

Boucle principale

1 2 3 4 5 6 7 8
tab 5 9 12 4 3 41 45 78

Partie triée
Quand on peut constater que le tableau est trié ?
Le tableau est devenue trié si on parcourt le tableau et on n’effectue aucune permutation c'est-à-dire
on a toujours T[i] < T [i+1].
On passe à la question suivante : Est-ce qu’on sait après combien d’itérations le tableau deviendra
trié ?
La réponse est : Non
On conclue donc qu’on ne doit pas utiliser la boucle pour. Il reste don à choisir entre la boucle
« Tant que » et « répéter…jusqu’à ».
La question suivante : Est-ce qu’on peut déduire que le tableau est trié sans effectuer aucune
comparaison ?
La réponse : On doit au minimum parcourir le tableau une seule fois avant de tester si le tableau est
trié ou non. Alors nous devons utiliser la boucle « répéter…jusqu’à »
On élabore maintenant le Tri A Bulles :

ISSAT 38
Algorithmique et Structures de Données Ch 6 : Algorithmes de recherche et tri

Algorithme Tri_A_Bulles :

Procédure Tri_A_Bulle(var T :Tab ; n :entier)

variable
i,j,inter:entier
Trie:booleen
début
j←0;
répéter
Trie←vrai
Pour i de 1 à n-j faire
si(T[i]>T[i+1])alors
inter ←T[i]
T[i] ← T[i+1]
T[i+1] ← inter
Trie ← faux
finSi
FinPour
j←j+1;
jusqu’à(Trie)
Fin