Chapitre 8- Algorithmique

ALGORITHMIQUE

rg
A
CHAPITRE 8: ALGORITHMIQUE L
G

.o
 Leçon 1: Notions d’algorithmique
O
of R
I
 Leçon 2: Les éléments de bases et les instructions
simples
T
pr
H
 Leçon 3: Les structures de contrôles M
I
d

 Exercices et corrigés
Q
an

U
E
gr

[Link] 1
 Chapitre 8- Algorithmique

Notions d’algorithmique
Compétences visées
 Définir algorithme et donner les propriétés d'un bon algorithme
 Identifier les étapes de résolution d'un problème
 Identifier les données, les traitements et les résultats d'un problème d onné

rg
A Introduction
Le mot « algorithme » vient du nom de l’auteur persan Al-Khawarizmi (né
L vers 780 - mort vers 850) qui a écrit en langue arabe le plus ancien traité d’algèbre «
G abrégé de calcul par la complétion et la simplification » dans lequel il décrivait des

.o
O procédés de calcul à suivre étape par étape pour résoudre des pro blèmes ramenés à
R des équations. On trouve des algorithmes dans des situations de la vie courante
of
(cuisiner, se vêtir) ou professionnelle (la conduite d’un train, la consultation d’un
I catalogue de bibliothèque, etc.).
T
pr
H I Définitions et propriétés
M Un algorithme est une suite finie et ordonnée d’instructions permettant de
I résoudre un problème donné. Le résultat doit donc s’obtenir en un temps fini.
d

L’algorithmique est la science qui étudie les algorithmes

Q Algorigramme : c’est une représentation graphique d’un algorithme. Pour le
an

U construire, on utilise des symboles normalisés.

E Un algorithme doit donc être :
 Compréhensible: car on n'écrit pas un algorithme pour soit même, mais pour
l'expliquer aux autres.
gr

 Lisible: L’algorithme doit respecter une structure bien définie

 De haut niveau: Il ne doit pas faire appel à des notions techniques relatives à un
langage programme particulier ou bien à un système d'exploitation donné.
 Précis: Chaque élément de l'algorithme ne doit pas porter à confusion, il est donc
important de lever toute ambiguïté
 Structuré: Un algorithme doit être composé de différentes parties facilement
identifiables
2 [Link]
 Chapitre 8- Algorithmique
 Résoudre le problème posé.
 Toujours se terminer.

II Les étapes de résolution d’un algorithme

 Les entrées (ou la déclaration et la saisie des données)
 Le traitement
 Les sorties (ou l’affichage / l’impression des données transformées)

rg
A
II.1 Les entrées L
Il s’agit de repérer les données nécessaires à la résolution du problème. Dans G

.o
cette phase peut aussi figurer ce qu’on appelle l’entrée des données, qui peut se
manifester par la saisie de caractères ou de nombres sur le clavier.
O
Son symbole est of R
I
II.2 Le traitement T
pr
Il s’agit de déterminer toutes les étapes des traitements à faire et donc des H
"instructions" à donner pour une exécution automatique. Si ces instructions
s’exécutent en séquence, on parle d’algorithme séquentiel. Si les opérations
M
I
d

s’exécutent sur plusieurs processeurs en parallèle, on parle d’algorithme parallèle. Si

les taches s’exécutent sur un réseau de processeurs on parle d’algorithme réparti ou Q
an

distribué. Nous ne traiterons ici que des algorithmes séquentiels. U

Son symbole est
E
II.3 Les sorties
gr

Les résultats obtenus peuvent être affichés sur l’écran, ou imprimés sur papier,
ou bien encore conservés dans un fichier.
Son symbole est le même que pour l’entrée

III Langage et règles d’écriture d’un algorithme

Un algorithme peut être écrit en utilisant un langage de description
d’algorithme (LDA). Ce langage utilise un ensemble de mots clés et de structures
[Link] 3
 Chapitre 8- Algorithmique
permettant de décrire de manière complète et claire l’ensemble des opérations à
exécuter sur des données pour obtenir des résultats. Un tel langage présente un réel
avantage, celui de pouvoir être transcrit dans un langage de programmation structuré
et lisible. Il ne faut donc pas confondre algorithme et programme.

IV Structure générale d’un algorithme

L’entête Algorithme Nom de l’algorithme

rg
A Les déclaration des constantes et variables {𝑪𝒐𝒏𝒔𝒕𝒂𝒏𝒕𝒆𝒔 ∶ 𝐿𝑖𝑠𝑡𝑒 𝑑𝑒𝑠 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒𝑠
𝑽𝒂𝒓𝒊𝒂𝒃𝒍𝒆𝒔: 𝐿𝑖𝑠𝑡𝑒 𝑑𝑒𝑠 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠
L
𝑫𝒆𝒃𝒖𝒕
G

.o
𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 1
𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 2
O Le corps de l’algorithme
…
𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑛
R of { 𝑭𝒊𝒏
I  L‘en-tête permet tout simplement d‘identifier un algorithme par un nom. Ce
T nom n’influence en rien le bon déroulement de l’algorithme. En général il faut donner
pr
H des noms parlants à nos algorithmes, ceci pour permettre au lecteur d’avoir une idée
M de ce que fera l’algorithme;
 Les déclarations de constantes, variables, structures sont une liste exhaustive
I
d

des objets ou des données utilisés et manipulés dans le corps de l‘algorithme.

Q  Le corps de l‘algorithme contient les tâches (instructions, opérations) à
an

U exécuter. Ces tâches peuvent être des appels de fonction ou des instructions simples
E Le symbole de début et fin est
Dans un LDA, certains mots sont réservés pour un usage bien défini. On
gr

les nomme les mots clés. Ce sont les mots que le langage utilise pour son
fonctionnement. Dans notre langage de définition les mots clés commenceront
toujours par une majuscule et seront soulignés.

4 [Link]
 Chapitre 8- Algorithmique

Les éléments de base et les instructions simples

Compétences visées
 Définir type, opérateur, constante, variable
 Identifier les types de base et les opérateurs de base
 Donner la différence entre une constante et une variable
 Donner les conventions de nommage des constantes et des variables

rg
 Définir : instruction, affectation, écriture, lecture A
 Donner le rôle de chaque instruction dans un algorithme L
 Exécuter un algorithme à la main G

.o
O
of R
A. Les éléments de base I
I Types de base T
pr
Un type de base est un type primitif, c'est-à-dire non décomposable H
pour le problème considéré. Les types de bases à utiliser dépendent du problème à
M
résoudre. Le type définit plusieurs choses :
I
d

On distingue cinq principaux types qui sont :

 Le type entier : Le type entier ne peuvent accepter que les entiers relatifs, c'est -à- Q
an

dire 45; 50; -567 U

 Le type réel : Ce type utilise les nombres réels. Ce type accepte les entiers d’autant E
plus qu’un entier est aussi un réel. On peut donc avoir : -3.67 ; 4.23578
 Le type booléen : type booléen ne peut prendre que deux valeurs : Vrai ou Faux
gr

 Le type caractère : ce type n’accepte qu’un seul caractère alphabétique. Les

caractères avec accent, les caractères spéciaux ne sont pas permis et leur utilisation
dans ce cas de figure sera considéré comme erreur. Nous pouvons donc avoir entre
autre ‘a’ ; ‘A’; NB: les caractères seront notés entre une côte.
 Le type chaîne de caractères : ce type accepte plusieurs caractères.
NB: les chaînes de caractères seront notées entre double côtes.
Exemple : "électronique"

[Link] 5
 Chapitre 8- Algorithmique

II Opérandes et operateurs
1 Définitions
Un operateur est un outil qui permet d’agir sur une variable ou d’effectuer des
calculs.
Un opérande est une donnée utilisée par un opérateur.
Exemple : Dans «7-x», «-» désigne l’opérateur ; «7» et «x» sont les opérandes
2 Types d’operateurs

rg
A Il existe plusieurs types d’opérateurs :
L  Les opérateurs arithmétiques qui permettent d’effectuer des opérations
arithmétiques entre opérandes numériques :
G

.o
 Opérateurs élémentaires : «+», «-», «X», «/», «DIV» (division entière)
O  Changement de signe : «-»
R  Élévation à la puissance : «^»
of
I  Reste d’une division entière : «modulo» (ou «%»)
T  Les opérateurs de comparaison («=», «#», «>», «<», «≤» et «≥») qui
pr
H permettent de comparer deux opérandes et produisent une valeur booléenne, en
s’appuyant sur des relations d’ordre :
M
 Ordre naturel pour les entiers et les réels
I
d

 Ordre lexicographique ASCII pour les chaînes de caractère

Q  Les opérateurs logiques qui combinent des opérandes booléens pour former des
an

U expressions logiques plus complexes :

E  Opérateur unaire : «non» (négation)
 Opérateurs binaires : «et» (conjonction), «ou» (disjonction),
gr

 L’opérateur d’affectation, représenté par le symbole ←, qui confère une valeur à

une variable ou à une constante.

III Constantes et variables

Les constantes et les variables sont des éléments fondamentaux,
indispensables au bon déroulement d’un algorithme, caractérisés par un
identificateur, une valeur et un type.

6 [Link]
 Chapitre 8- Algorithmique

1 Définitions
Une variable est une donnée (emplacement) stockée dans la mémoire de
l’ordinateur. Elle est repérée par un identificateur (nom de la variable constitué
de lettres et/ou de chiffres, sans espace) et contient une valeur dont le type
(nature de la variable) peut être un entier, un réel, un booléen, un caractère, une
chaîne de caractères… Il ne faut pas confondre constante et variable.
Une constante, comme une variable, peut représenter un chiffre, un
nombre, un caractère, une chaîne de caractères, un booléen. Toutefois,

rg
contrairement à une variable dont la valeur peut être modifiée au cours de A
l’exécution de l’algorithme, la valeur d’une constante ne varie pas. L
Remarque : G

.o
 Le type d’une variable détermine l’ensemble des valeurs qu’elle peut prendre
et les opérations réalisables qu’elle peut subir.
O
 L’utilisation d’une variable doit être précédée de sa déclaration.
of R
 Si la valeur de la variable peut changer au cours du déroulement de I
l’algorithme, en revanche son type est figé lors de déclaration. T
pr
La syntaxe pour déclarer une variable est la suivante : H
variable ou var Nom de la variable : type de la variable
M
Exemple : variable moyenne : reel var a : entier
I
d

La syntaxe pour déclarer une constante est la suivante :

constante ou const Nom de la constante = valeur Q
an

Exemple : constante pi=3,14 const sexe=’M’ U

E
2 Conventions de nommage
Le nom d’un algorithme, d’une variable ou d’une constante doit respecter les
gr

règles suivantes:
 commencer par une lettre ;
 ne comporter ni caractère spécial (comme l’espace) ni ponctuation
 ne pas être un mot du langage algorithmique (comme « algorithme »,
« début », « fin », « variable », « non », « ou », « et », « si », « sinon », «
pour »…)

[Link] 7
 Chapitre 8- Algorithmique

2. Les instructions simples

Une instruction est un ordre qui permet de spécifier à la machine l’action à
effectuer.
On distingue plusieurs types d’instructions : les instructions simples et les
structures de contrôle.
Parmi les instructions simples on a :
- L’instruction d’affectation
- L’instruction de lecture

rg
A - L’instruction d’écriture
L a Affectation
G L’instruction d’affectation permet d’attribuer une valeur à une variable.

.o
Cette instruction signifie : « identificateur prend valeur » noté « identificateur
O valeur »
R La syntaxe générale est la suivante : NomVariable ←Expression ;
of
I « Expression » peut être :
T une constante. ..........................................................................Ex : surface ← 40
pr
H une autre variable. .........................................…........Ex : Variable1 ←Variable2
le résultat d’une fonction. ............................Ex : resultat ← racine (nombre)
M
un calcul portant sur différents éléments. .……... Ex : S← (PI *D*D/ 4)
I
d

Après l’affectation, le contenu de « variable » est modifié. Il contient

Q désormais, la valeur de l’expression de droite. Son mode de fonctionnement est le
an

U suivant : On évalue d’abord l’expression de droite avant de l’affecter à « variable ».

E Exemple N←5 c’est-à-dire N prend la valeur de 5.N contient désormais la valeur 5
Exemple 1 Corrigé
gr

Donner les valeurs finales de A, B, et C Après la valeur des variables est :

Variables
A, B, C : Entier A = ? B = ? C = ?
Début
A ←5 ;
A = 5 B = ? C = ?
B ←3 ;
A = 5 B = 3 C = ?
C ←A + B ;
A = 5 B = 3 C = 8
2.1 Enregistrement
A ←2 ;graphique A = 2 B = 3 C = 8
C ←B – A ; A =2 B =3 C =1
Fin

8 [Link]
 Chapitre 8- Algorithmique
b I nstruction d’écriture
Cette instruction permet d’effectuer l’affichage un message à l’écran.
 Mot clé: ecrire ou afficher
 Syntaxe: ecrire(‘expression’). Expression sera affiché tel quel à l’écran.
Exemple: ecrire (‘entrer votre nom’) ; afficher (‘Bonjour à tous’)
Exemple 2 Corrigé
Quel résultat produit le programme On verra apparaître à l’écran 4,

rg
suivant ? puis 16 (qui vaut 4^2) A
Variables
val, carre :reel L
Début
G

.o
val ← 4 ;
carre ← Val^2 ; O
Ecrire (Val) ; 4
Ecrire (carre) ; of 16
R
Fin
*
I
Le symbole de l’écriture ou affichage est : T
pr
Exemple : Algorigramme de ecrire (‘[Link]’) H
M
c I nstruction de lecture I
d

Cette instruction permet d’entrer une donnée à partir du clavier. La machine attend
que l’utilisateur tape une valeur au clavier. Q
an

 Mot clé: lire ou saisir U

 Syntaxe: lire(nom_variable) (nom_variable étant une variable d’un type E
déclaré à l’avance).
gr

Remarque
Avant de Lire une variable, il est très fortement conseillé d’écrire des libellés à
l’écran, afin de prévenir l’utilisateur de ce qu’il doit frappe
Exemple 3
Écrire un algorithme qui demande un nombre entier à l’utilisateur, puis qui calcule
et affiche le double de ce nombre.

[Link] 9
 Chapitre 8- Algorithmique

Corrigé
Variables
nb, carre : Entier
Début
Ecrire("Entrez un nombre :" ) ;
Lire(nb ) ;
double ←2*nb;
Ecrire("Son double est : ", double) ;
Fin

rg
A Le symbole de lecture ou saisir est :
L Exemple : Algorigramme de lire (a) est
G

.o
O
R of
I
T
pr
H
M
I
d

Q
an

U
E
gr

10 [Link]
 Chapitre 8- Algorithmique

Les structures de contrôles

Compétences visées
 Donner les différents types de structures de contrôle.
 Donner la syntaxe de chacune de ces structures
 Choisir la structure de contrôle appropriée pour la résolution d’un problème.

rg
A priori, dans un algorithme les instructions sont exécutées séquentiellement, A
c’est-à-dire dans l’ordre dans laquelle elles apparaissent. Or la puissance et le
«comportement intelligent » d’un algorithme proviennent essentiellement : L
G

.o
 De la possibilité d’effectuer des choix, c’est-à-dire de se comporter
différemment suivant des circonstances, par exemple en fonction d’une réponse O
d’utilisateur, d’un résultat de calcul...
of R
 De la possibilité d’effectuer des boucles ou itérations, autrement dit de
I
répéter plusieurs fois un ensemble donné d’instructions.
T
pr
En résumé, les opérations élémentaires relatives à la résolution d’un problème, H
peuvent en fonction de leur enchainement, être organisées suivant une famille M
de structures algorithmiques fondamentales : I
d

 Les structures séquentielles ;

 Les structures alternatives ;
Q
an

 Les structures de choix ; U

 Les structures itératives ou répétitives. E

I. Les structures séquentielles

gr

Les structures séquentielles se caractérisent par une suite d’actions à exécuter

successivement dans l’ordre énoncé. Une structure séquentielle peut donc présenter
de la manière suivante :
Début :
instruction 1
instruction 2
instruction n
Fin

[Link] 11
 Chapitre 8- Algorithmique

II. Les structures alternatives

La résolution de certains problèmes nécessite parfois la mise en place d’un test
pour effectuer une tâche :
 si le test est positif, on effectue un certain traitement ;
 sinon, c’est-à-dire si le test est négatif, on effectue un autre traitement.
En algorithmique, on traduit cette structure alternative à l’aide d’instructions
conditionnelles.
Une structure alternative est une situation dans laquelle on ne peut choisir

rg
A
qu’entre deux solutions possibles.
L
G a Structure alternative complète (structure si ... Alors ...sinon ...)

.o
O Si condition Alors
R traitement 1 ; (instructions à effectuer si la condition est vérifiée)
of
Sinon
I traitement 2 ; (instructions à effectuer si la condition n’est pas vérifiée)
T FinSi
pr
H
M Lorsque la condition prend la valeur Vrai, alors Traitement1 est exécutée
I et Traitement2 est ignorée. Lorsque la condition prend la valeur Faux, alors
d

Traitement2 est exécutée et Traitement1est ignorée.

Q Remarque : Il existe des conditions simples et des conditions complexes :
an

U  une condition simple peut correspondre à un test d’égalité (A=B ) ou

E d’inégalité (A >B) ;
 une condition complexe est une combinaison logique de conditions
gr

simples (A=B et B<C)

L’algorigramme de la structure alternative complète est :

Application : Écrire un algorithme qui lit un nombre puis

affiche si ce nombre est négatif ou positif.

12 [Link]
 Chapitre 8- Algorithmique
Algorithme Signe
Variables :
x: réel
Début
Ecrire(‘Saisir un nombre‘)
Lire (x)
Si(x < 0)Alors
Ecrire(‘le nombre entré est négatif’)
Sinon
Ecrire (‘le nombre entré est positif’)

rg
FinSi A
Fin
L
G

.o
b Structure alternative réduite (structure si ... Alors ...)
La structure proposée ci-dessus est qualifiée de « complète » mais, selon le O
cas, il se peut que, si la condition n’est pas vérifiée, il n’y ait pas à effectuer de
of R
traitement 2. On écrira ainsi la structure alternative « réduite ». I
Si condition Alors
T
traitement (instructions à effectuer si la condition est vérifiée)
pr
FinSi H
M
c Structures alternatives imbriquées I
d

Plusieurs structures alternatives peuvent être imbriquées, si bien que dans un Q

an

traitement peut (peuvent) figurer une ou plusieurs structure(s) alternative(s).

Pour une meilleure lisibilité de l’algorithme, on utilise l’INDENTATION,
U
qui consiste à écrire les instructions sur des lignes différentes en procédant à des E
décalages.
gr

III. Les structures répétitives

Toutes les structures itératives répètent l’exécution de traitement(s).
Deux cas sont cependant à envisager, selon que :
 le nombre de répétitions est connu à l’avance : c’est le cas des boucles itératives
 le nombre de répétitions n’est pas connu ou est variable : c’est le cas des boucles
conditionnelles.
Nous nous limiterons à la boucle itérative
[Link] 13
 Chapitre 8- Algorithmique

La structure pour … allant de … a …, faire

Cette structure est une boucle itérative ; elle consiste à répéter un certain
traitement un nombre de fois fixé à l’avance. Sa syntaxe est la suivante :
Pour i allant de v1 à v2 pas n faire
Action
Finpour

Remarque

rg
A  La variable i est un compteur, dont la valeur augmente automatiquement
L de 1 à chaque tour. Cette variable permet en définitive de contrôler le nombre
G entier de tours. Cette variable est en d’autres termes la variable de contrôle

.o
d’itération, caractérisée par sa valeur initiale, sa valeur finale et son pas de
O variation.
R  La sortie de la boucle s’effectue lorsque le nombre souhaité d’itérations est
of
I atteint, c’est-à-dire lorsque prend la valeur v2.
T  Le pas peut ne pas être précisé, dans ce cas il est considéré comme valant 1.
pr
H
Son algorigramme est :
M
I
d

Q Exemple :Écrire un algorithme qui calcul le

an

U carré des nombres compris entre 1 et 10.

E Variables
I, c: Entier
gr

Debut
Pour i allant de 1 à 10 faire
c←i*i
ecrire("le carre est." ,c)
Finpour
Fin

14 [Link]