INITIATION A L’ALGORITHME

SEQUENCE 1 : Les Structures de contrôles

1-Introduction :
1-1 :Qu’est ce qu’un algorithme :
- Un algorithme est une séquence d’actions faisant évoluer l’environnement d’un Etat initial donné
vers l’état final désiré .
- Un algorithme est un ensemble de règles ayant les 4 caractéristiques suivantes :
1. Il est fini et se termine après un nombre fini d’opérations.
2. S’il y a des données en entrée leur type doit être précise
3. Il doit avoir au moins un résultat.
4. Il doit être effectif : toutes les opérations doivent pouvoir être effectuées exactement et dans
un temps fini par un homme utilisant les moyens manuels.
Les caractéristiques 2 et 4 indiquent le point de départ de l’élaboration d’un algorithme.
Dans le problème à traiter il faut identifier :
1. Les données en entrée.
2. Les résultats à obtenir.
Ensuite, il faut définir la méthode pour obtenir les résultats recherchés à partir des données. C’est
la recherche ou la conception de l’algorithme proprement dit. Pour un problème donné, il existe souvent
plusieurs algorithmes de résolution. Il s’agit de choisir le meilleur en fonction des circonstances
d’application.
Exemple : Calcul d’un polynôme :
P(x) = 4x 3 + 2x2 – 5x + 3
Pour calculer P(7), par exemple, l’algorithme qui paraît évident est de calculer les puissances
successives de 7 puis de multiplier par les coefficients et d’additionner les produits ainsi obtenus. Cette
résolution nécessite 6 multiplications et 3 additions.
Par contre :
P(x) = (( 4x + 2)x –5)x + 3
Le calcul du polynôme sous cette forme ne nécessite plus que 3 multiplications et 3 additions. Il est
plus économique en nombre d’opérations. Donc en temps d’exécution.
Dans le choix d’un algorithme les principaux critères à prendre en considération :
1. Le temps d’exécution .
2. L’espace mémoire nécessaire.
3. La précision des calculs.
Enfin, il faut décrire l’algorithme choisi. Là encore il existe de multiples méthodes de description.
J’en donnerai deux :
1. L’écriture de l’algorithme en LCS (Langage de Conception Structurée)
2. L’organigramme .
Remarque : LCS n’est en aucun cas un langage de programmation, il donne les structures de base
minimales nécessaires pour décrire n’importe quel algorithme.
1-2: Algorithme et Langage de Programmation :
Un langage de programmation est «Compréhensible » par l’ordinateur. C’est à dire qu’il existe un
programme de traduction (Compilateur) qui code en langage machines (code binaire) ce que le
programme à écrit.
1-3: Convention d’écriture :
 1-3-1: LCS

La notion de base est celle d’instruction, définie comme étant la description non ambiguë d’une ou
plusieurs actions élémentaires à effectuer dans un ordre déterminé.
Selon les besoins une suite d’instructions formera un bloc délimité par les mots Début et Fin :

Début
Instruction 1.
Instruction 2.
Instruction 3.
…
…
Instruction n.
Fin

Un bloc peut en contenir d’autres.

On peut schématiser ce principe par l’arborescence :

1 2 3

1.1 1.2 3.1 3.2

3.1.1 3.1.2

Un algorithme de résolution complexe est divisé en plusieurs sous-algorithmes plus simples.

1-3-1 : Organigramme :

Les symboles utilisés dans un organigramme pour décrire un algorithme sont les suivants :

Début

Instruction 1

Instruction 2

Instruction n

Fin

Le rectangle indique une action à exécuter.

On dispose en outre du losange :

Qui symbolise une alternative.

Le parallélogramme indique qu’on introduit des données ou qu’on fournit un résultat.

L’organigramme donne une impression de déroulement successif des instructions plus grandes, mais ne
met pas en évidence la notion de bloc.

2- Les Structures de Contrôle :

2-1 : Les Instructions de base :

2.1.1 : La lecture des données :

Cette action donne une valeur à un objet tout en le nommant, c’est à dire en lui affectant
un Identificateur.
Syntaxe : LIRE < Identificateur >
Exemple : LIRE N
LIRE X , Y , Z
Action : Lorsque l’exécutant (l’ordinateur après traduction de l’algorithme en un langage de
programmation quelconque, ou bien le concepteur lors de la vérification de l’algorithme) rencontre cette
instruction, il s’arrête et attend que l’utilisateur donne une valeur à N dans le premier exemple.

2.1.2 : L’affectation :

Syntaxe : < Identificateur > = <Expression >

Expression étant définie par :
< Expression > = < Identificateur > / < Constante > /
< Expression Arithmétique > /
< Expression logique >

Exemple : Total = 526

Prix = Total
Somme = Total + 6
Action : Après exécution, <Identificateur > contient la valeur de <Expression>
Prix contient maintenant la valeur 526 et somme contient la valeur 532.

Remarques :
1. L’affectation écrase la valeur précédente de < Identificateur > par la nouvelle.
2. La valeur de l’objet à droite du signe = n’est pas touchée par l’affectation.

2.1.3 : L’écriture des résultats

Syntaxe : Ecrire < Expression>

Exemple : Ecrire Total.

 Ecrire ‘Ceci est une chaîne de caractères’
Action : Cette instruction est le symétrique de lire. Elle visualise les résultats.
En l’absence d’ordre d’écriture dans l’algorithme, les résultats ne sont
pas fournis à l’utilisateur.
Remarque : Dans le deuxième exemple la chaîne de caractères est entourée de ' ' , ce sont des
délimiteurs de chaîne, ils indiquent que la suite de caractères situés entre eux est une constante et ne doit
pas être traitée en tant qu’Identificateur.

2.1.4 : Déclaration d’objet de type

Dans un algorithme, on est obligé de déclarer au début tous les objets qui seront utilisés par la suite,
en indiquant leur type.

Types simples :
Entier : Un objet de ce type peut prendre une valeur entière
Réel : Un objet de ce type peut prendre une valeur décimale Chaîne de
caractères : ( Abréviation : Chaîne )
Booléen : Un objet de ce type prend sa valeur dans l’ensemble {Vrai, Faux }

2.2 : Les Opérations

2.2.1 : Opérateurs arithmétiques :

+ Pour l’addition.
_
Pour la soustraction.
* Pour la multiplication.
/ Pour la division.
** Pour la puissance.
Les parenthèses peuvent être utilisées.

2.2.2 : Opérateurs relationnels :

= Egal .
<> Différent de
< Inférieur
<= Inférieur ou égal
> Supérieur
>= Supérieur ou égal

2.2.3 : Opérateurs logiques :

OU ou logique
ET et logique
NON non logique

2.3 : Quelques Exemples d’Algorithmes Simples :

* Calcul de la somme de 2 nombres :

Analyse :
Etape 1 : Donner une valeur à A
Donner une valeur à B
Etape 2 : Calculer la valeur de l’expression A + B
Etape 3 : Editer le résultat .
Cet exemple trivial met en évidence la composition des algorithmes les plus simples :
1-Initralisation des données.
2-Traitement.
 3-Edition des résultats.
Avant d’écrire l’algorithme, l’analyse permet de définir les objet, encore appelés variables nécessaires à
la résolution du problème :
A Le nombre 1
B Le nombre 2
Somme Le résultat

En LCS :
Algo1
Var A , B , Somme : Entier.
Début
Lire A
Lire B
Somme = A + B
Ecrire Somme.
Fin

En organigramme :

Début

Lire A , B

Somme = A + B

Ecrire Somme

Fin

* Calcul du quotient et du reste de la division entiers de 2 entiers :

Dividende A / Diviseur B / Quotient Q / Reste R

A = BQ + R
Analyse : 1- Initialisation de A et B
2- Calcul de Q
Calcul de R = A – BQ
3- Edition des Résultats

Variables nécessaires :
A , B , Quotient , Reste tous de type Entier

L’algorithme :
Algo2
Var A , B , Quotient , Reste : Entier
Début
! Initialisation
Lire A , B
! Traitement
Quotient = A / B
Reste = A – (Quotient * B)
! Edition des résultats
Ecrire ‘La division de ‘ , A , ’ par ’ , B , ’ a pour Quotient ’ , Quotient ,
’ et pour reste ’ , Reste
Fin

Début

Lire A , B

Quotient = A / B

Reste = A – ( Quotient * B )

Ecrire Quotient , Reste

Fin

* Permutation de 2 nombres :

Permuter les valeurs des 2 variables X et Y

Analyse :
On ne peut pas simplement faire X = Y , car la valeur précédente de X serait perdue, il faut donc la
sauvegarder au préalable, et pour cela il faut une troisieme variable appelée < Tampon > ou variable de
travail.

Algorithme :
Permutation
Var X , Y , T : Entier
Debut
Lire X , Y
! Traitement
T = X
X = Y
Y = T
! Edition des résultats
Ecrire X , Y
Fin
 Début

Lire X , Y

T = X

X = Y

Y = T

Ecrire X , Y

Fin

2.4 : La Structure Alternative :

2.4.1 : Syntaxe
VRAI FAUX
Exp.
Log
Si < Exp. Logique > Alors
Bloc 1
Sinon Bloc 1 Bloc 2
Bloc 2
Fin Si

Remarque : bloc1 et bloc2 peuvent se limiter à une seule instruction .

Quand < Exp. Logique > est varie , bloc1 est exécuté et bloc2 est ignoré .
Par contre quand < Expression Logique > est fausse on exécute bloc2 et on ignore Bloc1.

2.4.2 : Exemples
* Editer le plus grand des 2 nombres X et Y.
SUP
Lire X , Y
Var X , Y : entier
Début
Lire X ,Y
Si X >Y alors X>Y
Ecrire X
Sinon O N
Ecrire Y Ecrire X Ecrire Y
Fin si
Fin

Fin
 * Ordonner 3 nombre par ordre croissant.

Soient V1,V2,V3 les variables à classer. On compare V1 à V2 et on les ordonne pour avoir la petite
valeur dans V1, puis on compare V3 à chacune des précédentes, 3 comparaisons suffissent . Pour les
permutations on a besoin d’un tampon.

ORD
Var V1, V2, V3, T : entier
Début
Lire V1, V2 ,V3
Si V1> V2 Alors
T = V1
V1 = V2
V2 = T
Fin si
Si V3< V1 Alors
T = V1
V1 = V3
V3 = V2
V2 = T
Sinon
Si V3 < V2 Alors
T = V2
V3 = T
Fin Si
Ecrire ‘les valeurs dans l’ordre son’ ,V1,V2,V3
Fin si
Fin

2.5 : La Structure Répétitive.

2.5.1 : Syntaxe :

Tant que <Exp. logique > faire

Bloc
Refaire VRAI FAUX
Exp.
Log

Bloc

On teste d’abord si < Exp. logique > est varie. Dans ce cas on exécute les instructions du bloc puis
un boucle de niveau sur le test de < Exp. Logique>.
Par contre, si <Exp. Logique> est fausse la boucle se termine ( le bloc n’est pas exécuté )
Un bloc peut contenir des structures alternatives et des structures répétitives imbriquées.
2.5.2 : Exemples
* La multiplication :
Effectuer une multiplication de 2 entiers positifs en n’utilisant que l’addition
P =Ax B P = A + A + ….+ A

B fois
 Analyse :
B sera un compteur décrémenté à chaque boucle , dans laquelle on additionnera la valeur de A à la valeur
précédente de P.
P est initialisé à 0.
Algorithme
Mult
Var A , B , P : entier
Début
P= O
Ecrire ‘Introduire 2 entiers positifs’
Lire A ,B
! boucle de calcul
Tant que B<>0 faire
P=P+A
B=B-1
Refaire
! Edition
Ecrire P
Fin
Organigramme
Début

P=0

Lire A , B

O N
B <> 0

P=P+A
B=B-1 Ecrire P

 Factoriel d’un nombre : Fin

Ex : 3 ! =3 x 2 x 1= 6

Fact
Var N , I , J : entier
Début
I=1
J=1
Lire N
Tant que I < N faire
I=I+1
J=J*I
Refaire
Ecrire ‘le factoriel est :’ , J
Fin
 Séquence 2 : Complément Algorithmiques :

1 – Les Tableaux.

1.1 :Tableau à une dimension :

Un tableau est une structure de donnée regroupant une suite de variables de même type.
Par définition , un tableau à une dimension de taille N, d’éléments de type T est un élément de T N.
Un tableau à une dimension peut encore être Appelé vecteur.
Pour déclarer un tableau , il est nécessaire d’indiquer sa dimension , sa taille et le type de ses éléments :
< tableau > = < Identificateur > : tableau ( 1 . . N ) de < type >
N étant un entier positif
On atteint un élément du tableau par son indice i :
i ( 1. . N )
comme toute variable , un tableau se déclare en début d’algorithme

Exemple :

Jour : Tableau ( 1. . 7 ) de chaîne

Lundi Mardi Jeudi Vendredi Samedi Dimanche
Jour (1) = ‘lundi’
Jour (4) = ‘Jeudi’
Jour (8) = indéfini.
Si un programme est amené à dépasser les limites d’un tableau . il y a une erreur de logique quelque
part . il faut revoir l’algorithme.

1.2 : Tableau à deux dimensions :

Un tableau à deux dimensions correspond à la notion de matrice ( M x N ). Il contient des éléments

toute de même type T, c’est donc un élément de Tm x Tn
on peut encore dire que c’est un tableau de taille M de tableau de taille N d’éléments de type T.
<tableau> = < Identificateur > : Tableau (1.. M,1..N ) de < type >
On atteint un élément d’un tableau à deux dimensions par le couple d’indice ( I , J ) :
I (1. . M)
J (1. . N)
I est appelé indice de ligne .
J est appelé indice de colonne.
Exemple :
Tab : tableau ( 1. . 3, 1 .. 4 ) de entier

1 2 3 5
8 13 21 34
55 89 144 233

Tab (2,3) = 21
Tab (3,2) = 89
Ne pas oublier qu’un tableau ne peut contenir qu’un seul type de données .

2- Algorithmes de Traitement de tableaux :

Pour ne pas avoir à écrire chaque fois l’initialisation du Tableau T, on suppose qu’il
contient des données et qu’il est disponible en mémoire centrale .
 2.1 : Recherche du maximum :

Problème : Soit un tableau T de N entiers, donner la valeur du plus grand élément

de T ainsi que l’indice de la première occurrence de ce maximum.
Donnée : Tableau T
Résultat : Maximum MAX

Algorithme : L’idée est d’initialiser MAX avec la valeur du premier élément de

T , puis de le comparer successivement avec chaque élément en
affectant la valeur de ce dernier à MAX lorsqu’il est plus grand.
Comme variable de travail il faut un compteur I
Maximum
! Recherche du maximum d’un tableau
var T : tableau (1..10) de entier
MAX. , I : entier
Début
! Initialisation
I =1
MAX = 1
! Boucle de parcours du tableau
Tant que I< = 10 faire
! Test si MAX est le plus grand
Si MAX < T (I) Alors
MAX = T (I)
FinSi
I = I+ 1
Refaire
Ecrire ‘Le maximum est ‘ , MAX
2.2 : Recherche d’un élément dans un tableau .

Problème : Soit un élément E donné , on veut savoir s’il est ou non présent dans le
tableau T
Entrée : Tableau T
Entier E
Sortie : Message d’absence

Recherche
Var T : tableau (1..10) de entier
E , I : entier
Trouve : booléen
Début
Lire E
I =1
Trouve = faux
Tant que I < = 10 faire
Si T (I) = E alors
Trouve = vrai
Finsi
I = I+1
Refaire
Si trouve alors
…………
Sinon
écrire ‘l’élément n’est pas dans T ‘
FinSi
Fin
3 - Notion de Sous – Programme
3 - 1 procédure :
Définition :

Une procédure est un sous-programme écrit à l’intérieur (ou éventuellement à l’extérieur ) d’un
programme principal assurant de manière autonome un traitement particulier. Ce traitement peut alors
être répété dans le programme par simple appel de la procédure .
La notion de procédure comporte 2 aspects dont il faut prendre conscience et qu’il est très important
de distinguer :
- La définition de la procédure, appelée déclaration de procédure, placée en tête de l’algorithme
principal directement après la déclaration des variables et qui décrit le traitement effectué par la
procédure.
- L’utilisations de la procédure appelée APPEL de procédure, qui se situe dans le bloc de l’algorithme
complet.

Syntaxe :

Procédure < Identificateur > < liste de paramètres >

un bloc de procédure contient toutes les rubriques d’un algorithme complet :

* Déclaration de variables , qui seront alors des variables locales à la procédure

* La suite des instructions entre début et fin .

Exemple :

Programme - jour
Var I : entier
Procédure jour ( N : entier )
Début
Si N = 1 alors
Ecrire ‘c’est lundi’
Sinon
Si N = 2 alors
Ecrire ‘c’est mardi ‘
fsi
Fsi

Fin ! Fin de procédure

Début ! début de programme principal.
Ecrire ‘Introduisez un n° du jour’
Lire I
Jour (I)
Fin

3.2 : Fonction

Définition :
C’est un sous-programme similaire à la procédure mais qui calcule une valeur d’un type donné,
valeur qui sera restituée au programme appelant , à travers le non donné à la fonction.

Syntaxe :

FONCTION < Identificateur > (liste de paramètres formels ) : < type >
 Exemples :

Test
Var M : entier
Fonction f ( N : entier ) : entier
Var I , Fact : entier
Début
I=1
Fact = 1
Tant que I < = N faire
Fact = Fact * I
I= I + 1
Refaire
f = Fact
Fin ! fin de la fonction
Début ! de l’algorithme principal
Lire (M)
Ecrire ‘le factoriel de M est’ , f ( M )
Fin

4- Des Tris .
5- Exercices.