Introduction à l’algorithme

Dr Daouda Traoré

email: daoudatr2008@[Link]
Algorithme : Définition

 Algorithme : procédure de calcul bien définie qui prend

en entrée une valeur, ou un ensemble de valeurs, et qui
donne en sortie une valeur, ou un ensemble de valeurs.
Un algorithme est donc une séquence d’étapes de
calcul qui transforment l’entrée en sortie.
 L’algorithmique est le permis de conduire de
l’informatique
Algorithmique : premier pas
 Calcul de la somme de deux entiers

variable a, b : entier
variable s : entier

Debut
afficher(" Donner le premier entier ")
saisir(a)
afficher(" Donner le deuxième entier ")
saisir(b)
s<- a+b
afficher(" La somme de a et b est : ")
afficher(s)
Fin
Algorithmique : les étapes
 Initialisation des variables
 Permet de donner des valeurs initiales aux variables
qui seront utilisées dans la résolution du problème
posé
 Traitement
 Résolution du problème étape par étape.
 Affichage du résultat ou retour du
résultat
 Affichage du résultat du problème à l’écran, dans un
fichier, ou sauvegarde du résultat du programme
dans une variable
Algorithmique : pseudo code
 Dans ce cours les algorithmes seront
exprimées sous la forme de programmes écrits
en pseudo-code.
 Un pseudo code n’est pas un « vrai code », il
permet d’employer l’écriture qui semble être
la plus claire et la plus concise pour spécifier
un algorithme.
Pseudo code : déclaration de
variables
 Pour déclarer une variable dans notre pseudo algorithme, il
faut d’abord préciser le mot variable, suivi du nom de la
variable, suivi de deux points et le type de la variable.

La syntaxe d’une déclaration de variable est la suivante :
variable Nom_variable : type

Exemple : variable nom : chaine de caractères

L’opérateur d’affectation d’une variable : <-

Exemple : a<-5

Il est possible de déclarer plusieurs variables sur une
même ligne

La syntaxe de déclaration plusieurs variables sur une
même ligne est la suivante :
variable variable1, variable2, …: type

Déclaration d’une constante
constante Nom_constante: type
Pseudo code : les entrées-sorties

 La fonction afficher(<liste des noms de variables, de

constantes ou d’expression>) permet d’afficher à
l’écran les informations fournies à son entrée.

 La fonction saisir(<liste des noms de variables>)

permet de stocker dans les variables en entrées les
informations fournies par l’utilisateurs.
Pseudo code : exemple
 Calcul de la surface d’un cercle

variable r : réel
variable S : réel

Debut
constante PI : réel
PI<-3.14
afficher(" Donner le rayon du cercle :")
saisir(r)
S<- r*r*PI
afficher(" La surface est :")
afficher(S)
Fin
 Pseudo-code : Traitement
conditionnel
 Un traitement conditionnel permet d’effectuer des choix (alternative) ou de faire un choix
parmi plusieurs.
 Instruction : « si-alors-sinon »
si (expression conditionnelle égale à vraie)
alors faire séquence1 d’ instructions
sinon séquence2 d’ instructions
finsi

Expression
conditionnell
e
vraie fausse
Sequence1 Sequence2
d’instructio d’instructio
ns ns

Suite du
Pseudo code : maximum de deux
entieres
 Calcul du maximum de deux entiers

variable a, b : entier
variable max : entier

Debut
afficher(" Donner deux entiers")
saisir(a)
saisir(b)
si (a > b)
alors max <- a
sinon max <- b
finsi
afficher(max)
Fin
Les différentes formes du si
 si avec sinon
si E
si E vrai faux
alors A1 A1, B1,

sinon B1
finsi
 si sans sinon

si E
alors A1 si E
vra
i
A1 faux
 Les différentes formes du si

 si emboités si
E
si E1 1
alors si E2 vrai
alors A1; A2, ...; An;
sinon B1; B2, ...; Bn; faux
E
2
finsi
sinon C1; C2, ...; Cn; vrai faux

finsi A1,A2;..An B1,B2;..Bn C1,C2;..Cn

; ; ;
Exemple de si emboité
 si emboités
variable moyenne : réel
afficher("donner votre moyenne ")
saisir(moyenne)

si moyenne >=12
si moyenne < 14
alors afficher("assez bien")
finsi
finsi
 Pseudo-code : Traitement
conditionnel
 Un traitement conditionnel permet d’effectuer des choix
(alternative) ou de faire un choix parmi plusieurs.
 Instruction : « selon »
selon <identificateur>
(liste de ) valeur (s) : séquence1 d’instructions
(liste de ) valeur (s) : séquence1 d’instructions
…
[autres : instructions par défaut]
Exemple de selon
 selon

variable codeCouleur : caractère

afficher("Donner un code de couleur")
saisir(codeCouleur)

selon codeCouleur
"0" : afficher("vert")
"1" : afficher("jaune")
"2" : afficher("rouge")
autres : afficher("noir")
Traitement répétitif (boucle)
 Les boucles permettant d’exécuter plusieurs fois la
même série d’instructions jusqu’à ce qu’une condition
ne soit plus réalisée.
 Les variantes se différencient par la manière de
caractériser le nombre de boucles effectivement
réalisées.

pour : on exprime le décompte exact de boucles

Tant que : on exprime la condition de continuation

Répéter … Tant que : on exprime la condition d’arrêt
La boucle pour
 La boucle pour permet d’exécuter plusieurs fois la même
série d’instructions. Dans sa syntaxe, il suffit de préciser :
 Le nom de la variable qui sert de compteur (et éventuellement sa valeur de
départ),
 La condition sur la variable pour laquelle la boucle s’arrête (basiquement
une condition qui teste si la valeur dépasse une limite)
 Une instruction qui incrémente (ou décrémente) le compteur.
 Elle se présente sous la forme suivante :
pour <Cpt><-CptInit à CptFin [par <pas>] faire
séquence d’ instructions;
finpour
La boucle pour
 Exemple : exécuter l’instruction A, puis exécuter N fois
l’instruction B; puis après l’instruction C

variable i : entier;
A
A;
pour i=1 à N faire
B;
finpour Répéter N fois B
C;

C
La boucle pour : schéma détaillé de
l’exemple

variable i : entier
A; A
pour i=1 à 10 par 1
faire
B; i=
finpour 1
C;
i!
=11

Répéter 10 fois
B

i=i+
1 C
 La boucle pour : exemple
{Saisie de n nombres et calcul de la moyenne }

variable n : entier
variable i : entier
variable noteCourant, somme : réel
Début
somme<- 0 {initialisation du calcul} -> commentaire
afficher("Donnez le nombre de notes que vous voulez saisir:");
saisir(n);
pour i=1 à n faire
afficher("Note",i )
afficher(" : ")
saisir(noteCourant)
somme = somme+noteCourant;
finpour
afficher("Moyenne : ",(somme)/n);
Fin
La boucle tant que
 La boucle tant que permet d’exécuter plusieurs fois la même série
d’instructions. Elle se présente sous la forme suivante :
tant que (expression est vraie ) faire
séquence d’ instructions;
fintanque
 Exemple : exécuter l’instruction A, puis tant que E est vraie faire B
et si E est fausse faire C;
A

A; vrai
Tant que E faire E
B;
fintanque B faux
C;
C
 La boucle tant que
Tant que (Expression) faire
sequence d’instructions;
fintanque

 Expression constitue la condition de poursuite de la boucle. La

présence des parenthèses permet de délimiter cette condition.
 Expression est évaluée avant le premier tour de boucle. Il est
donc nécessaire que sa valeur soit définie à ce moment.
 On doit assurer la convergence (arrêt de la boucle) : la condition
doit à un moment donné s’évaluer à faux.
 Condition nécessaire : la condition doit faire intervenir une variable qui
sera modifiée dans le corps de boucle
 Dans le cas d’une conjonction de conditions (tant que ( E1 Et E2)…)

L’arrêt est provoquée quand l’une des deux conditions s’évalue à
faux

La condition d’arrêt est alors : !E1 Ou !E2
 La boucle tant que : exemple

{ Moyenne d’une série de notes saisies au clavier } -> commentaire

variable note, somme : réel

somme <- 0;
variable nbNote : entier
Debut
nbNote <- 0;
afficher(" Donnez une note ou -1 pour terminer : ");
saisir(note);
tant que (note ≠-1) faire
somme <- somme + note;
nbNote <- nbNote+1;
afficher (" Donnez une note ou -1 pour terminer : ");
saisir(note)
fintanque
afficher(" Le nombre de notes saisies est :", nbNote);
afficher(" La moyenne est des notes saisies est : ", (somme)/nbNote);
Fin
 Equivalence d’un tant que et d’un
pour

 Le pour est un cas particulier du tant que

pour i=binf à bsup faire P i<-binf
finpour tant que(i <= bsup) faire
P
i <- i+1
fintanque
 Plus généralement :
pour Cpt<-CptInit à CptMax par k faire P Cpt<-CptInit;
finpour tant que Cpt <= CptMaxfaire
faire
P
Cpt = Cpt+k
fintanque
La boucle répéter…tant que
 L’a boucle répéter…tant que est un autre moyen
d’exécuter plusieurs fois la même série d’instructions.
Elle est toujours parcourue au moins une fois. La
condition d’arrêt n’est examinée qu’à la fin de chaque
répétition. Elle se présente sous la forme suivante :
répéter
séquence d’ instructions;
tant que (expression est vraie );
 La boucle répéter…tant que :
exemple

variable n : entier
Début
répéter
afficher("Donnez un entier strictement supérieur a zéro :")
saisir(n)
afficher("Vous avez fourni :" ,n)
tant que (n <=0) ;

afficher("La valeur positive strictement supérieure à zéro est :");

afficher(n);
Fin
 La boucle tant que : exemple

{Saisie avec filtre : saisie d’une note entre 0 et 20}

variable note : réel

Début
afficher(" Donnez une note : ")
saisir(note)
tant note < 0 Ou note > 20 faire
afficher("la note saisie est incorrecte, veuillez ressaisir : ")
saisir("note)
fintanque
Fin
 Algorithme du plus grand commun
diviseur

{PGCD (plus grand commun diviseur}

Algorithme PGCD
variable a, b : entier
variable x, y : entier
Début
a=46
b=108
x<-a, y<-b;
si (a < 0) alors x=-a;
si (b < 0) alors y=-b;
tant que (x≠y) faire
si(x < y)
alors y<- y-x;
sinon x <- x-y;
finsi
fintanque
afficher("Le pgcd de ", a, b);
afficher("est :", x)
Fin
 La boucle pour : exemple

 Exemple :
pour i=1 à 11 par 2 faire A finpour { « A » exécuté 6 fois}
pour i=0 à 11 par 2 faire A finpour {« A » exécuté 6
fois}
pour i=1 à 12 par 2 faire A finpour { « A » exécuté 6
fois}
pour i=1 à 10 par 2 faire A finpour { « A » exécuté 5
fois}
 La boucle pour : exemple
{ Incrément de n en n : affichage des multiples de n inférieurs à 100 }

variable n : entier
variable i : entier
variable max : entier
max <-99
afficher("Donnez un nombre inferieur à 100 :")
saisir(n);
pour i<-n à max par n faire
afficher( i);
afficher( " ");
finpour
 Algorithme du calcul de puissance
{ calcul de x a la puissance n }

variable x , n, p, resultat : entier

resultat <- 1
afficher("Donnez la valeur de x :");
saisir(x);
afficher("Donnez la valeur de n :");
saisir(n);
pour p=1 à n faire
resultat <- resultat*x;
finpour
afficher("Resultat : ",resultat);