Cours Algorithmiques et

programmation
Année universitaire 2024/2025
Pr. F. Ben Bouazza
[email protected]

13/10/2024 Pr. F. Ben Bouazza 1

Organisation du cours
• Les instructions itératives (les boucles)
• L’instruction « Pour »
• L’instruction « Tant que… faire »
• L’instruction « Répéter… jusqu’à »
• Les tableaux
• Tableaux à une seule dimension
• Tableaux à deux dimensions
• Les enregistrements (structures)
• Les fonctions et les procédures
• Programmation avec langage C

Pr. F. Ben Bouazza 2

 Introduction aux algorithmes

• Contexte
• « Informatique » est un concept (1962 par Philippe Dreyfus) pour
caractériser le traitement automatique de l’information: « information
automatique ».
• Ce terme a été accepté par l’Académie française en avril 1966, et
l’informatique devient officiellement la science du traitement automatique
de l’information, où l’information est considérée comme le support des
connaissances humaines et des communications dans les domaines
techniques, économiques et sociaux.

Pr. F. Ben Bouazza 3

 Introduction aux algorithmes

• Notions élémentaires
• Informatique : la science du traitement automatique de l’information. Elle traite
de deux aspects complémentaires :
o Programmes ou logiciels (software) qui décrivent un traitement à réaliser,
o Machines ou le matériel (hardware) qui exécute ce traitement.

Pr. F. Ben Bouazza 4

 Introduction aux algorithmes

Algorithme
• Un algorithme est une suite ordonnée d’instructions qui indique la démarche à suivre
pour résoudre un problème ou effectuer une tâche. Le mot algorithme vient du nom
latinisé du mathématicien perse AlKhawarizmi « le père de l'algèbre ».

• Exemple : Appel téléphonique

a. Ouvrir son téléphone,

b. Chercher/Composer le numéro du destinataire,
c. Appuyer sur le bouton « Appel ».
Muhammad Ibn Mūsā al-
Khuwārizmī (~780-850)

Pr. F. Ben Bouazza 5

 Introduction aux algorithmes

L'algorithmique
• La science des algorithmes. Elle s’intéresse à l’art de
construire des algorithmes ainsi qu’à déterminer leur
validité, leur robustesse, leur réutilisabilité, leur
complexité ou leur efficacité.

Décrire La démarche de résolution du problème

Traduire un algorithme dans un langage « compréhensible » par

l’ordinateur

Exécution automatiquement
Etapes de développement
Pr. F. Ben Bouazza 6
 Introduction aux algorithmes
• L'algorithmique
Exemple : Calcul de la moyenne d’un étudiant
Supposons qu’on doit calculer la moyenne d’un étudiant pour un
ensemble de matières.

Principe du traitement automatisé

Pr. F. Ben Bouazza 7

 Introduction aux algorithmes
L'algorithmique
Exemple : Calcul de la moyenne d’un étudiant
1. Définir le nombre des matières concernées ainsi que les notes et les
coefficients ;
2. Réaliser les opérations suivantes :
• Multiplier chaque note d’une matière par son coefficient,
• Calculer la somme des résultats des multiplications,
• Diviser la somme obtenue par le total des coefficients,
3. Afficher le la moyenne de l’étudiant (résultat final).

Pr. F. Ben Bouazza 8

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Structure générale:
Un algorithme se compose généralement de deux parties :
• Partie déclarative (entête de l’algorithme): contient généralement les
déclarations (des constantes, des variables, etc.)
• Partie corps de l’algorithme : constituée d’une ou plusieurs séquences
d’instructions faisant appel à des opérations de base à exécuter par
l’ordinateur.

Pr. F. Ben Bouazza 9

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Structure générale:
Syntaxe:

Pr. F. Ben Bouazza 10

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les variables et les constantes:
L’élément unitaire de stockage de l’information
est appelé bit (0 ou 1).
Dans la mémoire de l’ordinateur, les données
sont manipulées par groupes de 8 bits (octets),
ou plus (mots de 16, 32, 64 bits,…).
Une case mémoire est donc appelée mot et
pour que l’unité centrale puisse stocker une
information et la retrouver dans la mémoire,
chaque mot est repéré par une adresse. Organisation de la mémoire

Pr. F. Ben Bouazza 11

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les variables et les constantes:
La variable (Var): Une case mémoire destiné à contenir des valeurs de type défini au
préalable (nombres, caractères, chaînes de caractères,…). Elle possède un nom, un
type, et un contenu qui peut être modifié au cours de l’exécution de l’algorithme.
La constante (Cost): Sa valeur reste inchangée tout au long du déroulement
(exécution) de l’algorithme.
Syntaxe :
Var nom_variable : type ;
Const nom_constante = valeur ;

Pr. F. Ben Bouazza 12

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les types de base:
Le type d’une variable définit l’ensemble des valeurs que peut prendre la variable,
ainsi que l’ensemble des opérations que l’on peut appliquer sur cette variable.
i. Type entier
C’est un type numérique représentant l’ensemble des entiers relatifs, tels que: -9, 0,
1, 31, …. Les opérations permises sur ce type sont : +, - , *, div (division entière) et
mod (modulo ou reste de la division entière). Le mot clé est : entier.
Exemple : Var x : entier ;

Pr. F. Ben Bouazza 13

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les types de base:
ii. Type réel
C’est un type numérique aussi représentant l’ensemble des nombres réels, tels que :
0.25, -1.33, 2.5 e+10,… . Les opérations permises sur ce type sont : +, -, * et /.
Le mot clé est : réel.
Exemple : Var y : réel ;

Pr. F. Ben Bouazza 14

 Introduction aux algorithmes
• Caractéristiques des algorithmes:
ü Les types de base:
iii. Type caractère
• Ce type représente tous les caractères alphanumériques tels que : ʹaʹ, ʹAʹ, ʹ3ʹ,
ʹ%ʹ, ʹ ʹ, …
• Les opérations supportées par ce type sont : =, ≠, <, <=, >, >=.
• Le mot clé est : caractère.
• Exemple : Var a : caractère ;

Pr. F. Ben Bouazza 15

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les types de base:
iv. Type booléen
Ce type est utilisé dans la logique pour représenter les deux valeurs : vrai et faux.
Les opérations prises en charge sont : NON, ET, OU.
Le mot clé est : booléen.
Exemple : Var b : booléen ;

Pr. F. Ben Bouazza 16

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les types de base:
iv. Chaîne de caractères
Ce type représente les mots et les phrases tels que "Algorithmique", "Cours", etc. Le
mot clé utilisé est : chaîne.
Exemple : Var c : chaîne ;

Pr. F. Ben Bouazza 17

 Introduction aux algorithmes

• Caractéristiques des algorithmes:

ü Les types de base:
Exemple :
Var x, y : entier ;
z, w : réel ;
lettre : caractère ;
nom : chaîne ;
Etat : booléen ;
Const n = 100 ;
arobase = ʹ@ʹ ;
mot = "bonjour" ;
Pr. F. Ben Bouazza 18
 Les instructions
Les algorithmes comportent généralement deux types d’instructions :

o Les instructions simples : qui permettent la manipulation des

variables telles que l’affectation, la lecture et l’écriture.

o Les instructions de contrôle : qui précisent l’enchainement

chronologique des instructions simples. C’est en particulier le cas des
instructions conditionnelles ou les tests.

Pr. F. Ben Bouazza 19

 Les instructions simples

• L’instruction d’affectation
Permet d’assigner une valeur à une variable selon la syntaxe suivante :
variable ← expression ;
Une instruction d’affectation est exécutée comme suit :
- L’évaluation de l’expression située à droite de l’instruction
- L’affectation du résultat à la variable située à gauche de l’instruction.

Pr. F. Ben Bouazza 20

 Les instructions simples

• L’instruction d’affectation
L’expression peut être :
• Une variable ( v ← x )
• Une expression arithmétique ( e ← x + y )
• Une expression logique ( d ← a ou b )
Remarque :
Une constante ne figure jamais à gauche d’une instruction d’affectation.
Exemple d’instruction fausse : Const z = 1 ; z ← 2 ; « Faux »

Pr. F. Ben Bouazza 21

 Les instructions simples
• L’instruction d’affectation
Remarque :
• Après une affectation, l’ancien contenu d’une variable est substitué (écrasé) par le nouveau
contenu.
Exemple : Var a : entier ;
a←1;
a←2;
• Après la deuxième affectation, la valeur de a est devenue 2 (la valeur 1 est écrasée).
Une instruction d’affectation doit se faire entre deux types compatibles.
Exemple : Var x, y : entier ; z : réel ; a, b : caractère ;

Pr. F. Ben Bouazza 22

 Les instructions simples
• L’instruction d’affectation
Symbole Signification Symbole Signification
Les opérateurs arithmétiques (par ordre de Les opérateurs de comparaison ou relationnels
priorité) > , >= supérieur et supérieur ou égal
^ ou ** Puissance < , <= inférieur et inférieur ou égal
* , / , mod Multiplication, Division et Modulo = , ≠ (ou < >) égal et différent
+,- Addition et Soustraction Les opérateurs logiques ou booléens
Les opérateurs logiques ou booléens NON ET négation de conjonction
NON Non logique (négation) NON OU négation de disjonction
ET Et logique (conjonction)
OU Ou logique (disjonction)

Les expressions logiques peuvent être composées des opérateurs logiques et/ou relationnels.
Par exemple, (A<20) ET (B>=10) est Vrai si A est inférieur à 20 et B est égal ou supérieur à 10, et faux sinon.

Pr. F. Ben Bouazza 23

Les instructions simples

• L’instruction de lecture
Cette instruction permet de lire des valeurs en entrée (input) et les affecter aux
variables stockées dans la mémoire. Les valeurs affectées sont souvent des données
introduites à partir d’un périphérique d’entrée tel que le clavier.
Syntaxe :
Lire (var1, var2,…) ;
Exemple :
Lire(x) : lit et stocke une valeur donnée
dans la case mémoire associée à x.
Lire(x, y) : lit et stocke deux valeurs, la
première dans x et la deuxième dans y.

Pr. F. Ben Bouazza 24

 Les instructions simples

• L’instruction d’écriture
Cette instruction permet d’écrire en sortie (output) les données résultant d’un
traitement effectué par l’algorithme (valeur, texte, …) en les affichant par exemple sur
un périphérique de sortie tel que l’écran.
Syntaxe :
Ecrire (var1, var2, expr1, expr2, …) ;
Exemple :
Calculez et affichez la moyenne:
l’utilisateur introduit 10 pour x et 20
pour y alors l’affichage sera : La
moyenne est : 15

Pr. F. Ben Bouazza 25

 Les instructions simples

Exercices:
1. Ecrire un algorithme qui lit le prix HT d’un article, le nombre
d’articles et le taux de TVA, et qui fournit le prix total TTC
correspondant.

Pr. F. Ben Bouazza 26

 Les instructions conditionnelles (les alternatives)
• Structure d’un test
Il existe deux formes de test : forme simple (ou réduite) et forme
complète.
ü Forme simple
Une action, qui correspond à une ou plusieurs instructions, est exécuté si
une condition est vérifiée. Sinon l’algorithme passe directement au bloc
d’instruction qui suit immédiatement le bloc conditionnel.
Syntaxe :
Si (condition) Alors
instruction(s) ; // action
Finsi

Pr. F. Ben Bouazza 27

 Les instructions conditionnelles (les alternatives)

• Structure d’un test

ü Forme complète
Cette forme permet de choisir entre deux actions selon qu’une
condition est vérifiée ou non.
Syntaxe :
Si (condition) Alors
instruction(s) 1 ; // action1
Sinon instruction(s) 2 ; // action2
Finsi

Pr. F.Pr.
BenF. Bouazza
Ben Bouazza 28
 Les instructions conditionnelles (les alternatives)

• Tests imbriqués
La forme complète permet de choisir entre plusieurs actions en imbriquant des formes
simples.
Syntaxe :
Si (condition1) Alors instruction(s) 1 ;
Sinon Si (condition2) Alors instruction(s) 2 ;
Sinon Si (condition3) Alors instruction(s) 3 ;
…
Sinon instruction(s) N ;
FinSi
FinSi
FinSi
FinSi
Pr. F. Ben Bouazza 29
 Les instructions conditionnelles (les alternatives)

• Tests imbriqués
l’utilisation de tests imbriqués permet de :
ü Simplifier le (pseudo-) code : moins de conditions (simples ou
composées).
Un algorithme (ou programme) plus simple et plus lisible.
ü Optimiser le temps d’exécution : dans le cas où la première
condition est vérifiée, l’algorithme passe directement à la fin, sans
tester le reste qui est forcément faux.
Un algorithme (ou programme) plus performant à l’exécution.
Pr. F. Ben Bouazza 30
 Les instructions conditionnelles (les alternatives)

• Tests imbriqués
Exemple : Etat de l’eau
Dans les conditions normales de température et de pression, l’eau
est sous forme de glace si la température est inférieure ou égale à 0°
C, sous forme de liquide si la température est comprise entre 0° C et
100° C et sous forme de vapeur au-delà de 100° C. Ecrivons
l’algorithme qui permet de vérifier l’état de l’eau selon sa
température.

Pr. F. Ben Bouazza 31

 Les instructions conditionnelles (les alternatives)
• Les choix multiples
Il existe une autre variante d’instructions conditionnelles qui permet d’effectuer des
actions différentes suivant les différentes valeurs que peut avoir une variable.
Syntaxe :
Selon (variable)
valeur1 : instruction(s) 1 ;
valeur2 : instruction(s) 2 ;
…
valeurN : instruction(s) N ;
défaut : instruction(s) par défaut;
FinSelon ;

Pr. F. Ben Bouazza 32

 Les instructions conditionnelles (les alternatives)

• Les choix multiples

Dans la structure de test à choix multiples :

o L’action peut être une suite d’instructions ;

o La valeur est une constante de même type que la variable ;

o La partie « défaut » est exécutée si aucun des autres cas n’est vérifié ;

o L’exécution des différents cas (y compris le cas par défaut) est exclusive:
l’exécution d’un seul cas provoque la sortie de cette structure.

Pr. F. Ben Bouazza 33

 Les instructions itératives (les boucles)

Une boucle (ou itération) est une instruction de contrôle qui permet
de répéter plusieurs fois un ensemble d’instructions. Généralement,
deux cas sont distingués :
• Le nombre de répétitions est connu.
• Le nombre des répétitions est inconnu ou variable.

Pr. F. Ben Bouazza 34

 Les instructions itératives (les boucles)
L’instruction « Pour »
Cette structure possède un indice (compteur) de contrôle d’itérations
caractérisé par :
• une valeur initiale,
• une valeur finale,
• un pas de variation.
Syntaxe :
Pour indice de début à fin Pas valeur_du_pas
instruction(s) ;
FinPour

Pr. F. Ben Bouazza 35

 Les instructions itératives (les boucles)
Exemple : un compteur croissant/décroissant
Les deux algorithmes suivants comptent de 1 à N et de N à 1
respectivement.
Algorithme compteur_croissant ; Algorithme compteur_decroissant ;
Var i : entier ; Var i : entier ;
Const N=100 ; Const N=100 ;
Début Début
Pour i de 1 à N /* par défaut le pas = 1 */ Pour i de N à 1 /* par défaut le pas = -1 */
Ecrire (i); Ecrire (i);
FinPour FinPour
Fin Fin
Résultat d’exécution : 1,2, 3, … , 99, 100 Résultat d’exécution : 100, 99, 98, … , 2, 1

Pr. F. Ben Bouazza 36

 Les instructions itératives (les boucles)

L’instruction « Tant que… faire »

Cette instruction permet de tester une condition et répéter le traitement
associé tant que cette condition est vérifiée.
Syntaxe:
Tant que condition faire
instruction(s) ;
FinTq

Pr. F. Ben Bouazza 37

 Les instructions itératives (les boucles)

L’instruction « Répéter… jusqu’à »

Dans cette instruction, un traitement est exécuté au moins une fois puis
sa répétition se poursuit jusqu’à ce que la condition soit vérifiée.
Syntaxe:
Répéter
instruction(s) ;
Jusqu’à (condition) ;

Pr. F. Ben Bouazza 38

 Les instructions itératives (les boucles)

Exemple :
Soit l’algorithme suivant :
Var n, p : entier ;
Début
Le bloc de la boucle qu’il faut
Répéter
répéter jusqu’à ce que la condition
Ecrire ("Donner un nombre :") ; (n=0) soit vérifiée
Lire (n) ;
p ← n*n ; Ecrire (p);
Jusqu’à (n=0)
Ecrire ("Fin de l’algorithme") ; condition d’arrêt
Fin

Pr. F. Ben Bouazza 39

 Les instructions itératives (les boucles)

La notion du compteur
Un compteur est une variable associée à la boucle dont la valeur est
incrémentée de un à chaque itération. Elle sert à compter le nombre
d’itérations (répétitions) de la boucle.
Initialisation
du compteur

Pr. F. Ben Bouazza 40

 Les instructions itératives (les boucles)

La notion d’accumulation
Elle est utilisée notamment pour calculer la somme d’un ensemble de
valeurs. L’instruction correspondante se présente ainsi :
variable ← variable + valeur ;
Exemple : calcul de la somme de n valeurs données par l’utilisateur

Pr. F. Ben Bouazza 41

 Les instructions itératives (les boucles)

Les boucles imbriquées

Les boucles peuvent être imbriquées les unes dans les autres. Deux ou
plusieurs boucles imbriquées peuvent être aussi les mêmes ou
différentes.
Exemple : Boucle 2
Pour i de 1 à 2
Boucle 1
Écrire ("i = ", i) ;
Pour j de 1 à 3 boucle 1
Écrire ("j = ", j) ; boucle 2
Finpour
Finpour

Pr. F. Ben Bouazza 42

 Les tableaux

Un tableau est un ensemble de variables de même type ayant toutes le

même nom.
Comment peut-on différencier entre des variables ayant le même nom?
Chaque élément du tableau est repéré par un indice. Il s’agit d’un numéro
(généralement un entier) qui permet de différencier chaque élément du
tableau des autres.
Ainsi, les éléments du tableau ont tous le même nom, mais pas le même
indice. Pour accéder à un élément d’un tableau, on utilise le nom du
tableau suivi de l’indice de l’élément entre crochets.

Pr. F. Ben Bouazza 43

 Les tableaux

Exemple
Soit le tableau T contenant les valeurs suivantes : 5, 10, 29, 3, 18 et 14 :
L’organisation du tableau T dans la mémoire peut être représentée
comme suit :

Pr. F. Ben Bouazza 44

 Les tableaux

Tableaux à une seule dimension

Dans ce type de tableaux, chaque élément est accessible (pour lecture ou
modification) par un seul indice.
Déclaration
La syntaxe de déclaration d’un tableau à une seule dimension :
Tableau nom_du_tableau [taille] : type ;
Exemple :
Tableau Notes [100] : réel ;

Pr. F. Ben Bouazza 45

 Les tableaux

Tableaux à une seule dimension

ü Manipulation
Une fois déclaré, un tableau peut être manipulé comme un
ensemble de variables simples.
i. L’affectation
L’affectation d’une valeur v à un élément i d’un tableau T de type
numérique, se fait par : T[i] ← v ;
Exemple: T[0] ← 5 ; affecte la valeur 5 au premier élément du tableau T.

Pr. F. Ben Bouazza 46

 Les tableaux

Tableaux à une seule dimension

ü Manipulation
ii. La lecture
Il est possible aussi d’affecter des valeurs aux éléments d’un tableau par
une instruction de lecture.
Exemple :
Ecrire "Entrer une note :" ;
Lire T[0] ;

Pr. F. Ben Bouazza 47

 Les tableaux

Tableaux à une seule dimension

Application 1:
Ecrivons un algorithme qui permet de lire des valeurs saisies par
l’utilisateur dans un tableau de taille 20, et les afficher par la suite.

Pr. F. Ben Bouazza 48

 Les tableaux

Tableaux à une seule dimension

ü Manipulation
iii. L’écriture
L’écriture de la valeur d’un élément du tableau s’écrira comme suit :
Ecrire T[i] ;
Cette instruction permet d’afficher la valeur de l’élément i du tableau T.

Pr. F. Ben Bouazza 49

 Les tableaux

Tableaux à une seule dimension

ü Manipulation
Application 1:
Pour saisir les éléments d’un tableau T:
Pour i de 0 à n-1 // n est la taille de T
Ecrire ("Donner la valeur", i);
Lire T[i] ;
FinPour
Cette boucle permet de parcourir tout le tableau T en affectant à chaque
élément une valeur.

Pr. F. Ben Bouazza 50

 Les tableaux

Tableaux à deux dimensions

Les tableaux à deux dimensions se présentent sous forme d’un ensemble
de lignes et de colonnes (Matrice)
chaque élément est repéré par deux indices.
Exemple : le tableau T ci-dessous possède 3 lignes et 4 colonnes.

i : indice des lignes

j : indice des colonnes

T[2][1] (i=2 et j=1) désigne l’élément

de la 3ème ligne et la 2ème colonne

Pr. F. Ben Bouazza 51

 Les tableaux
Tableaux à deux dimensions
ü Déclaration d’un tableau à deux dimensions
i. Syntaxe :
Tableau nom_tableau [taille1][taille2] : type ;
Exemple : Tableau Notes [10][20] : réel ;

Pr. F. Ben Bouazza 52

 Les tableaux

Tableaux à deux dimensions

ü Manipulation d’un tableau à deux dimensions
Un tableau à deux dimensions est manipulé de la même façon qu’un
tableau simple (à une seule dimension) que ce soit pour l’affectation, la
lecture ou l’écriture.
Application 2
Reprenons l’algorithme précédent pour un tableau de 5 lignes et 20
colonnes.

Pr. F. Ben Bouazza 53

 Les tableaux

La recherche dans un tableau

ü La notion du drapeau
Le drapeau (ou flag en Anglais) est une variable booléenne initialisée à
Faux (drapeau baissé). Dès qu’un évènement attendu se produit, la
variable change de valeur à Vrai (drapeau levé).
è la valeur finale du drapeau permet de savoir si un évènement a eu lieu
ou pas.
Exemple: En supposant l’existence d’un tableau comportant N valeurs
entières. On doit écrire un algorithme qui lit un nombre donné et informe
l’utilisateur de la présence ou de l’absence de ce nombre dans le tableau.

Pr. F. Ben Bouazza 54

 Les tableaux

La recherche dans un tableau

ü La notion du drapeau
Tableau Tab[N] : entier ;
Var val, i : entier ;
existe : booléen ;
Début
Ecrire ("Entrez la valeur à rechercher ") ;
Lire (val) ;
existe ← faux ;
Pour i de 0 à N-1
Si (val = Tab[i]) Alors existe ← vrai; Finsi
Finpour
Si (existe) Alors Ecrire (val, "fait partie du tableau") ;
Sinon Ecrire (val, "ne fait pas partie du tableau") ;
Finsi
Fin

Pr. F. Ben Bouazza 55

 Les tableaux
Le tri d’un tableau
ü Tri par sélection
Cette technique consiste à sélectionner, pour une place donnée,
l’élément qui doit y être positionné.
Exemple 1 :
Soit à trier, en ordre croissant, le tableau suivant :

Pr. F. Ben Bouazza 56

 Les tableaux

Exemple 1:
Algorithmiquement, nous pouvons décrire ce processus de la manière
suivante :
Ø Boucle principale : prenant comme point de départ le premier
élément, puis le second, etc, jusqu’à l’avant dernier.
Ø Boucle secondaire : à partir de ce point de départ mouvant, nous
recherchons jusqu’à la fin du tableau le plus petit élément. Une fois
trouvé, nous l’échangeons avec le point de départ.

Pr. F. Ben Bouazza 57

 Les tableaux

Exemple 1:
Pour i de 0 à 6 /* boucle principale : le point de départ se décale à chaque tour */
posmin ← i ; /* on considère provisoirement que T(i) est le plus petit élément et posmin est la position du
minimum initialisée par i*/
Pour j de (i + 1) à 7 /* on examine tous les éléments suivants */
Si (T(j) < T(posmin)) Alors posmin ← j ;
Finsi
Finpour
/* on sait maintenant où est le plus petit élément. Il ne reste plus qu'à effectuer la permutation*/
temp ← T(posmin) ;
T(posmin) ← T(i) ;
T(i) ← temp ;
/* On a placé correctement l'élément numéro i, on passe à présent au suivant */
FinPour
Pr. F. Ben Bouazza 58
 Les tableaux

Le tri d’un tableau

ü Tri par insertion
Soit à trier un tableau d’éléments en ordre croissant.
Le principe de ce type de tri repose à chaque itération sur trois phases:
• On prend le premier élément dans la partie non encore triée du
tableau (la clé).
• On cherche la place de la clé dans la partie déjà triée du tableau, en
commençant par la droite de cette partie.
• Une fois cette place trouvée, on y insère la clé après qu’on ait décalé
vers la droite tous les éléments de la partie triée dont la valeur est plus
grande ou égale à la valeur de la clé.

Pr. F. Ben Bouazza 59

 Les tableaux

Le tri d’un tableau

ü Tri par insertion
Exemple:

Pr. F. Ben Bouazza 60

 Les tableaux
Le tri d’un tableau
ü Tri par insertion
Algorithme Tri_Insertion ;
Var i, j, n, clé : Entier; // n est la taille du tableauT
Tableau T[n] : Entier ;
Début
Pour i de 1 à n-1 // on commence par le 2ème élément (début de la partie
non triée)
clé ← T[i] ;
j ← i - 1 ; // indice du 1er élément à droite de la partie triée
Tant que ((j >= 0) ET (clé < T[j])) Faire
T[j +1] ← T[j]; // Décalage
j ← j - 1;
FinTant que
T[j +1] ← clé; // Insertion de la clé
FinPour
Fin

Pr. F. Ben Bouazza 61

 Les tableaux

Le tri d’un tableau

Tri par sélection: Dans tous les cas, la boucle interne est exécuté pour
i=1, 2, 3 jusqu’à i=(n-1) (n-1) + (n-2) + (n-3) + …+ 1 étant n (n-1) / 2
exécutions.
Tri par insertion: Dans le pire des cas un tableau trié à l’envers (en
ordre décroissant dans ce cas), et la boucle interne est exécuté (n-1) +
(n-2) + (n-3) + … + 1 fois, étant n (n-1) / 2 exécutions au maximum. Au
meilleur des cas, le tableau est trié en ordre voulu (croissant dans ce
cas) et la boucle interne ne s’exécutera jamais En moyenne, le
nombre d’exécutions est n (n-1) / 4.

Pr. F. Ben Bouazza 62

 Les enregistrements (structures)

Les tableaux nous permettent de stocker plusieurs éléments de même type

(les notes) dans un tableau de type réel.
Supposons maintenant qu’en plus des notes des étudiants, nous voulons
stocker aussi leurs informations (nom, prénom, matricule, …)?
Une structure qui permet de stocker des données de différents types.

Pr. F. Ben Bouazza 63

 Les enregistrements (structures)

Définition
Un enregistrement (ou structure) permet de regrouper un ensemble de
données de différents types sous le même nom (un seul objet). Il est défini
par un ensemble d’éléments appelés champs qui peuvent être de types
différents.
Déclaration et manipulation
Structure nom_structure //défini par l’utilisateur
champ1 : type1 ;
champ2 : type2 ; les variables membres
... de la structure déclarée
champN : typeN ;
FinStructure ;

Pr. F. Ben Bouazza 64

 Les enregistrements (structures)

Exemple :
Structure Etudiant Les variables de type Etudiant peuvent être déclarées
num : entier ; comme suit :
nom : chaîne ;
moyenne : réel; Var x,y : Structure Etudiant ; /* Deux variables
FinStructure ; structures x et y de type Etudiant */
§ La manipulation d’une variable structure se fait par champ (membre);
§ L’accès à une information contenue dans un champ se fait en précisant
le nom de la variable structure suivie du champ concerné, séparés par
un point.
x.num ←123 ; // affecte le nombre 123 au champ num
Lire (x.nom) ; // lire le champ nom
x.moyenne ←13.5 ; // affecte le nombre 13.5 au champ moyenne

Pr. F. Ben Bouazza 65

 Les enregistrements (structures)

Tableau de structures
Il est possible de déclarer un tableau dont les éléments sont des
structures :
Tableau nom_tableau [taille] : Structure nom_structure ;
Exemple :
Tableau T[10] : Structure Etudiant ;
Donc, T est un tableau de 10 éléments de type structure (« Etudiant »
dans ce cas).
L'accès à un champ d’élément i d’un tableau de structure se fait comme
suit :
nom_tableau [i].champ

Pr. F. Ben Bouazza 66

 Les enregistrements (structures)

Tableau de structures Structure Etudiant

Exemple : Tableau T[10] : Structure Etudiant ; num : entier ;
les instructions : nom : chaîne ;
T[0].nom ← "Mohamed" ; moyenne : réel;
T[0].num ← 1 ; et FinStructure ;
T[0].moyenne ← 12.5 ;
Affectent les contenues des trois champs du 1er élément du tableau T.

De même, les instructions :

Ecrire (T[0].num) ;
Ecrire (T[0].nom) ;
Ecrire (T[0]. moyenne) ;
Affichent les contenues des trois champs du 1er élément du tableau T.

Pr. F. Ben Bouazza 67

 Les enregistrements (structures)

Structure membre d’une autre structure

Une structure peut figurer parmi les champs d'une autre structure (elle doit
obligatoirement être déclarée avant la structure qui la contient).
Exemple :
Structure Compte
Ncpt: entier;
nom: chaine ; Structure Date
DtOuverture : Date ; jour, mois, annee : entier ;
Finstructure ; Finstructure ;

Où « DtOuverture » est une variable structure de type « Date », champ de la

structure «Compte ».

Pr. F. Ben Bouazza 68

 Les enregistrements (structures)
Structure membre d’une autre structure
Lorsqu'un champ d'une structure est lui-même une structure, l’accès à
ce champ se fait
comme suit :
variable_structure.variable_sous_structure.champ
Par exemple :
c.DtOuverture.annee ← 2019 ; affecte la valeur 2019 au champ année
de l’enregistrement « DtOuverture » qui est lui-même un champ de
l’enregistrement « c ». Tel que « c » est une variable de type « Compte
». Structure Compte
Ncpt: entier; Structure Date
nom: chaine ; jour, mois, annee : entier ;
DtOuverture : Date ; Finstructure ;
Finstructure ;
Pr. F. Ben Bouazza 69
 Les enregistrements (structures)

Structure membre d’une autre structure

Dans le cas d'un tableau, l'accès se fait comme suit :
nom_tableau[indice].variable_sous_structure.champ
Par exemple : T[i].DtOuverture.annee ← 2019 ;
Où T[i] fait référence au ième élément du tableau T de type « Compte
». Structure Compte Structure Date
Ncpt: entier; jour, mois, annee : entier ;
nom: chaine ; Finstructure ;
DtOuverture : Date ;
Finstructure ;

Pr. F. Ben Bouazza 70

 Les enregistrements (structures)

Structure membre d’une autre structure

Dans le cas d'un tableau, l'accès se fait comme suit :
nom_tableau[indice].variable_sous_structure.champ
Par exemple : T[i].DtOuverture.annee ← 2019 ;
Où T[i] fait référence au ième élément du tableau T de type « Compte
». Structure Compte Structure Date
Ncpt: entier; jour, mois, annee : entier ;
nom: chaine ; Finstructure ;
DtOuverture : Date ;
Finstructure ;

Pr. F. Ben Bouazza 71

 Les fonctions et les procédures

1. Introduction
La fiabilité, la lisibilité et la réutilisabilité des programmes, reposent sur
l’utilisation des sous-programmes:
§ La réduction de la taille des programmes : il est possible de déterminer
les blocs analogues, les substituer par un sous-programme, ensuite
l’appeler dans des points déterminés au niveau du programme principal.
§ L’organisation du code : le problème initial peut être découpé en sous-
problèmes (modules) où chacun sera résolu par un sous-programme.

Pr. F. Ben Bouazza 72

 Les fonctions et les procédures

2. La notion de sous-programme

Un sous-programme, est une portion de code (programme), destiné à

réaliser une certaine tâche à l’intérieur d’un autre programme.

Il est identifié par un nom unique et un bloc d’instructions qui peut être
exécuté plusieurs fois par des appels.

Un appel est une instruction qui fait partie d’un autre programme (le
programme appelant).

Pr. F. Ben Bouazza 73

 Les fonctions et les procédures

2. La notion de sous-programme

Un sous-programme est utilisé :

• Lorsqu’une tâche est répétée plusieurs fois : éviter de réécrire le

même code à plusieurs endroits dans le même programme.

• Pour réaliser la structuration d’un problème en sous-problèmes :

diviser le problème en sous-problèmes pour mieux le contrôler.

Pr. F. Ben Bouazza 74

 Les fonctions et les procédures

2.1 La portée d’une variable

Il est possible d'avoir deux variables différentes avec le même nom toutefois qu'elles ont
des portées différentes: une variable définie au niveau du programme principal est
appelée variable globale et sa portée est totale.
è Tout sous-programme du programme principal peut utiliser cette variable: variable
locale dont la portée est limitée au sous-programme dans lequel elle est déclarée.
Remarque :
Si l’identificateur (le nom) d'une variable locale est identique à celui d’une variable
globale, cette dernière est localement masquée. Autrement dit, la variable globale
devient inaccessible dans le sous-programme contenant la variable locale de même nom.

Pr. F. Ben Bouazza 75

 Les fonctions et les procédures
2.1. La portée d’une variable
Algorithme Principal ;
Var x, y : entier ; // variables globales
Début
x←5;y←8;
… ; // Appel au sous-programme Secondaire
Ecrire (x, y) ;
Fin

Sous-programme: Sous-programme Secondaire ;

Var x : entier ; // variable locale
Début
x←3;
Ecrire (x, y) ;
Fin L’exécution de ce
programme

Pr. F. Ben Bouazza 76

 Les fonctions et les procédures

2.2. Les paramètres

Les paramètres d'un sous-programme sont un ensemble de variables
locales (paramètres formels) associées à un ensemble de variables ou
constantes du programme appelant (paramètres effectifs).
Remarque :
- Un paramètre est une variable locale, donc il admet un type.
- L’appel d’un sous-programme possédant un ou plusieurs paramètres,
implique une association entre ces paramètres et les paramètres effectifs
du programme appelant, respectivement de même type.

Pr. F. Ben Bouazza 77

 Les fonctions et les procédures

2.3. Le passage de paramètres

L'association entre les paramètres effectifs et les paramètres formels est
appelé passage de paramètres. Il existe deux types de passage de
paramètres :
- Le passage par valeur: La valeur du paramètre effectif est affectée
(copiée) au paramètre formel correspondant. Sachant que les paramètres
formels ne sont que des variables locales du sous-programme.
- Le passage par référence (ou adresse): L’adresse du paramètre effectif qui
est affectée au paramètre formel correspondant. Ceci rend possible au
sous-programme d’accéder directement à l’adresse de la variable concernée
(le paramètre effectif) et par conséquent la modifier si nécessaire. Ce type
de passage nécessite d’utiliser la notion des pointeurs.

Pr. F. Ben Bouazza 78

 Les fonctions et les procédures
3. Les fonctions
Une fonction est une suite d’instructions (sous-programme)
regroupées sous un nom; elle prend en entrée des paramètres
(arguments) et retourne un résultat. Une fonction admet un type et
retourne toujours un résultat.
3.1. Définition (déclaration) d’une fonction:
Fonction nom_fonction (paramètres : types) : type de la valeur retournée
Var var1, var2,…: types; // variables_locales • Les paramètres sont en nombre fixe (n≥0)
Début • Le type de la valeur retournée est le type de la
instructions de la fonction ; fonction.
Retourner (résultat) ; // (au moins une fois) • La valeur de retour (ou le résultat) est spécifiée
Fin par l'instruction Retourner.
Pr. F. Ben Bouazza 79
 Les fonctions et les procédures

3. Les fonctions
3.2. Appel d’une fonction:
On fait appel à une fonction comme suit :
var ← nom_fonction (paramètres) ;
Où les paramètres d’appel peuvent être des variables, des constantes ou
même des résultats d’une autre fonction.
Remarque :
A la définition ou à l’appel d’une fonction, les parenthèses sont toujours
présentes même lorsqu'il n'y a pas de paramètres.

Pr. F. Ben Bouazza 80

 Les fonctions et les procédures
3. Les fonctions
Exemple 1 :
Soit l’algorithme A qui calcule la Si (n >= 0) alors valabs ← n ;
Sinon valabs ← -n ;
valeur absolue d’un nombre en FinSi
utilisant une fonction : Retourner valabs ;
Algorithme A ; Fin
Var a: reel;
b : entier ; Début /* Algorithme principal */
Fonction Abs (n : reel) : entier /* Définition de la fonction */ Ecrire (" Donner une valeur ") ;
Var valabs : entier; Lire (a) ;
Début b ← Abs(a) ;
Ecrire (b) ;
Passage de paramètre par valeur : la valeur Fin
de la variable a est copiée dans la variable n.
Pr. F. Ben Bouazza 81
 Les fonctions et les procédures

4. Les procédures
Une procédure est un sous-programme qui admet également un nom
et des paramètres mais ne retournant aucun résultat.
4.1. Définition d’une procédure:
Procédure nom_procédure (paramètres : types)
Var var1, var2,…: types; // variables_locales
Début
instructions de la procédure ;
Fin

Pr. F. Ben Bouazza 82

 Les fonctions et les procédures

4. Les procédures
4.2. Appel d’une procédure: L’appel d’une procédure se fait comme
suit :
Algorithme B ;
Var a : entier ;
Procédure Abs (n : entier) /* Définition de la procédure nom_procédure (paramètres) ;
*/ Début /* Algorithme principal */
Début Ecrire (" Donner une valeur ") ;
Si (n >= 0) alors Lire (a) ;
Ecrire n ; Abs(a) ;
Sinon Fin
Ecrire -n ;
FinSi
Fin

Pr. F. Ben Bouazza 83

 Les fonctions et les procédures

5. Fonctions et procédures récursives

La récursivité est une méthode de description d’algorithmes qui
permet à une fonction (ou procédure) de s’appeler elle-même
directement ou indirectement..
5.1. Exemple:
On peut définir la factorielle d’un nombre N non négatif de deux
manières :
Définition non récursive (itératif) : N ! = N * N-1 * …* 2 * 1
Définition récursive : N ! = N * (N – 1) ! et 0 ! = 1

Pr. F. Ben Bouazza 84

 Les fonctions et les procédures
5. Fonctions et procédures récursives
5.1. Exemple: calcul de la factorielle
a) Solution itérative : b) Solution récursive :
Fonction FACT ( n : entier ) : entier
Var i, F: entier ; Fonction FACT ( n : entier ) : entier
Début Début
Si (n = 0) alors F ← 1 ; Si (n=0) alors Retourner 1 ;
Sinon Sinon Retourner n * FACT (n-1) ; //
F←1; Appel récursif de la fonction FACT
Pour i de 2 à n Finsi
F ← F * i; Fin
Finpour
Retourner F;
Finsi
Fin
Pr. F. Ben Bouazza 85
 Les fonctions et les procédures

5. Fonctions et procédures récursives

5.2. Interprétation
• Une procédure ou une fonction récursive Fonction FACT ( n : entier ) : entier
Début
doit comporter une condition d’arrêt qui Si (n=0) alors Retourner 1 ;
Sinon Retourner n * FACT (n-1) ; //
empêche des appels récursifs sans arrêt. Appel récursif de la fonction FACT
Finsi
• Le paramètre de l’appel récursif doit Fin

converger toujours vers la condition

d’arrêt.

Pr. F. Ben Bouazza 86