CH 3 Algorithm e
Transféré par
Sanz GuéCH 3 Algorithm e
Transféré par
Sanz GuéLangage Algorithmique
Konan Marcellin BROU
[email protected]
2021-2022
Sommaire
Etapes de résolution d’un
problème
Concepts de base du langage
Structure d’un algorithme
Les sous-algorithmes
Les structures de données
Le langage C
Bibliographie
INP-HB/DFRMI/K. M. BROU Langage algorithmique 2
2
Sommaire
Objectifs
Connaitre les concepts de base du
langage algorithmique
Savoir écrire un algorithme
Savoir écrire un programme
INP-HB/DFRMI/K. M. BROU Langage algorithmique 3
I. Les étapes de la programmation
1.1. Eres de la programmation Langage Machine
En binaire (base 2)
1950-1960 : L’âge du Chaos
000100111011000101001010101010
Langage machine et Assembleur 010000101010101010101010101010
Temps de programmation En hexadécimal (base 16)
considérable et programmes peu
41 30 C1 A4
fiables. 3A 20 C1 A8
Exemple : A B + C x D 1A 30 C1 A0
50 30 C2 A4
Langage Assembleur
LDA C
MUL D
ADD B
STO A
Avantage : rapidité d’exécution
INP-HB/DFRMI/K. M. BROU Langage algorithmique 4
4
I. Les étapes de la programmation
1973-1980 : L’âge de la structure 1990 et +: L’âge des objets
Langage évolué ou structuré LO ou LOO
Temps de programmation Baisse du temps de
considérable et problème de programmation et réutilisation de
réutilisation. logiciels.
Langages : Pascal, Fortran, Langages C++, Java, Python
python, C Exemple : A B + C x D
Exemple : A B + C x D En C++
En C class Calcul {
int void main() { private int A, B, C, D;
int A, B, C, D; int void main() {
scanf("%d%d%d",&B,&C,&D); scanf("%d%d%d",&B,&C,&D);
A=B+C*D A=B+C*D
printf("%d",A) printf("%d",A)
} }
}
Avantage : maintenance aisée
INP-HB/DFRMI/K. M. BROU Langage algorithmique 5
I. Les étapes de la programmation
1.2. Programmation Qu’est-ce qu’un algorithme ?
Production d’un programme Terme d’origine arabe
But essentiel dans la résolution Suite finie d’opérations
d’un problème en informatique. élémentaires, dont le
Partie la plus importante = déroulement dans un ordre prévu
Analyse à l’avance, résout, en un temps
fini, une classe donnée de
L’analyse consiste à concevoir et à problèmes, i.e. fait passer d’un
écrire un algorithme correct. ensemble de données à un
ensemble de résultats.
Analyse Codage
Problème
à Algorithme Programme
résoudre
Une fois l’algorithme mis au point,
il faut le coder dans le langage de
programmation choisi, pour
obtenir le programme demandé.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 6
6
I. Les étapes de la programmation
Exemple d’algorithme
Soient un point d’eau et de 2
bidons : B de 5 litres et b de 3
litres.
On voudrait obtenir exactement 4
litres d’eau dans le bidon B.
Opérations permises :
1. Remplir un bidon : RB
2. Vider un bidon : VB
3. Transvaser le contenu d’un bidon
à un autre (arrêt quand un bidon
est vide ou l’autre plein) : TB.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 7
I. Les étapes de la programmation
Résolution La Solution 2 comporte moins
d’opérations, donc s’exécutera
beaucoup plus rapidement que la
Solution 1.
Un bon algorithme doit minimiser
au maximum le nombre
d’opérations à effectuer.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 8
8
I. Les étapes de la programmation
Exercice Présenter le résultat sous la
Soient un point d’eau et de 3 forme suivante
bidons : B2 de 3 litres, B3 de 7
Solution 1 :
litres et B7 de 10 litres.
N° Opérations (B, b)
On voudrait obtenir exactement 5 1
litres d’eau. 2
Opérations permises : 3
4
1. Remplir un bidon 5
2. Vider un bidon 6
3. Transvaser le contenu d’un bidon à 7
8
un autre (arrêt quand un bidon est
vide ou l’autre plein).
INP-HB/DFRMI/K. M. BROU Langage algorithmique 9
I. Les étapes de la programmation
Qu’est-ce que programmer ? Langage de programmation :
C’est un code de communication,
Programmer c’est donner à
permettant à un être humain
l’ordinateur une liste d’action à
(programmeur) de dialoguer avec
effectuer ou un schéma de
une machine en lui soumettant
traitement pour résoudre un
des instructions et en analysant
problème donné.
les données matérielles fournies
Programmation : processus de par l’ordinateur.
réalisation d’un programme.
Constitué d’un vocabulaire et de
Programme ou logiciel : suite règles syntaxiques servant à
d’actions que doit effectuer exprimer les algorithmes dans
l’ordinateur pour obtenir un une forme exploitable par
ensemble de résultats à partir l’ordinateur (le programme).
d’informations initiales.
Langages C, Fortran, Java, Visual
Basic, Python
INP-HB/DFRMI/K. M. BROU Langage algorithmique 10
10
I. Les étapes de la programmation
Etape 2 : Recherche d’un
1.3. Résolution d’un problème
algorithme
en 4 étapes : Rechercher une méthode de
Etape 1 : Etude solution
Il faut formuler le problème à Traduire cette méthode en une
résoudre en des termes clairs et suite d’actions à effectuer pour
précis (pas d’ambiguïté). résoudre le problème :
Exemple : Rechercher le maximum on obtient un algorithme.
de 3 nombres entier a, b, c. A un problème donné peut
correspondre plusieurs
algorithmes.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 11
11
I. Les étapes de la programmation
Un algorithme est une suite finie Solution 1
a>b ?
d’instructions, dont le faux vrai
déroulement dans un ordre prévu
à l’avance, résout, en un temps b>c ? a>c ?
fini, une classe donnée de faux vrai faux vrai
problèmes.
max = c max = b max = c max = a
A un problème donné peut
correspondre plusieurs algos.
Exemple : Solution 2
Recherche du maximum de 3 a>b ?
faux vrai
nombres entiers.
Solution 1 : 3 comparaisons max=b max=a
c>max ?
Solution 2 : 2 comparaisons faux vrai
max reste max = c
inchangé
INP-HB/DFRMI/K. M. BROU Langage algorithmique 12
12
I. Les étapes de la programmation
ALGORITHME maximum1 ALGORITHME maximum2
VAR a, b, c, max : ENTIER VAR a,b,c, max : ENTIER
DEBUT DEBUT
ECRIRE('Entrer 3 nombres entiers : ‘’) ECRIRE('Entrer 3 nombres entiers : ')
LIRE(a, b, c) LIRE(a, b, c)
SI(a > b) ALORS SI(a > b) ALORS
SI(a > c) ALORS max a
max a SINON
SINON max b
max c SI(c > max) ALORS
SINON SI (b > c) ALORS max c
max b ECRIRE('Maximun de', a, b, c, ' = ', max)
SINON FIN
max c
ECRIRE('Maximun de', a, b, c, ' = ', max)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 13
13
I. Les étapes de la programmation
1.4. Étape 3 : Programmation #include <stdio.h>
Traduire l’algorithme dans un
langage de programmation. void main() /*programme maximun2*/
{int a,b,c, max ;
C’est-à-dire un langage
printf("Entrer 3 nombres entiers : ");
compréhensible par la machine. scanf("%d%d%d", &a, &b, &c);
On obtient un programme. max = a > b ? a : b;
Exemple : algorithme maximum2 if(c > max)
en langage C (maxi.c). max = c ;
printf("Maximun de %d %d %d = %d\n", a, b, c, max);
}
INP-HB/DFRMI/K. M. BROU Langage algorithmique 14
14
I. Les étapes de la programmation
1.5. Etape 4 : Mise au point Compilateur :
Saisir le programme puis le faire Logiciel de traduction qui traduit
exécuter plusieurs fois avec des globalement les textes sources
données différentes. (en langage source) en langage
machine (souvent binaire
Permet de vérifier qu'il résout bien
exécutable par la machine).
le problème posé.
Exemple : C/C++, …
Tout code écrit dans un langage
de programmation doit être Avantage : Rapidité
traduit pour être compris par la Inconvénient : Pas de portabilité
machine.
C’est le rôle des compilateurs et
interpréteurs .
Code source Code en
du Traducteur langage
Programme machine
INP-HB/DFRMI/K. M. BROU Langage algorithmique 15
15
I. Les étapes de la programmation
Algorithme
Interpréteur : Programme
Logiciel identique au compilateur
Saisie
mais la traduction s’effectue ligne
d’instruction par ligne Messages
Programmes sources
d’instruction. d’erreurs
Exemple : maxi.c
Exemple : VBA, Python, …
non Bibliothèque
Avantage : Portabilité des Compilation ok ? Autres code
applications oui Programmes objets objets (.obj)
Exemple : maxi.obj
Inconvénient : Lenteur
Langage pseudo-compilé oui
non
Programme à la fois compilé puis Edition de liens ok ?
interprété. oui Fichier exécutable
(Ex. : maxi.exe)
Exemple : Java, Python, …
Avantage : Portabilité, multi Données
non
plates-formes (Windows, Unix) Exécution ok ?
oui
Inconvénient : Lenteur
INP-HB/DFRMI/K. M. BROU Langage algorithmique Résultats 16
16
I. Les étapes de la programmation
1.6. TP : éditeur de Dev C++ Faire l’édition de lien : Menu
Execute/Run
Créer un dossier de travail
Exécuter le programme
Lancer Dev C++
Vérifier les fichiers générés
Menu File/New/Source File
maxi.c, maxi.obj, maxi.exe
Saisir le programme maximum
Le sauvegarder sous le nom
maxi.c dans le dossier de travail
Faire la compilation : Menu
Execute/Compile
Corriger les erreurs éventuelles
INP-HB/DFRMI/K. M. BROU Langage algorithmique 17
17
II. Concepts de base du langage
2.1 Présentation Concis : doit tenir en une page ;
Pour écrire un algorithme, il faut Modulaire : découpage en sous-
algorithme
un langage algorithmique
constitué d’un vocabulaire et de Typé : numérique, chaîne de
caractères…
règles syntaxiques.
Ce langage doit être :
Spécialisé : pour écrire des
algorithmes
pas des poèmes ni des recettes de
cuisine ;
De haut niveau : déchargé de
détails techniques
Pas un langage de
programmation ;
INP-HB/DFRMI/K. M. BROU Langage algorithmique 18
18
II. Concepts de base du langage
2.2 Qualités d’un algorithme Validité ou justesse:
Qualité d'écriture : Le résultat doit répondre au
problème posé.
Il doit être structuré, indenté,
modulaire, avec des Remarque : un jeu d'essais ne
commentaires pertinents, etc. prouve jamais qu'un programme
est correct.
Il doit être lisible et maintenable ;
Il peut seulement prouver qu'il est
Terminaison : faux ;
Le résultat doit être atteint en un
Performance :
nombre fini d'étapes,
Etude du coût (complexité) en
Il ne faut donc pas de boucles
temps et en mémoire.
infinies,
Coût le plus faible possible
Il faut étudier tous les cas
possibles de données, ... ;
INP-HB/DFRMI/K. M. BROU Langage algorithmique 19
19
II. Concepts de base du langage
2.3 L’alphabet du langage
Constitué de caractères
utilisables dans l’écriture d’un
algorithme :
les lettres de l’alphabet : a - z ou
A- Z;
les chiffres : 0 - 9 ;
les caractères spéciaux : #, $, ;.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 20
20
II. Concepts de base du langage
2.4 Codage de l’information Le langage de l’ordinateur :
Le langage humain : Ordinateur : machine électronique
ayant un alphabet limité.
Permet aux hommes de
communiquer entre eux. Il ne peut distinguer que deux
états :
Comporte beaucoup de symboles
(cf. alphabet du langage) le courant passe (1) , le courant le
courant ne passe pas (0).
Bit (BInary digiT) :
plus petite information manipulée
par un ordinateur
INP-HB/DFRMI/K. M. BROU Langage algorithmique 21
21
II. Concepts de base du langage
Chaque symbole de l’alphabet
humain est représenté par un
codes qui pourra être converti en
bit.
Le code ASCII :
Code sur 8 bits (256 symboles ).
Prend en compte les caractères
graphiques et les lettres
accentués ou non.
Lecture du tableau
A : code
= 41 en hexadécimal
= 65 en décimal
= 01000001 en binaire
INP-HB/DFRMI/K. M. BROU Langage algorithmique 22
22
II. Concepts de base du langage
Le code étendu (en hexa)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 23
23
II. Concepts de base du langage
Le code Vidéotex : Code à 7 bits, se compose de 127
Procédé de télécommunication caractères alphanumérique,
permettant à un usager de graphique et de contrôle répartis
recevoir des messages sur un en deux tables :
écran vidéo de type MINITEL. G0 : permet de coder les chiffres
Il utilise la norme française et les lettres comme en ASCII
TELETEL. standard
G2 : permet de coder les accents
et quelques symboles particuliers.
G1 : permet de coder les
caractères alphamosaïques qui
servent à faire de dessins à
l’écran.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 24
24
II. Concepts de base du langage
Le code ANSI (American National Le code EBCDIC
Standard Institute) Extended Binary Coded Decimal
Code utilisé par le système Interchange Code
d’exploitation Windows ; Utilisé principal par IBM, code 8
Il reprend en grande partie le bits ou 9 bits (1 bit d’imparité).
code ASCII, et propose des Le code UNICODE
extensions différentes selon le Utilisé par Windows 95 et +.
code de page.
Code universel codé sur 16 bits.
Code page 850 :jeu de caractères
But : coder le plus grand nombre
multilingues
possible de symbole en usage
Code page 864 :jeu de caractères dans le monde.
arabe
Permet de coder 65535 caractères
Code page 865 :jeu de caractères différents.
nordique
INP-HB/DFRMI/K. M. BROU Langage algorithmique 25
25
II. Concepts de base du langage
Exercice 1 :
Un fichier contient les
informations suivantes :
4C 65 20 42 54 53 20 65 6E 20 55 43
41 50 20 65 73 74 20 75 6E 65 20 22
65 78 63 65 6C 6C 65 6E 74 65 22 20
46 6F 72 60 61 74 69 69 6F 6E 2E 22
Convertissez ces codes en ASCII.
Exercice 2 :
Coder le texte suivant en
hexadécimal :
Technologie 1989 "Leçon sur
les codes"
INP-HB/DFRMI/K. M. BROU Langage algorithmique 26
26
II. Concepts de base du langage
Réponse Exercice 1
Réponse Exercice 2
INP-HB/DFRMI/K. M. BROU Langage algorithmique 27
27
II. Concepts de base du langage
2.5. Les opérateurs Opérateurs relationnels :
Opérateurs arithmétiques : Opérateur Symbole
Egalité =
Opérateur Symbole
Différence
Addition +
Infériorité stricte <
Soustraction -
Infériorité large
Multiplication *
Supériorité stricte >
Division entière //
Supériorité large
Division réelle /
Modulo % Opérateurs de manipulation de
chaînes de caractères :
Opérateurs logiques
Opérateur Symbole Opérateur Symbole
Et ET Concaténation &
Ou OU +
Négation NON
INP-HB/DFRMI/K. M. BROU Langage algorithmique 28
28
II. Concepts de base du langage
2.6 Les identificateurs Il doit être expressif, i.e., choisi
Mots choisis par le concepteur de de telle sorte qu’il désigne bien
l’algorithme pour représenter les l’objet qu’il représente.
objets de l’algorithme : Exemple : prixTTC, valeurMax,
deuxPI, _2PI
nom de l’algorithme, nom de
variable, … Contre exemple : 2PI
Constitué d’une suite de Il n’y a pas de distinction entre
caractères alphanumériques minuscule et majuscule.
Le premier caractère est PrixTTC, PRIXTTC, prixttc
désignent le même objet.
obligatoirement une lettre de
l’alphabet ou le caractère de
soulignement.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 29
29
II. Concepts de base du langage
2.7. Les mots réservés Remarque :
Identificateurs prédéfinis du Par convention, les mots réservés
langage algorithmique. seront écrits en majuscules ainsi
que le premier caractère des
Ils ne doivent pas être utilisés
constantes.
comme identificateur dans un
algorithme.
Exemples :
ALGORITHME, FONCTION,
TANTQUE, POUR
INP-HB/DFRMI/K. M. BROU Langage algorithmique 30
30
II. Concepts de base du langage
2.8. Les nombres
Deux types de nombre : les
entiers et les réels.
Exemples :
125 : entier
3.1459 : réel
15 E-3 (réels, notation
scientifique).
INP-HB/DFRMI/K. M. BROU Langage algorithmique 31
31
II. Concepts de base du langage
2.9. Les commentaires
Inséré dans un algorithme afin de
faciliter sa lecture et sa
maintenance.
Exemple :
(* prixTTC désigne le prix Toute
Taxe Comprise *)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 32
32
II. Concepts de base du langage
CONST N = 2 (* objets globaux *)
2.10. Structure d’un
algorithme FONCTION max(D x, y, z :ENTIER) :ENTIER
VAR m: ENTIER
Un algorithme comprend 5 DEBUT
SI (x > y) ALORS
parties : mx
1. Déclaration d’objets globaux SINON
my
(facultatif) SI (z > m) ALORS
2. Déclaration de sous-algorithme mz
(facultatif) max m
FIN
3. Tête de l’algorithme
ALGORITHME maximum
4. Déclaration des objets VAR a, b, c, m : ENTIER
(facultatif) DEBUT
ECRIRE('Entrer 3 nb entiers :' )
5. Corps de l’algorithme : contient
LIRE(a,b,c)
les instructions exécutables m max(a,b,c)
ECRIRE(‘Maximum = ', m)
Exemple : Calcul du maximum de ECRIRE('N =', N)
trois nombres FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 33
33
II. Concepts de base du langage
Tête de l’algorithme Tout objet manipulé par
Il s’agit de donner un nom à l’algorithme doit être déclaré
l’algorithme précédé du mot avant son utilisation dans le corps
réservé ALGORITHME. de l’algorithme.
Ce nom doit avoir une relation Les différents objets sont : les
avec le but de l’algorithme constantes, les types, et les
Exemple : variables.
ALGORITHME maximum
INP-HB/DFRMI/K. M. BROU Langage algorithmique 34
34
III. Partie déclaration
3.1. Déclaration de constante Exemple :
Espace mémoire représenté par ALGORITHME declareConst
un identificateur et utilisé pour CONST Pi = 3.1459
désigner une valeur fixe d’un NbreMois = 12
ensemble donné. Ecole = 'INP-HB'
Omega = 100 * Pi
Cette valeur reste inchangée tout DEBUT
au long de l’exécution de FIN
l’algorithme.
Syntaxe :
CONST identificateur = expression
INP-HB/DFRMI/K. M. BROU Langage algorithmique 35
35
III. Partie déclaration
3.2. Déclaration de type Hiérarchie des types
Un type est constitué par un Type
ensemble de valeurs et par des
opérateurs définis sur cet
ensemble. Simple Structuré Pointeur
Syntaxe :
TYPE identificateur = nom du type Standard Manufacturé Statique Dynamique
- CAR - Intervalle - Tableau - Pile
Exemple : - TEXTE - Enuméré - Enregistrement - File
- BOOLEEN - Liste
ALGORITHME declareType
- ENTIER - Ensemble
CONST N = 3
- REEL - Fichier
TYPE Vecteur = TABLEAU[1..N] DE REEL
DEBUT
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 36
36
III. Partie déclaration
3.3. Les types simples Type caractère (CAR)
Type entier (ENTIER) Ensemble de la table ASCII.
Ensemble des entiers relatifs. Une constante caractère est
délimitée par de simples ou
Opérateurs : opérateurs
double quotes.
arithmétiques et relationnels
Opérateurs : opérateurs de
Type réel (REEL) concaténation et relationnels
Ensemble des nombres réels. Il existe une relation d’ordre dans
Opérateurs : opérateurs la table ASCII.
arithmétiques et relationnels Exemple :
sauf les opérateurs // et %. 'a' < 'b' < 'c' < … 'z'
'a' + 'b' + 'c' donne la chaîne de
caractères 'abc'
INP-HB/DFRMI/K. M. BROU Langage algorithmique 37
37
III. Partie déclaration
Type chaîne de caractères Type booléen (BOOLEEN)
(TEXTE) Ensemble constitué des deux
Ensemble des chaînes de valeurs VRAI et FAUX.
caractères délimitées par de Opérateurs sont les opérateurs
simples ou double quotes. logiques.
Opérateurs : opérateurs de Exemple : table de vérité
concaténation et relationnels.
Exemple : A B A ET B A OU B NON A
VRAI VRAI VRAI VRAI FAUX
'omega' < 'valeur'
VRAI FAUX FAUX VRAI FAUX
"omega" < "valeur" FAUX VRAI FAUX VRAI VRAI
'informatique' > 'Informatique' > FAUX FAUX FAUX FAUX VRAI
'Information'
'INP-' + 'HB' donne la chaîne de
caractères 'INP-HB'
INP-HB/DFRMI/K. M. BROU Langage algorithmique 38
38
III. Partie déclaration
3.4. Les types manufacturés Deux sortes :
Types construits par le Type énuméré
concepteur de l’algorithme. Type intervalle.
Intérêt
définir de façon très précise le
champ de validité des objets
utilisés.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 39
39
III. Partie déclaration
Type énuméré Opérateurs : opérateurs
Ensemble constitué par relationnels.
l’énumération des constantes Exemple :
symboliques. Orange < Vert < Rouge
Syntaxe :
TYPE
identificateur = (valeur1, valeur2, …, valeurn)
Exemple :
TYPE
Feux = (Orange, Vert, Rouge)
Banque = (BICICI, SIB, SGBCI, BIAO, BHCI, BCEAO)
Jour = (lundi, mardi, mercredi, jeudi, vendredi,
samedi, dimanche)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 40
40
III. Partie déclaration
Type intervalle
Sous-type des types déjà définis.
Opérateurs : ceux du type père.
Syntaxe :
TYPE
Identificateur=borneInférieure..borneSupérieur
Exemple :
TYPE
Chiffre = 0..9
Lettre = 'a'.. 'z'
Boulot = lundi..vendredi
Repos = samedi..dimanche
INP-HB/DFRMI/K. M. BROU Langage algorithmique 41
41
III. Partie déclaration
3.5. Le types tableau Variable indicée :
Présentation Chaque élément du tableau
Il possède un nom et un type fixe, Référencé par le nom du tableau
suivi par un ou plusieurs indices.
Il est associé à un ensemble de
valeurs. Indice :
Il permet de représenter des Correspond à une dimension du
ensembles de valeurs ayant des tableau.
propriétés communes. Leurs valeurs appartiennent à un
Exemple : vecteur et matrice en sous-ensemble des entiers.
mathématique.
Définition
Structure de données regroupant
une suite d’éléments de même
type rangés dans des cellules
mémoires contigües.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 42
42
III. Partie déclaration
Tableau à une dimension : Syntaxe 2 :
Vecteur TYPE
Adresse d’une variable indicée : Identificateur = TABLEAU[indiceInf..indiceSup] DE type T
VAR
Identificateur2 : Identificateur
adr + (i – IndiceInf)*p
avec :
Chaque élément du tableau est
adr : adresse du premier élément référencé par le nom du tableau
P : nombre de mot occupé par un suivi par un indice.
élément
i : indice d’un élément
indiceInf : indice inférieur
Syntaxe 1 :
VAR
Identificateur : TABLEAU[indiceInf..indiceSup] DE type T
INP-HB/DFRMI/K. M. BROU Langage algorithmique 43
43
III. Partie déclaration
Exemple : Accès au éléments du tableau :
tableau de 5 éléments de type On utilise un seul indice.
entier (notes d’un élève) t[1] : le 1er élément du tableau
VAR t
t : TABLEAU[1..5] DE ENTIER
ou t[2] représente le 2ième
TYPE élément du tableau t
Vecteur = TABLEAU[1..5] DE ENTIER
VAR t[i] représente le iième élément
t : Vecteur du tableau t
INP-HB/DFRMI/K. M. BROU Langage algorithmique 44
44
III. Partie déclaration
Tableau à deux dimensions : Exemple :
Matrice Matrice de 3 lignes et 2 colonnes
Syntaxe 1 : d’éléments de type réels c’est-à-
dire 6 éléments (Colonne 1 : note,
VAR colonne 2 : coefficient).
Identificateur :
TABLEAU[indiceInf1..indiceSup1, VAR
indiceInf2..indiceSup2] DE type T m : TABLEAU[0..2, 1..2] DE REEL
ou
TYPE
Syntaxe 2 : Matrice = TABLEAU[0..2, 1..2] DE REEL
VAR
TYPE m : Matrice
Identificateur =
TABLEAU[indiceInf1..indiceSup1,
indiceInf2..indiceSup2] DE type T
VAR
Identificateur2 : Identificateur
INP-HB/DFRMI/K. M. BROU Langage algorithmique 45
45
III. Partie déclaration
Accès aux éléments du tableau m : Adresse de m[i, j]
On utilise deux indices : un pour M : nombre de ligne
les lignes (1er indice) et un autre p : taille en octet d’un élément
pour les colonnes (2ième indice). Adresse de m[1, 1] : (adr + M*p)
m[0, 1] : élément situé à est égal à
l’intersection de la ligne 0 et de la = adr + (i*M + j-1)p
colonne 1 est avoir (intégrer boneInf)
m[1, 2] : élément situé à
Tableau à plusieurs dimensions :
l’intersection de la ligne 1 et de la
colonne 2 Tenseur
m[i, j] : élément situé à Syntaxe :
l’intersection de la ligne i et de la
colonne j TYPE
Identificateur =
TABLEAU[indiceInf1..indiceSup1,
indiceInf2..indiceSup2, indiceInfn..indiceSupn]
DE type T
INP-HB/DFRMI/K. M. BROU Langage algorithmique 46
46
III. Partie déclaration
3.6. Déclaration de variable Exemple
Définition VAR
dividende, diviseur, quotient, reste : ENTIER
Une variable est un espace
prix_TTC : REEL
mémoire désigné par un J : Jour
identificateur et utilisé pour
désigner une valeur quelconque
d’un ensemble donné. Corps de l’algorithme
Sa valeur peut changer tout au
Partie qui contient les instructions
long de l’exécution de
exécutables de l’algorithme.
l’algorithme.
Affectation
C’est en fait une adresse mémoire
où l’on range une valeur. Lecture/Ecriture
Structures de contrôle
Syntaxe :
Fonction
VAR Cette partie est délimitée par les
Identificateur : type de la variable mots réservés DEBUT et FIN.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 47
47
IV. Instructions exécutables
5.1. L’affectation Syntaxe :
Instruction la plus élémentaire Identificateur Expression
Cette instruction se lit :
Elle consiste à affecter à une
Identificateur reçoit la valeur de
variable la valeur d’une
Expression
expression de même type ou de
ou
type compatible.
Ranger la valeur de Expression
dans Identificateur
INP-HB/DFRMI/K. M. BROU Langage algorithmique 48
48
IV. Instructions exécutables
Exemple : Evolution des variables dans la
ALGORITHME affectation
MC
Var Variables i j k b
i, j, k : ENTIER après (1) ? 2 ? ?
b : BOOLEEN après (2) ? 2 3 ?
DEBUT après (3) 5 2 3 ?
j2 (1) après (4) 7 2 3 ?
k3 (2) après (5) 8 2 3 ?
i j + k (3) après (6) 8 2 3 FAUX
i i + j (4) après (7) 8 2 3 ERREUR
i i + 1 (5)
b i = j (6)
bi (7)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 49
49
IV. Instructions exécutables
Exercices : Exercice 2 : Déterminer les valeur
Exercice 1 : Déterminer les des tableaux t1 et t2 après
valeurs des variables a, b, c et d exécution de cet algorithme.
après exécution de cet algorithme
ALGORITHME affectation1
ALGORITHME affectation2
VAR a, b, c, d : ENTIER
TYPE Vecteur = TABLEAU[1..3] DE ENTIER
DEBUT
VAR t1, t2 : Vecteur
a1
DEBUT
b3
t1[1] 1
ca+b
t1[2] 2
da-b
t1[3] 3
ac+2*b
t2[1] t1[1] + t1[2]
bc+b
t2[2] t1[1] + t1[3]
ca*b
t2[3] t2[1] + t1[3]
db+d
t2[1] t2[3] - t1[1]
ad*c
t1[2] 2 *t2[1] + t1[2]
SI (c > d) ALORS
t1[1] t2[2] + t1[1]
ca-d
FIN
SINON
cb-d
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 50
50
IV. Instructions exécutables
5.2. Instruction d’écriture Syntaxe 1 :
Ecriture : opération permettant ECRIRE(v1, v2, …, vn)
de véhiculer les données de la MC où les vi sont des variables et/ou
vers l’extérieur des constantes.
Après l’écriture de vn, le curseur
Exemple : écran
reste après vn
Syntaxe 2 :
MC
ECRIRE
Permet au curseur de passer à la
Périphérique de sortie
ligne suivante
INP-HB/DFRMI/K. M. BROU Langage algorithmique 51
51
IV. Instructions exécutables
Exemple 1 : Exemple 2 :
ALGORITHME ecriture ALGORITHME ecriture
CONST Pi = 3.14 CONST Pi = 3.14
VAR omega : REEL VAR omega : REEL
DEBUT DEBUT
omega 100 * Pi omega 100 * Pi
ECRIRE('Valeur de PI = ', Pi) ECRIRE('Valeur de PI = ', Pi)
ECRIRE('Valeur de omega = ', omega) ECRIRE
FIN ECRIRE('Valeur de omega = ', omega)
FIN
Après Exécution
Valeur de PI = 3.14Valeur de omega = 314
Après Exécution
Valeur de PI = 3.14
Valeur de omega = 314
INP-HB/DFRMI/K. M. BROU Langage algorithmique 52
52
IV. Instructions exécutables
5.3. Instruction de lecture Exemple 1 : lecture d’un nombres
entier
Lecture : opération permettant de ALGORITHME lecture
véhiculer les données de d’un VAR x : ENTIER
DEBUT
périphérique d’entrée vers la MC.
ECRIRE('Entrer un entier : ')
La donnée lue est affectée à une LIRE(x)
variable. ECRIRE(‘valeur lue = ‘, x)
FIN
Exemple : clavier
Exemple 2 : addition de 2
MC
nombres entiers
ALGORITHME lecture
Périphérique d’entrée
VAR x, Y, res : ENTIER
Syntaxe DEBUT
LIRE(v1, v2, …, vn) ECRIRE('Entrer deux entiers : ')
LIRE(x, y)
où les vi sont des variables res x + Y
Les données lues seront affectées ECRIRE(x,' + ‘, y, ' = ', res)
aux vi. FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 53
53
IV. Instructions exécutables
Exercices : Exercice 4 : Sans changer les
instructions de l’Exercice 3
Exercice 1 : Ecrire un algorithme
ajoutez d’autres instructions afin
permettant d’afficher le message
d’afficher le message suivant :
"Bonjour Fatou" à l’écran.
Exercice 2 : Ecrire un algorithme Bonjour M. BROU Konan
Votre devoir est vraiment facile
permettant de lire le nom de <<<<<<<<<<>>>>>>>>>>>>
l’utilisateur et de l’afficher à
l’écran précédé du mot Exercice 5 : Ecrire un algorithme
"Bonjour". qui calcule la somme de 2 réels
Exercice 3 : Ecrire un algorithme saisis au clavier.
permettant d’afficher le message Exercice 6 : Ecrire un algorithme
suivant : qui calcule l’expression suivante :
Bonjour M. BROU x*y +5, x et y sont saisis au
<<<<<<<<<<<<
clavier.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 54
54
IV. Instructions exécutables
4.4. Nature séquentielle d’un Bloc
algorithme Ensemble d’instructions
séquentiellement chaînées
Un algorithme se déroule en délimitées par les mots réservés
séquence DEBUT et FIN.
C’est-à-dire que les instructions
sont exécutées l’une après l’autre, DEBUT
sauf contre indication. instruction1
instruction2
Instructions sont …
séquentiellement chaînées : instructionn
FIN
La fin de l’exécution d’une
instruction déclenche l’exécution
de celle qui la suit Remarque :
immédiatement. Si un bloc contient une seule
instruction, on peut omettre
DEBUT et FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 55
55
IV. Instructions exécutables
Les structures de contrôle
Un algorithme est dit structuré
s’il est écrit à l’aide des trois
structures de contrôle de base :
L’affectation
L’instruction conditionnelle
L’instruction itérative ou boucle
INP-HB/DFRMI/K. M. BROU Langage algorithmique 56
56
IV. Instructions exécutables
4.5. L’alternative Syntaxe 2 : l’alternative
complexe
Ou instruction conditionnelle
SI (condition) ALORS
Elle permet de faire un test
Bloc1
i.e. évaluer une expression SINON
logique et enchaîner vers telle ou Bloc2
telle autre instruction selon la
valeur trouvée.
Syntaxe 1 : l’alternative simple
Condition vérifiée ? FAUX
SI (condition) ALORS
Bloc VRAI
Bloc1 Bloc2
Condition vérifiée ? FAUX
VRAI Suite de l’algorithme
Bloc
Suite de l’algorithme
INP-HB/DFRMI/K. M. BROU Langage algorithmique 57
57
IV. Instructions exécutables
Exemple 1 : égalité de 2 nombres Exemple 2 : test complet d’égalité
entiers lus au clavier. de 2 nombres entiers lus au
clavier.
ALGORITHME egalite
VAR a, b : ENTIER
DEBUT ALGORITHME egalite
ECRIRE('Entrer deux nombres entiers : ' ) VAR a, b : ENTIER
LIRE(a, b) DEBUT
SI (a = b) ALORS ECRIRE('Entrer deux nombres entiers : ' )
ECRIRE('Les deux nombres sont égaux’) LIRE(a, b)
FIN SI (a = b) ALORS
ECRIRE('Les deux nombres sont égaux')
SINON
ECRIRE('Les deux nombres sont différents')
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 58
58
IV. Instructions exécutables
Exemple 3 : maximum de deux
nombres réels saisis au clavier.
ALGORITHME Maximum
VAR a, b : REEL
DEBUT
ECRIRE('Entrer deux nombres réels : ' )
LIRE(a, b)
SI (a = b) ALORS
ECRIRE('Les deux nombres sont égaux')
SINON SI (a > b) ALORS
ECRIRE(a, ' > ', b)
SINON
ECRIRE(b, ' > ', a)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 59
59
IV. Instructions exécutables
4.6. Le choix multiple Syntaxe :
ou aiguillage CHOISIR (expression) PARMI
C’est une généralisation de valeur1 : Bloc1
valeur2 : Bloc2
l’alternative complexe. …
Il permet de choisir une valeurn : Blocn
instruction à exécuter parmi [AUTRE : Blocn+1]
FIN
plusieurs selon la valeur d’une
expression.
Si la valeur de expression est
égale à une des valeursi, le bloci
correspondant est exécuté.
Dans le cas contraire, le blocn+1
est exécuté.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 60
60
IV. Instructions exécutables
Exemple 1 : Avec SI ... ALORS
Ecrire un algorithme permettant ALGORITHME ChiffreLettre
d’afficher les 3 premiers chiffres VAR chiffre : ENTIER
en toute lettre. DEBUT
ECRIRE('Entrer un chiffre : ' )
LIRE(chiffre)
ALGORITHME ChiffreLettre
SI(chiffre=0) ALORS
VAR chiffre : ENTIER
ECRIRE('zéro')
DEBUT
SINON SI(chiffre=1) ALORS
ECRIRE('Entrer un chiffre : ' )
ECRIRE('un')
LIRE(chiffre)
SINON SI(chiffre=2) ALORS
CHOISIR (chiffre) PARMI
ECRIRE('deux')
0 : ECRIRE('zéro')
SINON
1 : ECRIRE('un')
ECRIRE('Chiffre non demandé')
2 : ECRIRE('deux')
FIN
AUTRE : ECRIRE('Chiffre non demandé')
FIN
FIN Le choix multiple est préférable à
l'alternative lorsqu'il y a trop
d'imbrications de SI ... SINON SI
INP-HB/DFRMI/K. M. BROU Langage algorithmique 61
61
IV. Instructions exécutables
Exemple 2 :
La valeur de expression peut être
de type : ENTIER, CAR, TEXTE,
intervalle ou énuméré.
ALGORITHME Intervalle
VAR c : CAR
DEBUT
ECRIRE('Entrer un caractère : ' )
LIRE(c)
CHOISIR (c) PARMI
'A'.. 'Z', 'a'.. 'z' : ECRIRE('Lettre')
'0'.. '9' : ECRIRE('Chiffre')
'+','-', '*', '/' : ECRIRE('Opérateur arithmétique')
AUTRE : ECRIRE('Caractère spécial')
FIN
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 62
62
IV. Instructions exécutables
Exercices : Exercice 3 : Ecrire un algorithme
qui transforme, les notes de 0 à
Exercice 1 : Ecrire un algorithme
20 d’un devoir en une notation
qui lit le nom et le genre de
par lettre. Après avoir lu la note,
l’utilisateur puis affiche le
la moyenne m et l’écart-type
message Bonjour M. (ou Mme
des notes de la classe, on
selon la nature du genre) suivi du
applique le barème suivant :
nom de l’utilisateur.
Notes [0, m - [ : C
Exemple : "Bonjour M. Toto"
Notes [m - , m + [ : B
Exercice 2 : Ecrire un algorithme
Notes [m + , 20] : A
qui lit un réel a, et imprime un
résultat b tel que, si a > 20 alors
b=a/2 ; si a< 0 alors b = 0 ;
sinon b = 2a.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 63
63
IV. Instructions exécutables
Exercice 4 : Ecrire de deux façons Exercice 5 : Ecrire un algorithme
différentes (alternative et choix qui lit trois nombres entier x, y et
multiple) un algorithme z et permet de tester si x, y et z
permettant de simuler une peut être les longueurs de 3 côtés
calculette effectuant les d’un triangle. C’est le cas si et
opérations arithmétiques seulement si on a
élémentaires (+, -, *, /). Les simultanément :
opérandes et l’opérateur sont x>0
entrés au clavier. y>0
z>0
x + y >z
x+z>y
y+z>x
INP-HB/DFRMI/K. M. BROU Langage algorithmique 64
64
IV. Instructions exécutables
Exercice 6 : Ecrire un algorithme
permettant résoudre une
équation du second degré de la
forme ax2 + bx + c = 0 dans
l’ensemble des nombre
complexes C. Les coefficients a, b
et c sont des réels. On envisagera
tous les cas possibles.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 65
65
IV. Instructions exécutables
Les instructions itératives On distingue 3 types de boucles :
ou boucles POUR : on connaît le nombre
d’itération à faire
Elles permettent de spécifier
REPETER..JUSQUA : on ne connaît
l’exécution d’un bloc d’instruction pas le nombre d’itération à faire
un certain nombre de fois. TANTQUE : on ne connaît pas le
nombre d’itération à faire
INP-HB/DFRMI/K. M. BROU Langage algorithmique 66
66
IV. Instructions exécutables
Syntaxe 2 : pas décroissant
4.7. La boucle POUR
Instruction itérative à bornes FAUX
POUR i i2, i1, i3 i i1 ?
définies Bloc
VRAI
Syntaxe 1 : pas croissant i3 < 0
Bloc
Suite de
FAUX i = i + i3
POUR i i1, i2, i3 l’algo
Bloc
i i2 ? Avec :
VRAI
i3 0 i : variable de la boucle
Bloc
i1 : valeur initiale de i
Suite de
i = i + i3
l’algo i2 : valeur finale de i
i3 : appelé pas > 0 (pas croissant)
ou < 0 (pas décroissant)
valeur à ajouter à i à chaque
itération
= 1 par défaut (pas croissant)
i1 i2
INP-HB/DFRMI/K. M. BROU Langage algorithmique 67
67
IV. Instructions exécutables
Exemple 1 : Afficher le message Exemple 2 : Factorielle d’un
"Bonjour Fatou" 10 fois à l’écran. nombre.
Pas croissant
n ! = 1 x 2 x 3 x…x n
ALGORITHME Salutation ALGORITHME Salutation
CONST N = 10 ALGORITHME FactorielleCroissant
CONST N = 10
VAR i : ENTIER VAR i, n, fact : ENTIER
VAR i : ENTIER
DEBUT DEBUT
DEBUT
POUR i 1, N ECRIRE('Entrer un entier positif :' )
POUR i 1, N, 1
DEBUT LIRE(n)
DEBUT ou
ECRIRE('Bonjour Fatou' ) SI (n = 0) OU (n = 1) ALORS
ECRIRE('Bonjour Fatou' )
ECRIRE fact 1
ECRIRE
FIN SINON
FIN
FIN DEBUT
FIN
f act 1
POUR i 2, n
fact fact * i
FIN
ECRIRE(n, ' ! = ', fact)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 68
68
IV. Instructions exécutables
Exemple 2 : Factorielle d’un ALGORITHME FactorielleDecroissant
nombre. VAR i, n, fact : ENTIER
DEBUT
Pas décroissant ECRIRE('Entrer un entier positif :' )
n ! = n x (n-1) x (n-2) x … x 2 x 1 LIRE(n)
SI (n = 0) OU (n = 1) ALORS
fact 1
SINON
DEBUT
f act 1
POUR i n, 2, -1
fact fact * i
FIN
ECRIRE(n, ' ! = ', fact)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 69
69
IV. Instructions exécutables
4.8. La boucle TANTQUE Exemple :
Afficher le nom et le prénom de
On l’utilise quand on n’est pas sûr
l’utilisateur précédé du mot
que le corps de la boucle doit être
Bonjour autant de fois qu’il le
exécuté au moins une fois.
désire.
Syntaxe : ALGORITHME Salutation
TANTQUE (condition) VAR nom, prenom : TEXTE
Bloc reponse : TEXTE
DEBUT
Tant que la condition est vérifiée, reponse 'oui‘
le corps de la boucle (Bloc) est ECRIRE('Entrer votre nom et votre prénom :' )
exécuté. LIRE(nom, prenom)
TANTQUE(reponse = 'oui')
FAUX DEBUT
Condition vérifiée ? ECRIRE('Bonjour ',nom, ' ', prenom)
VRAI ECRIRE
ECRIRE('Continuer oui/non : ')
Bloc
LIRE(reponse)
Suite de FIN
INP-HB/DFRMI/K. M. BROU
l’algorithme Langage algorithmique FIN 70
70
IV. Instructions exécutables
Le corps de la boucle est exécuté
4.9. La boucle
jusqu’à ce que la condition soit
REPETER..JUSQUA vérifiée.
On l’utilise quand on est sûr que Remarque
le corps de la boucle doit être Pour transformer une boucle
exécuté au moins une fois. TANTQUE en une boucle
Syntaxe : REPETER..JUSQUA et vice versa, il
suffit de prendre la négation de la
REPETER
condition.
Bloc
JUSQUA(condition)
TANTQUE(condition)
Bloc
Equivalent à
Bloc
REPETER
Condition vérifiée ? VRAI
Bloc
FAUX JUSQUA(NON condition)
Suite de l’algorithme
INP-HB/DFRMI/K. M. BROU Langage algorithmique 71
71
IV. Instructions exécutables
Exemple : ALGORITHME Salutation
Afficher le nom et le prénom de VAR nom, prenom : TEXTE
l’utilisateur précédé du mot reponse : TEXTE
Bonjour autant de fois qu’il le DEBUT
ECRIRE('Entrer votre nom et votre prénom :' )
désire.
LIRE(nom, prenom)
REPETER
ECRIRE('Bonjour ',nom, ' ', prenom)
ECRIRE
ECRIRE('Continuer oui/non : ')
LIRE(reponse)
JUSQUA(reponse = 'non')
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 72
72
IV. Instructions exécutables
Exercices : Exercice 4 : Ecrire un algorithme
permettant de calculern :
Exercice 1 : Ecrire un algorithme S (i 2)
permettant de calculer la somme i 0
de n nombres lus au clavier (n Exercice 5 : Ecrire un algorithme
est une variable). permettant de calculer n!
Exercice 2 : Ecrire un algorithme Exercice 6 : Ecrire un algorithme
permettant de calculer somme permettant de calculer les
des n premiers nombres paires. coefficients du binôme de
Exercice 3 : Ecrire un algorithme Newton: p
n!
C n p!(n p)!
permettant de calculer la somme
du carré des 100 premiers Exercice 7 : combien de termes
nombres. sont-ils nécessaires à la série
pour que la condition suivante
soit satisfaite. N
1
i limite
i 1
INP-HB/DFRMI/K. M. BROU Langage algorithmique 73
73
IV. Instructions exécutables
Exercice 8 : Résistance Exercice 8.3 : Exercice 8.1 et
Exercice 8.2 dans le même
équivalente
algorithme.
Ecrire un algorithme permettant
n et la valeur des résistances sont
de calculer la valeur de la
lus au clavier.
résistance équivalente à n
résistances placées :
Exercice 8.1 : en série
n
Rs Ri R1 R2 Rn
i 1
Exercice 8.2 en parallèle
R1
1
Rp n
1 R2
Ri
i 1
Rn
INP-HB/DFRMI/K. M. BROU Langage algorithmique 74
74
IV. Instructions exécutables
Exercice 9 : Les nombres Exercice 11 : suite de Fibonacci
premiers Ecrire un algorithme permettant
Ecrire un algorithme permettant de calculer le nième .terme de la
de déterminer les nombres suite de Fibonacci définie par : U1
premiers inférieurs à 100 (un = 1, U2 = 2 et Un = Un-1 + Un-2 (n
nombre est premier s’il a deux 3)
diviseurs : 1 et lui-même).
Exercice 10 : Les nombres
parfaits
Un nombre parfait est un entier
naturel égal à la somme de tous
ses diviseur, 1 inclus (mais lui-
même exclu). Ex. 6 = 1 + 2 + 3.
Ecrire un algorithme permettant
de déterminer en les comptant les
nombres parfaits compris entre 6
et 10000.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 75
75
IV. Instructions exécutables
Exercice 13 ALGORITHME mystere2
Exercice 12 :
VAR x, y, z, u : ENTIER
DEBUT
ALGORITHME mystere1
LIRE(x, y)
VAR x, y : ENTIER
ux
DEBUT
z0
x0
TANTQUE(u 0)
REPETER
DEBUT
LIRE(y)
zz+y
SI( y > x) ALORS
uu-1
xy
FIN
JUSQUA(y = 0)
ECRIRE(z)
ECRIRE(x) Questions :
FIN
FIN
1. Que fait cet algorithme ?
Questions : 2. Que se passe t-il si x < 0 ?
Que fait cet algorithme ? 3. Proposer une solution
Remplacer la boucle 4. Proposer une solution pour les
REPETER..JUSQUA par une boucle valeurs de x et de y de signe
TANTQUE quelconque.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 76
76
V. Les sous-algorithmes
5.1. Présentation Besoins de réduction du code
machine :
Besoins de clarté et de
Eviter de réécrire plusieurs fois un
maintenance : bloc d’instructions qui intervient
Décomposer un algorithme plusieurs fois dans un même
complexe ou volumineux en algorithme ;
plusieurs unités logiques ou
Ce bloc est écrit une seule fois
modules plus simples que
sous forme d’un sous-algorithme
l’algorithme initial.
Il peut être appelé n’importe où
Ces différents modules sont
dans un algorithme.
appelés sous-algorithmes.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 77
77
V. Les sous-algorithmes
Exemple : maximum de 4 Les trois traitements sont
identiques sauf les variables qui
nombres entiers.
changent.
ALGORITHME maximum
VAR a, b, c, d, max1, max2, max : ENTIER
DEBUT
ECRIRE('Entrer 4 nombres entiers : ')
LIRE(a,b,c,d)
max1 a
SI(b > max1) ALORS Traitement 1
max1 b
max2 c
SI(d > max2) ALORS Traitement 2
max2 d
max max1
SI(max2 > max) ALORS Traitement 3
max max2
ECRIRE('Maximum = ',max)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 78
78
V. Les sous-algorithmes
5.2. Définition
Un sous-algorithme assure de
manière autonome un traitement
particulier.
Ce traitement peut alors être
répété dans l’algorithme principal
ou dans un autre sous-algorithme
par simple appel du sous-
algorithme.
On distingue deux sortes de sous-
algorithmes :
les procédures et les fonctions.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 79
79
V. Les sous-algorithmes
5.3. Procédure Structure d’une procédure
Elle est semblable à celle d’un
La notion de procédure comporte algorithme ;
2 aspects :
Elle comporte une tête, une partie
Déclaration de la procédure : c’est déclaration et un corps.
la définition de la procédure
La tête de la procédure :
Appel de la procédure : c’est
Commence par le mot réservé
l’utilisation de la procédure.
PROCEDURE
Déclaration d’une procédure Suivi du nom de la procédure et
Elle se situe en dehors d’un d’une liste de paramètres placée
algorithme. entre parenthèses.
Syntaxe : Les paramètres assurent la
PROCEDURE identificateur(liste de paramètres) communication entre les
[Déclaration d’objets locaux] différents modules d’un
DEBUT algorithme.
(* corps de la procédure *)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 80
80
V. Les sous-algorithmes
Exemples : Notion de paramètres ou
Paramètres de type D et R d’arguments :
Ils assurent la communication
PROCEDURE maximum (D x, y : ENTIER , R max : ENTIER)
entre les différentes parties d’un
DEBUT
max x algorithme.
SI (y max) ALORS 3 sortes de paramètres :
max y Paramètre de type Donnée ou
FIN
d’entrée
Paramètres de type DR Paramètre de type Résultat ou de
sortie
PROCEDURE echange(DR x, y : ENTIER) Paramètre de type Donnée-
VAR temp : ENTIER
Résultat ou d’Entrée-Sortie
DEBUT
temp x
xy
y temp
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 81
81
V. Les sous-algorithmes
Paramètre de type Donnée : Paramètre de type Résultat :
Chaque paramètre est précédé de Chaque paramètre est précédé de
D. R.
Il sert à véhiculer les données de Il sert à véhiculer les résultats de
l’extérieur (algorithme ou sous- l’intérieur du sous-algorithme
algorithme) vers l’intérieur du vers l’extérieur
sous-algorithme Exemple : paramètres max dans la
Exemple : paramètres x et y dans procédure maximum.
la procédure maximum.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 82
82
V. Les sous-algorithmes
Paramètre de type Donnée- Appel d’une procédure
Résultat : Il s’effectue à l’intérieur d’un
Chaque paramètre est précédé de algorithme ou d’un sous-
DR. algorithme appelant.
Combinaison des paramètres de Exemple :
type Donnée et de type Résultat.
Il sert à véhiculer les données de
l’extérieur (algorithme ou sous-
algorithme) vers l’intérieur du
sous-algorithme.
Après le traitement, il sert à
véhiculer les résultats de
l’intérieur du sous-algorithme
vers l’extérieur.
Exemple : paramètres x et y dans
la procédure echange.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 83
83
V. Les sous-algorithmes
Appel de la procédure maximum
PROCEDURE maximum (D x, y : ENTIER , R max : ENTIER)
ALGORITHME maximum DEBUT
VAR a, b, c, d, max1, max2, max : ENTIER max x
DEBUT SI (y max) ALORS
ECRIRE('Entrer 4 nombres entiers : ') max y
LIRE(a,b,c,d) FIN
max1 a
2 3 3
SI(b > max1) ALORS Traitement 1
max1 b ALGORITHME plusGrand
max2 c VAR a, b, c, d, max1, max2, max : ENTIER
SI(d > max2) ALORS Traitement 2 DEBUT
max2 d ECRIRE('Entrer 4 nombres entiers : ')
max max1 LIRE(a,b,c,d)
SI(max2 > max) ALORS Traitement 3 (*appel de la procedure maximum*)
max max2 maximum(a, b, max1)
ECRIRE('Maximum = ',max) maximum(c, d, max2)
FIN maximum(max1, max2, max)
ECRIRE('Maximum = ', max)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 84
84
V. Les sous-algorithmes
Appel de la procédure echange PROCEDURE echanger (DR x, y : ENTIER)
VAR temp : ENTIER
DEBUT
max x
SI (y max) ALORS
max y
FIN
2 3
3 2
ALGORITHME plusGrand
VAR a, b : ENTIER
DEBUT
ECRIRE('Entrer 2 nombres entiers : ‘)
LIRE(a,b)
(*appel de la procedure echange*)
ECRIRE('Avant échange : ', a, ' ',b)
echanger(a, b)
ECRIRE('Avant échange : ', a, ' ',b)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 85
85
V. Les sous-algorithmes
Procédure sans paramètre
Déclaration
PROCEDURE affMessage
DEBUT
ECRIRE('Bonjour Fatou, comment vas-tu ? ‘)
FIN
Appel de la procédure
ALGORITHME salutation
DEBUT
affMessage (*appel de la procedure affMessage*)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 86
86
V. Les sous-algorithmes
Exercices
Ecrire une procédure fact
permettant de calculer la
factorielle d’un nombre.
Ecrire algorithme permettant de
calculer les coefficients du binôme
de Newton
n!
p
C n
p! x ( n p )!
INP-HB/DFRMI/K. M. BROU Langage algorithmique 87
87
V. Les sous-algorithmes
5.4. Fonction Déclaration d’une fonction
Sous-algorithme similaire à la Elle se situe en dehors d’un
algorithme.
procédure mais qui calcule une
Syntaxe :
valeur d’un type donné.
Cette valeur sera retournée à FONCTION identificateur(liste de paramètres) : Type
l’algorithme appelant à travers le [Déclaration d’objets locaux]
DEBUT
nom de la fonction. (* corps de la fonction *)
Le nom de la fonction est donc un identificateur expression
FIN
paramètre résultat
INP-HB/DFRMI/K. M. BROU Langage algorithmique 88
88
V. Les sous-algorithmes
Exemple : Appel d’une fonction
Maximum de deux entiers Il s’effectue à l’intérieur d’un
algorithme ou d’un sous-
FONCTION maximum(D x, y : ENTIER) : ENTIER algorithme appelant.
VAR max : ENTIER Exemple :
DEBUT
max x
SI (y max) ALORS ALGORITHME PlusGrand
max y VAR a, b, max : ENTIER
maximum max DEBUT
FIN ECRIRE('Entrer 2 nombres entiers : ')
LIRE(a,b)
(* appel de la fonction maximum *)
max maximum(a, b)
ECRIRE('Maximum de ',a, ' et ', b, ' = ', max)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 89
89
V. Les sous-algorithmes
Différences entre procédure et Fonctions et procédures
fonction prédéfinies
au niveau de la déclaration : Il existe des procédures et
une fonction retourne une valeur fonctions prédéfinies, exemples
(donc possède un type) par Procédure ou fonction Signification
l’intermédiaire de son nom qui est EXP(x) Exponentielle
un paramètre résultat ; SQRT(x) Racine carrée
au niveau de l’appel : ABS(x) Valeur absolue
ARRETER Met fin à un programme
le nom d’une fonction peut
apparaître dans le membre droit
d’une affectation.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 90
90
V. Les sous-algorithmes
Exercices
Ecrire une fonction fact
permettant de calculer la
factorielle d’un nombre.
Ecrire algorithme permettant de
calculer les coefficients du binôme
de Newton
n!
p
C n
p! x ( n p )!
INP-HB/DFRMI/K. M. BROU Langage algorithmique 91
91
V. Les sous-algorithmes
Exercice : Ecrire un algorithme Exercice : Ecrire un algorithme
permettant d’effectuer les permettant d’effectuer les
traitements suivants sur un traitements suivants sur une
vecteur de 10 réels : matrice de 10 réels (5 lignes, 2
Lire les éléments du vecteur colonnes) :
Afficher les éléments du vecteur Lire les éléments de la matrice
Rechercher le minimum et le Afficher les éléments de la matrice
maximum des éléments du Rechercher le minimum et le
tableau. maximum des éléments du
Calculer la moyenne des éléments tableau.
du tableau. Calculer la moyenne des éléments
Rechercher la présence d’un du tableau.
élément dans le vecteur. Rechercher la présence d’un
NB : ces traitements seront écrits élément dans la matrice.
sous forme de sous-algorithmes. NB : ces traitements seront écrits
sous forme de sous-algorithm
INP-HB/DFRMI/K. M. BROU Langage algorithmique 92
92
V. Les sous-algorithmes
Ecrire un sous-algorithme Soient le deux suites U et V
permettant de calculer an pour définies par :
tout a réel et tout n entier U1 = 1, U2 = 2 et Ui = Ui-1 + Ui-2 et
(positif, négatif ou nul). Vi = Ui/Ui-1 (i 3)
a = 0 et n > 0 p = 1 La suite V tend vers une limite
a = 0 et n < 0 p est indéfinie approchée appelée nombre d’or.
a 0 et n < 0 p = 1/an On supposera que le nième terme
de la suite V soit Vn donne une
a 0 et n > 0 p = an
valeur approchée du nombre d’or
Ecrire un algorithme permettant avec la précision E, dès que
de calculer le nième terme de la
suite de Fibonacci définie par : Ecrire une permettant de calculer
U1 = 1, U2 = 2 et la valeur du nombre d’or avec une
Un = Un-1 + Un-2 (n 3) précision E, et le rang du terme de
la suite V considéré comme égal
au nombre d’or = 1 5
2
INP-HB/DFRMI/K. M. BROU Langage algorithmique 93
93
V. Les sous-algorithmes
5.5. Portée des variables Variables locales
Variables déclarées dans la partie
Variables globales déclaration de tout algorithme ou
Variables déclarées en dehors de sous-algorithme.
tout algorithme ou sous-
Ces variables ne sont accessibles
algorithme.
que dans les algorithmes ou sous-
Ces variables sont accessibles à algorithme où elles ont été
tout algorithme ou sous- déclarées.
algorithme.
A la sortie de l’algorithme ou
Leur durée de vie est celle de sous-algorithme, la zone de
l’algorithme principal mémoire qui leur a été allouée est
libérée.
Leur durée de vie est celle de
l’algorithme ou sous-algorithme
où elles ont été déclarées.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 94
94
V. Les sous-algorithmes
Exemple : v1 et v2 : globale
v3 : local
VAR v1, v2 : REEL
PROCEDURE modif(D v : REEL)
DEBUT
v1 v1 + v * v
FIN
ALGORITHME vGlobale
VAR v3 : REEL
DEBUT
ECRIRE('Entrer 2 nombres réels : ')
LIRE(v1, v2)
v3 v1 + v2
ECRIRE('Avant modification ',v1,v2)
modif(v3)
ECRIRE('Après modification ',v1,v2)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 95
95
VI. La récursivité
6.1. Présentation
Deux sortes de récursivité :
Récursivité indirecte : deux
fonctions s’appellent
mutuellement.
Récursivité directe : Un sous-
algorithme qui s’appelle lui-
même.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 96
96
VI. La récursivité
6.2. Récursivité indirecte Exécution : flop(4)
Un algorithme A appelle un
flop(4) FLOP
algorithme B qui lui-même
appelle A. flip(3) FLIP
Exemples : flop(2) FLOP
PROCEDURE flop(D m : ENTIER) flip(1) FLIP
DEBUT flop(0) Arrêt
ECRIRE(‘FLOP’)
SI(m>0) ALORS
flip(m-1)
FIN
PROCEDURE flip(D n : ENTIER)
DEBUT
ECRIRE(‘FLIP’)
SI(n>0) ALORS
flop(n-1)
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 97
97
VI. La récursivité
Exemple : n!
6.3. Récursivité directe
On parle de récursivité directe : 0! 1
Si un algorithme contient un ou n!
n! n * (n 1)!n 0
plusieurs appels à lui-même.
Ce principe est parfois utilisé
dans la vie courante :
"Yao descend de Kouacou soit si
Kouacou est le père (ou la mère)
de Yao, soit si le père (ou la mère)
de Yao descend de Kouacou".
En mathématique de nombreuses
fonctions sont définies suivant ce
principe.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 98
98
VI. La récursivité
Analyse récursive Etape 3 : Décomposition du cas
général : décomposer le cas
Permet d’éviter des appels infinis,
général afin de le ramener à un
comporte trois étapes :
problèmes, plus simples (de
Etape 1 : Paramétrage du tailles plus petites).
problème : déterminer les
différents éléments dont dépend
la solution du problème (en
particulier la taille du problème).
Etape 2 : Recherche d’un cas
trivial (test d’arrêt) : rechercher
un cas particulier qui donne la
solution directement sans appel
récursif. Ce sera souvent le cas ou
la taille du problème est égale à 0,
ou égale à 1, etc.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 99
99
VI. La récursivité
FONCTION fact(D n :ENTIER) : ENTIER
6.4. Quelques algorithmes DEBUT
récursifs simples SI(n=0) ALORS
fact 1
Factorielle d’un nombre SINON
Analyse du problème : soit fact la fact n*fact(n-1)
fonction factorielle FIN
Paramétrage
n: Nombre entier positif, nombre Exécution : fact(4)
dont on veut calculer la factorielle.
Recherche d’un cas trivial fact(4)= 4*3*2*1 = 24
*
SI(n=0) ALORS fact(n) = 1 4 fact(3) =3*2*1
*
Décomposition 3 fact(2)= 2*1
fact(n) = n fact(n-1) n > 0 *
2 fact(1)=1*1
*
1 fact(0)=1
1
INP-HB/DFRMI/K. M. BROU Langage algorithmique 100
100
VI. La récursivité
Exemple 2 : La tour d’Hanoi Règles
Les prêtres d’une secte ont à On ne peut déplacer qu’un seul
résoudre le problème suivant : disque à la fois.
Le jeu est constitué d’une Il est interdit de poser un disque
plaquette de bois où sont plantées plus grand sur un disque plus
trois tiges. petit.
Sur la 1ère tige sont enfilés 64 La fin du monde
disques de diamètres tous Elle coïncidera avec la fin du
différents. transfert des 64 disques.
Transférer tous ces disques sur la
2ème tige.
La 3ème tige est la tige de
manœuvre.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 101
101
VI. La récursivité
INP-HB/DFRMI/K. M. BROU Langage algorithmique 102
102
VI. La récursivité
Analyse du problème Décomposition du cas général
Soit hanoi le nom de la procédure Transférer récursivement (n-
récursive. 1) disques du sommet de x
(tige de départ), sur z (tige de
Soit deplacer la procédure de
manœuvre ), y (tige d’arrivé)
transfert d’un disque d’un socle à
sera utilisé comme tige de
un autre.
manœuvre :
Paramétrage :
hanoi(n-1,x,z,y)
n: Nombre de disque de type
Déplacer le disque qui reste en
entier
x (le plus grand) sur y :
x: Socle de départ deplacer(x,y)
y: Socle d’arrivé Transférer récursivement les
z: Socle intermédiaire (n-1) disques de z en y avec x
Recherche de cas triviaux : comme socle intermédiaire :
SI(n=0) ALORS ne rien faire hanoi(n-1,z,y,x)
SI(n=1) ALORS deplacer(x,y)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 103
103
VI. La récursivité
Algorithmes
Analyse du problème
Soit hanoi le nom de la procédure
PROCEDURE hanoi(D n, x, y, z : ENTIER)
récursive. DEBUT
Soit deplacer la procédure de transfert SI(n>0) ALORS
DEBUT
d’un disque d’un socle à un autre. hanoi(n-1, x, z, y)
Paramétrage : deplacer(x, y)
hanoi(n-1, z, y, x)
n: Nombre de disque de type FIN
entier FIN
x: Socle de départ
y: Socle d’arrivé PROCEDURE deplacer(D x, y : ENTIER)
z: Socle intermédiaire DEBUT
ECRIRE(‘Déplacez un disque de ‘,x,’ à ‘,y)
Recherche de cas triviaux : FIN
SI(n=0) ALORS ne rien faire
SI(n=1) ALORS deplacer(x,y)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 104
104
VI. La récursivité
Exécution : hanoi(3, A, B, C)
hanoi(3,A,B,C)
h1(2,A,C,B) d(A,B) h2(2,C,B,A)
h1(1,A,B,C) d(A,C) h2(1,B,C,A) h1(1,C,A,B) d(C,B) h2(1,A,B,C)
d(A,B) d(B,C) d(C,A) d(A,B)
h1(0,A,C,B) h2(0,C,B,A) h1(0,B,A,C) h2(0,A,C,B) h1(0,A,C,B) h2(0,C,B,A) h1(0,B,A,C) h2(0,A,C,B)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 105
105
VI. La récursivité
Fin du monde N = 64
Calcul de la complexité T(10) = 210 -1 = 1 023
T(20) = 220 - 1 = 1 048 575
1 si n 1
T (n) T(32) = 232 - 1 = 4 294 967 295
1 2T (n 1) si n 1 T(64) = 264 - 1 = 18 446 744 073 709
551 615 0,21020 unité de temps
Prenons comme unité de temps la
seconde.
1 an=31536000 s, 1 siècle 0,31010 s
Pour T(64) il faudrait environ 1010
siècles.
Ce qui n’est pas loin de la fin
du monde.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 106
106
VI. La récursivité
Exercice 1 : Exercices 3 :
Transformer une boucle en une On veut réaliser des opérations
procédure récursive. d’addition et de multiplication dans
PROCEDURE afficher1() un environnement qui n’offre que les
VAR i:ENTIER 2 opérateurs inc(incrémentation) et
DEBUT
POUR i 1, 10
dec(décrémentation).
ECRIRE('Bonjour Fatou') x=inc(2) x=3
FIN x=dec(2) x=1
Exercices 2 : Ecrire les sous-algorithmes récursifs
pour d’addition et la multiplication
Transformer deux boucles en une de 2 entiers positifs.
procédure récursive.
PROCEDURE afficher2()
Exercice 4 : Suite de Fibonacci
VAR i:ENTIER ={
DEBUT
POUR i 1, 10 Ecrivez un sous-algorithme récursif
POUR j 1, 3
ECRIRE('Bonjour Fatou')
calculant Fibo(n).
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 107
107
VI. La récursivité
Exercices 5 : PGCD Exercice 6 :
Ecrire un sous-algorithme récursif Ecrire une fonction récursive
permettant de calculer le pgcd de permettant de rechercher de façon
deux nombres entiers x et y. dichotomique une donnée dans un
Méthode 1 : tableau trié par ordre croissant.
SI x = y, alors pgcd = x Principe :
SI x<y, alors pgcd = pgcd de x et y–x Décomposer le tableau t en 2 sous
SI x > y, alors faire comme en 2 en tableaux, 3 cas possibles :
remplaçant x par y. Si x = t[milieu] alors x est trouvé et
Méthode 2 : Algorithme d’Euclide 300 la recherche est terminée.
av. JC Si x < t[milieu] alors chercher x dans
Soient 2 entiers naturels x et y, si y est la partie gauche du tableau t.
nul, alors le PGCD est égal à x. Sinon, Si x > t[milieu] alors chercher x dans
on calcule z, le reste de la division de x la partie droite du tableau t.
par y. On remplace x par y, et y par z, Conditions d’arrêt : t[milieu] = x ou
et on recommence le procédé. Le dimension de sous tableau = 0.
dernier reste non nul est le PGCD.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 108
108
VII. Méthode d’analyse des algorithmes
7.1. Présentation Il s’agit de décomposer le
problème complexe initial en des
Entre un problème à résoudre et
sous-problèmes dont le niveau
un programme, l’intermédiaire
de complexité est moins élevé
indispensable est un algorithme.
diviser pour régner.
La phase la plus difficile de la
programmation n’est pas la Deux méthodes d’analyse :
traduction de l’algorithme dans Analyse descendante
un quelconque langage Analyse ascendante.
Mais plutôt la conception de
l’algorithme.
On désigne cette étape sous le
nom d’analyse.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 109
109
VII. Méthode d’analyse des algorithmes
7.2. Analyse descendante A
Cette méthode consiste à partir
du problème initial, à descendre A1 A2 A3
étape par étape vers des
combinaisons de sous-problèmes A11 A12 A22 A31 A32
de plus en plus simple à résoudre.
A121 A122 A311
On procède en quelque sorte par
affinements successifs ;
c’est la méthode la plus utilisée
en programmation car naturelle et
facile à mettre en œuvre.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 110
110
VII. Méthode d’analyse des algorithmes
Exemple Illustration : recherche de 21 dans le
tableau suivant
Trouver un élément dans un
tableau non trié par la recherche 14 21 25 37 41 71 84 91 94
dichotomique.
La recherche dichotomique 21 < 41
accélère la recherche d’un élément
dans un tableau trié. 14 21 25 37
Principe
On compare l’élément cherché à 21 = 21
l’élément qui se trouve au milieu
du tableau.
S’il y a égalité, la recherche
s’arrête.
Sinon on poursuit la recherche
dans la moitié inférieure ou dans sa
moitié supérieure selon le résultat
de la comparaison.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 111
111
VII. Méthode d’analyse des algorithmes
Algorithme ALGORITHME Recherche
CONST N = 10
TYPE
Vecteur = TABLEAU[1..N] DE REEL
Recherche VAR x : REEL
indice : ENTIER
lireVect triBulles dicho t : Vecteur
DEBUT
lireVect(t) (* Saisie des éléments du tableau t*)
echange ECRIRE('Entrez l’’élément cherché : ')
LIRE(x)
triBulles(t) (* Tri du tableau t *)
indice dicho(t, x) (* Appel de la fonction dicho *)
SI(indice > 0) ALORS
ECRIRE('Elément ', x, ' a été trouvé, 'son indice est ', indice)
SINON
ECRIRE('Elément ', x, ' n''a pas été trouvé')
FIN
On détaille ci-dessous les
différents sous-algorithmes
INP-HB/DFRMI/K. M. BROU Langage algorithmique 112
112
VII. Méthode d’analyse des algorithmes
Procédure de saisie des éléments
d’un tableau
PROCEDURE lireVect(DR t : Vecteur)
VAR i : ENTIER
DEBUT
POUR i 1, N
DEBUT
ECRIRE('Enter t[',i, '] = ')
LIRE(t[i])
FIN
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 113
113
VII. Méthode d’analyse des algorithmes
Procédure de tri des éléments Principe
d’un tableau par la méthode du tri On compare chaque paire
bulles d’élément consécutif ; si ces
Il s’agit de ranger les éléments du éléments sont dans l’ordre, on
tableau dans un ordre croissant passe à la paire suivante, sinon
(ou décroissant) on procède à leur permutation
avant de traiter la paire suivante.
On parle de tri bulles par analogie
au fait que les éléments les plus
petits viennent au début de la
liste comme les bulles qui
remontent à la surface de l’eau.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 114
114
VII. Méthode d’analyse des algorithmes
Procédure tri par bulles Procédure de permutation de deux
valeurs
PROCEDURE triBulles(DR t : Vecteur)
VAR i, j : ENTIER PROCEDURE echange(DR x, y : REEL)
fini : BOOLEEN VAR temp : REEL
DEBUT DEBUT
i1 temp x
fini FAUX xy
TANTQUE((i < N) ET (NON fini)) y temp
DEBUT FIN
fini VRAI
POUR j i + 1, N
SI(t[i] > t[j]) ALORS
DEBUT
echange(t[i], t[j])
fini FAUX
FIN
i i+1
FIN
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 115
115
VII. Méthode d’analyse des algorithmes
Fonction de recherche dichotomique
FONCTION dicho(D t : Vecteur ; D x : REEL) : ENTIER
VAR i, j, m : ENTIER
DEBUT
i1
jN
REPETER
m (i + j) // 2 (* Calcul de l’indice du milieu du tableau t *)
SI(x > t[m]) ALORS
i m + 1 (* Recherche dans la moitié supérieure du tableau t *)
SINON
j m – 1 (* Recherche dans la moitié inférieure du tableau t *)
JUSQUA((t(m) = x) OU i > j)
SI(t[m] = x) ALORS
dicho m
SINON
dicho -1
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 116
116
VII. Méthode d’analyse des algorithmes
7.2. Analyse ascendante
On dispose d’outils (sous-
algorithmes) réalisant des
travaux élémentaires
On les compose pour résoudre un
problème de plus haut niveau.
Cette méthode est adopte une
démarche bidirectionnelle :
De haut en bas pour découper le
travail en tâches plus élémentaires
De bas en haut pour réaliser les
tâches élémentaire à l’aide des
outils disponibles.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 117
117
VII. Méthode d’analyse des algorithmes
7.3. Critiques On peut être amené à reprendre
l’application à tous les niveaux à
Analyse descendante la suite d’une remise en cause
Avantages d’un des choix initiaux
L’approche est systématique du Exemple : structure de
général au particulier ; données dynamique et non
L’aspect hiérarchique de l’analyse un tableau.
facilite la compréhension. Il y a un risque de redondance de
Inconvénients certains traitements
sous-algorithmes identiques qui
Elle effectue des choix conceptuels apparaissent dans plusieurs
de très haut niveau qui peuvent niveaux.
être délicats à réaliser au niveau On doit attendre d’écrire tous Les
inférieur. sous-algorithmes avant de tester tout
l’algorithme.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 118
118
VII. Méthode d’analyse des algorithmes
Analyse ascendante Inconvénients
Avantages Elle ne relève pas d’une
La réutilisation des sous- démarche systématique dans le
algorithmes existants ce qui processus d’analyse du
accroît la vitesse de problème ;
développement, réduit la taille de On note dérive possible de la
l’algorithme et facilite les tests ; résolution vers celle d’un autre
En choisissant des outils validés, problème.
on est sûr de leur opérationnalité Conclusion :
finale (moins de tests). Dans la pratique, on fait un
facilité de prototypage compromis entre ces deux
(construction rapide d’application à méthodes.
partir d’outils existants même si
ces outils sont trop généraux ou de
performance faible)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 119
119
VII. Méthode d’analyse des algorithmes
Exercice
On veut produire un algorithme
de résolution d’un système
linéaire régulier de N équations,
de la forme :
On peut résoudre ce système en
deux étapes :
d’abord on le transforme en
système triangulaire par
élimination progressive des
variables,
puis on résout le système
triangulaire.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 120
120
VIII. Structures de données dynamiques
8.1. Les pointeurs Notation
p : désigne la variable qui contient
Variable contenant l’adresse d’une
l’adresse de la variable c1 ;
autre variable.
p Cette variable peut être utilisée dans
la partie droite ou gauche d’une
p
affectation concernant des adresses.
c1 a
p : appelée variable pointée, désigne
p : variable de type pointeur qui l’objet dont l’adresse est rangée dans
contient l’adresse de la variable c1 p;
(contient la valeur a). p peut apparaître dans la partie
Déclaration de pointeur droite ou gauche d’une affectation
concernant des objets de même type.
TYPE Exemple :
TYPE_PTR = objet VAR
p1
VAR c1, c2 : CAR
nom_ptr : TYPE_PTR i : ENTIER p1
ou p1, p2 : CAR c1 a
VAR p3 : ENTIER
nom_ptr : objet
Objet étant de type simple ou structuré
INP-HB/DFRMI/K. M. BROU Langage algorithmique 121
121
VIII. Structures de données dynamiques
2.2. Opérations sur les pointeurs Variables MC Adresses
Opérateur adresse c1 'a' c1 a 07
c2 'b' c2 b 08
Noté &. i2 i 2 09
Permet d’affecter l’adresse d’une … P1 07 10
variable à un pointeur. p1 &c1 08
P2 12
p2 &c2
Syntaxe p3 &i
P3 09 14
indentificateur1 &identificateur2
identificateur1 : un pointeur p1
identificateur2 : une variable
p1
Exemple : c1 a
p2
p2
c2 b
p3
p2
i 2
INP-HB/DFRMI/K. M. BROU Langage algorithmique 122
122
VIII. Structures de données dynamiques
Affectation entre pointeurs Affectation entre valeurs pointées
p1 p2 p1 p2
Cette affectation permet d’obtenir : Cette affectation permet d’obtenir :
p p
p1 p2 1 2
p p
p1 p2 b1 b2
a b
Remarque :
p1
p2 a n’existe plus (alors que,
p1 p2 précédemment, il existait toujours,
a mais n’était plus accessible).
b
b existe en deux exemplaires ; l’un
des exemplaires a une adresse
Remarque : pointée par p1 et l’autre a une
a n’est plus accessible, car on a perdu adresse pointée par p2.
son adresse qui se trouvait dans p1.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 123
123
VIII. Structures de données dynamiques
Affectations illicites
Affectations entre pointeurs de valeurs
pointées de types différents.
p1 p3
p1 p3
Valeur d’adresse NUL
NUL : pointeur ne contenant aucune
adresse d’objet.
Permet d’initialiser les autres
pointeurs.
Exemple :
p NUL
Remarque :
p n’est défini que si p NUL
INP-HB/DFRMI/K. M. BROU Langage algorithmique 124
124
VIII. Structures de données dynamiques
2.3. Représentation d’une cellule La cellule contient deux champs :
Champ info : contient une information de
Utilisation d’une SD de type
type T ;
ENREGISTREMENT Champ suivant : contient une adresse.
TYPE Variable p : contient l’adresse de la
TYPE_PTR
= Cellule cellule.
Cellule = ENREGISTREMENT
info : T On dira, cellule d’adresse p ou cellule
suivant : TYPE_PTR pointée par p.
FIN T est un type simple, ou structuré
VAR
TYPE_PTR est un type pointeur
p : Cellule
Si p NUL, p.info permet d’accéder
p à l’information de la cellule d’adresse
p
p.
p.suivant permet d’accéder à
info suivant l’adresse contenue dans la cellule
d’adresse p.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 125
125
VIII. Structures de données dynamiques
2.4. Gestion dynamique de la Zone Explication
zone de 256 octets réservée par le système
mémoire d’exploitation pour contenir des informations
Un programme qui s’exécute est sur le programme (adresse de premier
PSP
segment libre suivant le programme,
chargé en MC comme suit : adresse de branchement après l’exécution
du programme, etc.)
MC contient le code machine des instructions du
zone de code
Limite Préfixe de segment de programme.
inférieure programme (PSP) Contient les données, elle est divisée en
quatre zones :
Code
La zone de variables globales ou
Variables globales ou statiques
statiques Le stack ou la pile contient les variables
Variables locales locales lors de l’exécution d’un sous-
zone de données
Données
(stack ou pile) programme.
Variables Le heap correspond à la zone mémoire
dynamiques (heap) utilisée pour l’allocation de variables
dynamiques
Limite Réserve (far heap)
Le far heap est une réserve pour
supérieure l’allocation dynamique.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 126
126
VIII. Structures de données dynamiques
Deux sortes de pointeurs :
Pointeurs contenant une adresse 16
bits : pointeur de type NEAR
Pointeur contenant une adresse 32
bits : pointeur de type FAR
Deux primitives de travail sur le tas :
RESERVER(p) : permet à chaque appel
d’obtenir une nouvelle cellule dont
l’adresse sera retournée dans la
variable p.
LIBERER(p) : rend la cellule d’adresse
p au réservoir.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 127
127
VIII. Structures de données dynamiques
3.1. Les piles
Définition
SD dynamique homogène à un seul ajout retrait
point d’accès. D sommet
Ajout et retrait des données par C
l’intermédiaire d’une tête d’accès B
appelée sommet de la pile. A
Gestion LIFO
LIFO : Last In First Out
La dernière donnée entrée est la
première à sortir.
Analogie avec une pile d’objets.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 128
128
VIII. Structures de données dynamiques
3.2. Applications des piles Calcul arithmétique
Appels de fonctions Une application courante des piles se
fait dans le calcul arithmétique :
Quand une fonction est appelée, les
l'ordre dans la pile permet d'éviter
paramètres (incluant l’adresse de
l'usage des parenthèses.
retour) doivent être passés à la
La notation postfixée (polonaise)
fonction appelante.
consiste à placer les opérandes
Si ces paramètres sont sauvegardés
devant l'opérateur.
dans une mémoire fixe, alors la
La notation infixée (parenthésée)
fonction ne peut pas être appelée
récursivement du moment que la consiste à entourer les opérateurs par
première adresse va être écrasée par leurs opérandes.
le deuxième retour d’adresse avant Exemple :
que la première ne soit utilisée. Notation infixée : (3+5)*2.
Les piles sont souvent nécessaires Nécessiter l'utilisation de parenthèses
pour rendre itératif un algorithme pour éviter toute ambiguïté :
récursif. 3+(5*2).
Notation postfixée : (3+5 *2 s'écrira :
35+2*
INP-HB/DFRMI/K. M. BROU Langage algorithmique 3 + (5 * 2) s'écrira
129 :352*+
129
VIII. Structures de données dynamiques
Propriétés :
3.3. Spécification fonctionnelle
Soient p : PileT et x :T
Soit le type PileT, ou pile d’objets de
type T pileVide(creerPile) = VRAI creerPile crée une pile vide.
pileVide(empiler(p, x)) = FAUX si on ajoute un élt à une pile, la
Opérateurs : pile résultante n’est pas vide.
depiler(empiler(p, x),x) = p si on ajoute un élt et on l’enlève,
creerPile : PileT Crée une pile vide
on retrouve la pile initiale.
pileVide : PileT BOOLEEN Teste si la pile est vide ou
dernier(empiler(p, x)) = x on récupère les élts dans l’ordre
non
inverse de celui où on les a mis.
empiler : PileT T PileT Ajoute un élément au
sommet de la pile
depiler : PileT T PileT Supprime l’élément au
sommet de la pile
dernier : PileT T Retourne le sommet de la
pile
INP-HB/DFRMI/K. M. BROU Langage algorithmique 130
130
VIII. Structures de données dynamiques
3.4. Description logique
TYPE
Sommet : élément le plus récent Pile = VIDE | PileNonVide
d’une pile. PileNonVide = ENREGISTREMENT
Corps : la pile amputée du sommet. sommet : T
corps : Pile
FIN
Nouveau
sommet
Nouvelle
pile Nouveau Ancienne
corps Ancien pile
corps
INP-HB/DFRMI/K. M. BROU Langage algorithmique 131
131
VIII. Structures de données dynamiques
Les fonctions
FONCTION creerPile : Pile FONCTION depiler(DR p : Pile) : Pile
DEBUT DEBUT
creerPile VIDE SI(pileVide(p)) ALORS
FIN Erreur
SINON
FONCTION pileVide(p :Pile) :BOOLEEN depiler corps(p)
DEBUT FIN
pileVide p = VIDE
FIN FONCTION dernier(D p : Pile) : T
DEBUT)
FONCTION empiler(DR p : Pile ; x : REEL) : Pile SI(pileVide(p)) ALORS
DEBUT Erreur
SI(NON pileVide(p)) ALORS SINON
empiler(p.corps, p.sommet) dernier p.sommet
p.sommet x FIN
empiler p
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 132
132
VIII. Structures de données dynamiques
3.5. Représentation physique Représentation chaînée
Deux représentations physiques :
Représentation contiguë (Tableau) :
tête A
éléments de la pile rangés de façon
pile
contiguë ; tête B
Représentation chaînée (pointeurs) : corps tête C
corps
élément de la pile rangés à des corps tête D queue
endroits quelconques corps vide
Représentation contiguë
tête A
B
pile
corps
C
D
INP-HB/DFRMI/K. M. BROU Langage algorithmique 133
133
VIII. Structures de données dynamiques
Mise en œuvre d’une pile par tableau Exemple
1
file[1] tête 0 0 0 0 0 enpiler
Partie file[2] t, q 1 2 3 0 0
utilisée queue 1 2 3 t q
I= 0
dépiler I= 3
pile = ()
Partie pile = (1, 2, 3)
inutilisée
1 2 3 0 0 enpiler 1 2 3 6 9
N t q t q
6 9 11
I= 2
I= 5
pile = (2, 3)
pile = (2, 3, 6, 9)
INP-HB/DFRMI/K. M. BROU Langage algorithmique 134
134
VIII. Structures de données dynamiques
TYPE PROCEDURE erreur FONCTION depiler(RD p : Pile) : Pile
Iindice = 1..N DEBUT DEBUT
Vecteur = TABLEAU[Indice] DE T ECRIRE(‘Erreur’) SI(pileVide(p)) ALORS (* pile vide *)
Pile = ENREGISTREMENT FIN erreur
sommet :ENTIER SINON
t : Vecteur FONCTION empiler(RD p : Pile ; x :T) : Pile p.sommet p.sommet - 1
FIN DEBUT dépiler p
SI(p.sommet = N) ALORS (* pile pleine *) FIN
FONCTION creerPile : Pile erreur
VAR p : Pile SINON FONCTION dernier(p : Pile) : T
DEBUT DEBUT DEBUT
p.sommet 0 p.sommet p.sommet + 1 SI(pileVide(p)) ALORS (* pile pleine *)
creerPile p p.t[p.sommet] x erreur
FIN FIN SINON
empiler p dernier p.t[p.sommet]
FONCTION pileVide(p : Pile) :BOOLEEN FIN FIN
DEBUT
SI(p.sommet = 0) ALORS
pileVide VRAI
SINON
pileVide FAUX
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 135
135
VIII. Structures de données dynamiques
Mise en œuvre d’une pile par une
représentation chaînée
sommet suivant
nbElt infoN infoN-1 info1
tête Pile
Chaque donnée de la pile contient une
valeur et un pointeur sur la donnée
précédemment empilée.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 136
136
VIII. Structures de données dynamiques
TYPE FONCTION pileVide(p : PtrTete) : BOOLEEN FONCTION dépiler(RD p : ptrTête) : ptrTête
PtrPile = Pile DEBUT VAR ptr :PtrPile
PtrTete = TETE SI((P.nbElt = 0) OU (p.sommet=NUL)) ALORS DEBUT
pileVide VRAI SI(pile_vide(p)) ALORS
TETE = ENREGISTREMENT SINON erreur
nbElt : ENTIER pileVide FAUX SINON
sommet : PtrPile FIN DEBUT
FIN ptr p.sommet
FONCTION empiler(RD p:ptrTête ; x:T) : ptrTête p.sommet ptr.suivant
Pile = ENREGISTREMENT VAR ptr :PtrPile p.nbElt p.nbElt - 1
info :T DEBUT LIBERER(ptr)
suivant :PtrPile RESERVER(ptr) FIN
FIN ptr.info x dépiler p
ptr.suivant p.sommet FIN
p.sommet ptr
p.nbElt p.nbElt + 1
empiler p
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 137
137
VIII. Structures de données dynamiques
FONCTION dernier(p : ptrTête) : T PROCEDURE lire(RD p : ptrTête) PROCEDURE afficher(p) Exécution
DEBUT VAR fini :BOOLEEN VAR n : ENTIER
SI(pile_vide(p)) ALORS i :ENTIER ptr : PtrPile ALGORITHME stack
erreur rep :CAR DEBUT VAR p :PtrPile
SINON DEBUT n p.nbElt DEBUT
dernier p.sommet.info fini FAUX ptr p.sommet p créerPile
FIN i1 ECRIRE(‘Nombre d’’élément=‘, n) lire(p)
TANTQUE(NON fini) TANTQUE(n > 0) (ou ptr NUL) afficher(p)
FONCTION creerPile : ptrTête DEBUT DEBUT ECRIRE(dernier(p))
Var p : ptrTête ECRIRE(‘Entrez x’, i) ECRIRE(ptr.info) p dépiler
DEBUT LIRE(x) ptr ptr.suivant afficher(p)
RESERVER(p) P empileR(p,x) nn-1 FIN
p.nbElt 0 ECRIRE(‘Nouvelle info O/N :’) FIN
p.sommet NUL LIRE(rep) FIN
creerPile p SI(rep = ‘N’) ALORS
FIN fini VRAI
SINON
i i+1
FIN
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 138
138
VIII. Structures de données dynamiques
Exercices :
Exercice 1 : Ecrire un algorithme de
conversion d’un nombre N dans une
base B quelconque.
par un tableau
par une structure chaînée
Exercice 2 : Ecrire un algorithme
permettant de gérer une pile
d’élèves :
par un tableau
par une structure chaînée
INP-HB/DFRMI/K. M. BROU Langage algorithmique 139
139
VIII. Structures de données dynamiques
4.1. Les files Application :
Définition File d’attente devant une caisse de
supermarché.
Une file est une structure à une tête de
File d’attente d’une imprimante.
lecture et une tête d’écriture, accès
séquentiel.
Sa gestion est telle que la première
information entrée est la première à
sortir(FIFO : Fist In Fist Out).
Analogie avec une file d’attente devant
un guichet.
Ajout Retrait
D C B A
queue tête
INP-HB/DFRMI/K. M. BROU Langage algorithmique 140
140
VIII. Structures de données dynamiques
4.2. Spécification fonctionnelle
Soit le type FileT, ou file d’objets de
type T
Opérateurs :
creerFile : FileT Crée un file vide
fileVide : FileT BOOLEEN Teste si la file est vide ou non
enfiler : FileT T FileT Ajoute un élément à la queue
de la file
defiler : FileT T FileT Supprime le premier de la file
premier : FileT T Retourne le premier de la file
Propriétés :
Soient f : FileT et x :T
filevide(créerfile)=VRAI creerFile crée une file vide.
fileVide(enfiler(f, x))=FAUX si on ajoute un élément à une file, la
file résultante n’est pas vide.
defiler(enfiler(f, x),x)=f si on ajoute un élément et on
l’enlève, on retrouve la file initiale.
premier(enfiler(f, x))=x on récupère les éléments dans l’ordre
de celui où on les a mis.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 141
141
VIII. Structures de données dynamiques
3.4. Description logique
Sommet : le premier élément d’une TYPE
file. File = VIDE | FileNonVide
FileNonVide = ENREGISTREMENT
Corps : la file amputée du sommet. tete : T
corps : File
tête FIN
Ancienne Ancien
file corps
Nouveau Nouvelle
corps file
Nouvelle
queue
INP-HB/DFRMI/K. M. BROU Langage algorithmique 142
142
VIII. Structures de données dynamiques
Les fonctions
FONCTION defiler(DR f : file) : file
FONCTION creerFile : File DEBUT
DEBUT SI(fileVide(f)) ALORS
creerFile VIDE Erreur
FIN SINON
f f.corps
FONCTION fileVide(f :File) :BOOLEEN defiler f.corps
DEBUT FIN
fileVide f = VIDE
FIN FONCTION premier(D f : file) : T
DEBUT)
FONCTION enfiler(DR f : file ; x : REEL) : File SI(fileVide(f)) ALORS
DEBUT Erreur
SI(fileVide(f)) ALORS SINON
f.tete x premier f.tete
SINON FIN
enfiler File(enfiler(f.Corps, x), f.tete)
enfiler f
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 143
143
VIII. Structures de données dynamiques
3.5. Représentation physique Représentation contiguë
Deux représentations physiques : sommet A
Représentation contiguë (Tableau) : B
éléments de la pile rangés de façon pile
corps
C
contiguë ;
D
Représentation chaînée (pointeurs) :
élément de la pile rangés à des
endroits quelconques. Représentation chaînée
sommet
A
pile sommet B
corps
sommet C
corps
sommet D
corps
corps vide
INP-HB/DFRMI/K. M. BROU Langage algorithmique 144
144
VIII. Structures de données dynamiques
Représentations contiguë FONCTION défiler(F : FileAt) : FileAt
DEBUT
CONST N = 10 FONCTION fileVide(f : FileAt) : BOOLEEN SI(fileVide(F)) ALORS
TYPE DEBUT erreur
Taille = 1..N SI(f.tête = f.queue) ALORS SINON
vecteur = TABLEAU[Taille] DE T fileVide VRAI f.tete f.tete + 1
SINON FIN
FileAt = ENREGISTREMENT fileVide FAUX
tab : vecteur FIN FONCTION enfiler(f : FileAt ; x : T) : FileAt
tete :Taille DEBUT
queue :Taille FONCTION premier(f : FileAt) :T SI(f.queue > N) ALORS
FIN DEBUT erreur
SI(fileVide(f)) ALORS SINON
FONCTION creerFile : FileAt erreur DEBUT
VAR f : FileAt SINON fF.tab[f.queue] x
DEBUT premier f.tab[f.tete] f.queue f.queue + 1
f.tete 1 FIN FIN
f.queue 1 FIN
creerFile f
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 145
145
VIII. Structures de données dynamiques
Représentations chaînée
TYPE
queue PtrFile = Cellule
PtrTete = FileAt
tete suivant
nbElt info1 info2 infoN
FileAt = ENREGISTREMENT
nbElt : ENTIER
f File tete :PtrFile
queue :PtrFile
FIN
Cellule = ENREGISTREMENT
info :T
suivant :PtrFile
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 146
146
VIII. Structures de données dynamiques
FONCTION creerFile: PtrFile FONCTION enfiler(f : PtrFile ; x) : PtrFile FONCTION défiler(f : PtrFile) : PtrFile
VAR F : Ptr_File VAR fp :PtrFile VAR fp : PtrFile
DEBUT DEBUT DEBUT
RESERVER(F) F.longueur f.longueur + 1 SI(fileVide(f)) ALORS
f.longueur 0 RESERVER(fp) erreur
F.tête NUL fp.info x SINON
f.queue NUL SI(f.queue = NUL) ALORS DEBUT
creerFile f DEBUT fp. f.tete
FIN fp.suivant f.tete f.tete fp.suivant
FONCTION fileVide(f:PtrFile) :BOOLEEN f.tete fp LIBERER(fp)
DEBUT f.queue fp FIN
SI(f.queue = f.tête) ALORS FIN SI(f.nbElt =1) ALORS
fileVide VRAI SINON f.queue NUL
SINON DEBUT défiler f
fileVide FAUX fp.suivant f.queue.suivant FIN
FIN f.queue.suivant fp
FONCTION premier(f:PtrFile) :T f.queue fp
DEBUT FIN
SI(fileVide(F)) ALORS enfiler f
erreur FIN
SINON
premier f.tete.info]
FIN
INP-HB/DFRMI/K. M. BROU Langage algorithmique 147
147
VIII. Structures de données dynamiques
5.1. Les listes
Ensemble ordonné et extensible
d’éléments de même type auxquels
on accède séquentiellement, et où
l’on d’insérer ou d’enlever un élément
à n’importe quel niveau de la
structure.
Généralisation des Piles et des Files.
Exemple :
L = (l1, l2…ln)
Liste d’élèves…
INP-HB/DFRMI/K. M. BROU Langage algorithmique 148
148
VIII. Structures de données dynamiques
5.2. Spécification fonctionnelle
Soit une liste d’objets de type T
Opérations
creerListe : Liste
suivant : T Liste T
insérerAvant : T T Liste Liste
supprimer : T Liste Liste
premier : Liste T
INP-HB/DFRMI/K. M. BROU Langage algorithmique 149
149
VIII. Structures de données dynamiques
5.3. Description logique
Une liste peut être vide ou non ;
une liste non vide peut être
décomposée en deux parties :
Début de liste
Reste de la liste.
INP-HB/DFRMI/K. M. BROU Langage algorithmique 150
150
Bibliographie
Livres [MEY] : "Méthodes de
[ALR] : "Structure de données et programmation", B. Meyer et C
algorithmes", Alfred Ano, John Baudoin, Eyrolles
Hopcroft, Jeffrey Ullman, InterEdition Christine PORQUET : ENSICAEN -
[BOR ] : "Initiation à la 1ère année – 2nd semestre –
programmation", Collection Sciences Algorithmique avancée :
et pratique de l’informatique, Bordas Poly_Algo_avancee_debut.pdf
Informatique
[COU] : "Initiation à l’algorithmique
et aux structures de données, 1, 2
Récursivité et structures de données
avancées", J. Courtin, I. Kowarski,
Dunod Informatique
[GUY] : "Arbre Table et Algorithmes",
J. Guyot, C. Vial, Eyrolles
INP-HB/DFRMI/K. M. BROU Langage algorithmique 151
151
Bibliographie
Webographie
http://brassens.upmf-
grenoble.fr/IMSS/limass/algoprog/al
gocours.html
http://www-math.univ-
fcomte.fr/pp_Annu/FLANGROGNET/E
NSEIGNEMENT/Hachage_2007.pdf
http://aqualonne.free.fr/dossiers/al
go5.html
Christine PORQUET : ENSICAEN - 1ère
année – 2nd semestre –
Algorithmique avancée :
Poly_Algo_avancee_debut.pdf
http://email.ini.dz/~hidouci/mcp/3_
Divise_Resoudre.pdf
INP-HB/DFRMI/K. M. BROU Langage algorithmique 152
152
Vous aimerez peut-être aussi
- Introduction à l'Algorithmique et CPas encore d'évaluationIntroduction à l'Algorithmique et C97 pages
- Cours Algorithmique et Programmation CPas encore d'évaluationCours Algorithmique et Programmation C59 pages
- Introduction à l'Algorithmique et PythonPas encore d'évaluationIntroduction à l'Algorithmique et Python100 pages
- Cours Complet Algorithmique Et Programmation en Python 2024-2025Pas encore d'évaluationCours Complet Algorithmique Et Programmation en Python 2024-2025223 pages
- Cours Algo Et Prog Chap1 Jusqu'au Slide 95Pas encore d'évaluationCours Algo Et Prog Chap1 Jusqu'au Slide 9595 pages
- Cours Algorithmique Et Programmation Python Jusqu'Aux FonctionsPas encore d'évaluationCours Algorithmique Et Programmation Python Jusqu'Aux Fonctions187 pages
- Cours Algorithmique Et Programmation - Chapitre 0Pas encore d'évaluationCours Algorithmique Et Programmation - Chapitre 046 pages
- Initiation Algorithmique L1 Partie1Pas encore d'évaluationInitiation Algorithmique L1 Partie121 pages
- Notes de Cours D'algorithmique Et Méthodes de ProgrammationPas encore d'évaluationNotes de Cours D'algorithmique Et Méthodes de Programmation68 pages
- Introduction à l'algorithmique et variablesPas encore d'évaluationIntroduction à l'algorithmique et variables98 pages
- Introduction à l'algorithmique en informatiquePas encore d'évaluationIntroduction à l'algorithmique en informatique69 pages
- Introduction à l'algorithmique LIFAP1Pas encore d'évaluationIntroduction à l'algorithmique LIFAP159 pages
- LIF: Lgorithmique ET Rogrammation Mpérative, Initiation: Licence STS Université Claude Bernard Lyon IPas encore d'évaluationLIF: Lgorithmique ET Rogrammation Mpérative, Initiation: Licence STS Université Claude Bernard Lyon I66 pages
- Chapitre 1 de L'algorithmique Vers La Programmation 1Pas encore d'évaluationChapitre 1 de L'algorithmique Vers La Programmation 113 pages
- Introduction à l'Algorithmique et ProgrammationPas encore d'évaluationIntroduction à l'Algorithmique et Programmation71 pages
- Etapes Developpement Programme Informatique100% (1)Etapes Developpement Programme Informatique2 pages
- 1.Support-cours-Programmation en Langage C - 2020Pas encore d'évaluation1.Support-cours-Programmation en Langage C - 202054 pages
- Chap1 - Intro - Algorithmique - DR BOULOU KDGPas encore d'évaluationChap1 - Intro - Algorithmique - DR BOULOU KDG29 pages
- Cours d'Initiation à l'InformatiquePas encore d'évaluationCours d'Initiation à l'Informatique32 pages
- Chapitre 1 - Introduction À La Programmation100% (1)Chapitre 1 - Introduction À La Programmation1 page
- Introduction aux Langages de Programmation et AlgorithmesPas encore d'évaluationIntroduction aux Langages de Programmation et Algorithmes67 pages
- Cours IUP - 01 Algorithmique Et ProgrammationPas encore d'évaluationCours IUP - 01 Algorithmique Et Programmation9 pages
- Probabilités, Analyse de Données Et Statistiques (WWW - Bibliodunet.com)100% (24)Probabilités, Analyse de Données Et Statistiques (WWW - Bibliodunet.com)631 pages
- NIJDAM, Christophe - La Finance Pour Les Nuls en 50 Notions Clés (2019, Edi8) - Libgen - Li100% (7)NIJDAM, Christophe - La Finance Pour Les Nuls en 50 Notions Clés (2019, Edi8) - Libgen - Li340 pages
- Guide de lIA Generative de Sousa Cardoso Cyril Parise Fanny Cyril de Sousa Cardoso Fanny Parise92% (13)Guide de lIA Generative de Sousa Cardoso Cyril Parise Fanny Cyril de Sousa Cardoso Fanny Parise295 pages
- Mathématiques Financières - Cours Et Exerces Corrigés95% (150)Mathématiques Financières - Cours Et Exerces Corrigés310 pages
- David R. Anderson, Dennis J. Sweeney, Thomas A. Williams - Statistiques Pour L'économie Et La Gestion (2015, DeBoeck)100% (4)David R. Anderson, Dennis J. Sweeney, Thomas A. Williams - Statistiques Pour L'économie Et La Gestion (2015, DeBoeck)946 pages
- Arretez D Oublier Ce Que Vous Lisez Eliott Meunier95% (21)Arretez D Oublier Ce Que Vous Lisez Eliott Meunier201 pages
- Grandes théories économiques en 50 notions100% (5)Grandes théories économiques en 50 notions301 pages
- La Boîte À Outils de L'analyse de Données en Entreprise (Clotilde Coron)100% (11)La Boîte À Outils de L'analyse de Données en Entreprise (Clotilde Coron)341 pages
- La Boîte À Outils Pour Prendre La Parole en Public Annie Leibovitz 2020 Dunod100% (11)La Boîte À Outils Pour Prendre La Parole en Public Annie Leibovitz 2020 Dunod358 pages
- Statistique Et Data Science Avec R by François Husson100% (6)Statistique Et Data Science Avec R by François Husson429 pages
- Lessentiel de Statistique Descriptive by Elisabeth OLIVIER100% (10)Lessentiel de Statistique Descriptive by Elisabeth OLIVIER197 pages
- Cinq Coups Davance (Patrick Bet-David) (Z-Library)89% (18)Cinq Coups Davance (Patrick Bet-David) (Z-Library)321 pages
- Initiation A La Statistique Avec R - @CahiersJaunes PDF100% (2)Initiation A La Statistique Avec R - @CahiersJaunes PDF456 pages
- Techniques Interdites de Manipulation Mentale Robert Mercier Z Library100% (13)Techniques Interdites de Manipulation Mentale Robert Mercier Z Library117 pages
- La Boite A Outils Pour Animer V - Florence Gillet-Goinard100% (11)La Boite A Outils Pour Animer V - Florence Gillet-Goinard364 pages
- Contrôleur Financier Commercial à AbidjanPas encore d'évaluationContrôleur Financier Commercial à Abidjan1 page
- Kit de Planification Stratégique Pour Les EntreprisesPas encore d'évaluationKit de Planification Stratégique Pour Les Entreprises14 pages
- Analysez Et Gérez Des Risques SI - PDFPas encore d'évaluationAnalysez Et Gérez Des Risques SI - PDF36 pages
- COMPTA STES L3 2019 Selon SYSCOHADA REVISEPas encore d'évaluationCOMPTA STES L3 2019 Selon SYSCOHADA REVISE49 pages
- Lycee Classique D'Edea: Minesec 03.10.2017 EXAMEN Sequence #1 Durée: 3h Classe: C Coeff. 5 Epreuve MathematiquesPas encore d'évaluationLycee Classique D'Edea: Minesec 03.10.2017 EXAMEN Sequence #1 Durée: 3h Classe: C Coeff. 5 Epreuve Mathematiques2 pages
- Analyse Statistique avec STATA pour L3 EcoPas encore d'évaluationAnalyse Statistique avec STATA pour L3 Eco2 pages
- Licence Finance d'Entreprise 2014-2015Pas encore d'évaluationLicence Finance d'Entreprise 2014-201587 pages
- Ooreka Lettre Motivation Stage Cabinet AvocatsPas encore d'évaluationOoreka Lettre Motivation Stage Cabinet Avocats3 pages
- Rapport D'activite - Parc Industriel Afz 2023Pas encore d'évaluationRapport D'activite - Parc Industriel Afz 202346 pages
- Cours Complet Archi Ordi - ESI - 2025Pas encore d'évaluationCours Complet Archi Ordi - ESI - 202571 pages
- Applications Des Microprocesseurs Et MicrocontroleursPas encore d'évaluationApplications Des Microprocesseurs Et Microcontroleurs21 pages
- Fonctionnement des Registres NumériquesPas encore d'évaluationFonctionnement des Registres Numériques6 pages
- Devis pour Electrification ComplètePas encore d'évaluationDevis pour Electrification Complète2 pages
- Robert Greene - Stratégie - Les 33 Lois de La Guerre - PDF - Stratégie Militaire - AthénaPas encore d'évaluationRobert Greene - Stratégie - Les 33 Lois de La Guerre - PDF - Stratégie Militaire - Athéna494 pages
- Beep Error Code - LENOVO - Toutes Les Idea Pad LaptopsPas encore d'évaluationBeep Error Code - LENOVO - Toutes Les Idea Pad Laptops3 pages
- Magrez MEMOIRE M2 GIDE Ludivine MagrezPas encore d'évaluationMagrez MEMOIRE M2 GIDE Ludivine Magrez107 pages
- Simulation Sous GNS3 D'une Solution Réseau100% (1)Simulation Sous GNS3 D'une Solution Réseau11 pages
- OceanofPDF Com The Mental Game of Trading Jared Tendler FR PDF57% (7)OceanofPDF Com The Mental Game of Trading Jared Tendler FR PDF549 pages
