Ministère de l’Enseignement Supérieur, de la Recherche Scientifique et de la Technologie

Direction Générale des Etudes Technologiques

Institut Supérieur des Etudes Technologiques de Zaghouan

Département TECHNOLOGIES DE l’INFORMATIQUE

Matière :
Algorithmiques & structures de données 1
Mots-clés du Support
Algorithme, programme, Structure de données, Actions de base, Variables, Structures de
données conditionnelles, chaînes de caractères, Structures de données itératives, les
Fonctions, les Procédures, les Enregistrements, le Tri, les Algorithmes de tri, etc.

Support de cours adressé aux étudiants du réseau ISETs et aux autres

étudiants de niveaux équivalents.

Réalisé par :
Nooman MAHJOUB (ISET Beja)

Moez CHEBI (ISET Kairouan)

MENSI Ali (ISET Zaghouan) (coordinateur du groupe)

Année universitaire : 2014-2015

Table des matières
FICHE DE PRESENTATION DE LA MATIERE ........................................................................................ 5

OBJECTIFS DU COURS ................................................................................................................................................ 5

EVALUATION ........................................................................................................................................................... 5
MOYENS PEDAGOGIQUES .......................................................................................................................................... 6
REPARTITION HORAIRE DES COURS .............................................................................................................................. 6
SUPPORTS ET REFERENCES BIBLIOGRAPHIQUES .............................................................................................................. 7

CHAPITRE 1 INTRODUCTION ............................................................................................................... 9

1. LES ÉTAPES DE RÉSOLUTION D’UN PROBLÈME EN INFORMATIQUE ......................................................... 9

3.1 Définition et analyse du problème ................................................................................................... 9
3.2 Ecriture d’un algorithme ................................................................................................................. 9
3.3 Programmation de l’algorithme....................................................................................................... 9
3.4 Compilation du programme ........................................................................................................... 10
3.5 Exécution et test du programme .................................................................................................... 10
2. STRUCTURE GÉNÉRALE D’UN ALGORITHME .......................................................................................... 10
2.1 Définition d’une variable ............................................................................................................... 11
2.2 Définition d’une constante ............................................................................................................. 12
2.3 Les types de base ............................................................................................................................. 12
2.4 Exemple d’un algorithme ............................................................................................................... 13

CHAPITRE 2 LES ACTIONS SIMPLES ................................................................................................ 14

1. INTRODUCTION........................................................................................................................................ 14
2. L’ACTION D’AFFECTATION ..................................................................................................................... 14
2.1. Syntaxe............................................................................................................................................ 14
2.2. Traitement....................................................................................................................................... 14
2.3. Compatibilité de types ..................................................................................................................... 14
2.3.1 Les expressions arithmétiques .................................................................................................................... 15
2.3.2 Les expressions logiques ............................................................................................................................. 15
3. EXERCICES D’APPLICATION.................................................................................................................... 16
4. CORRECTION DES EXERCICES................................................................................................................. 18
5. L’ACTION DE LECTURE OU D’ENTREE .................................................................................................... 19
5.1 Syntaxe............................................................................................................................................ 19
5.2 Traitement....................................................................................................................................... 20
6. L’ACTION D’ECRITURE OU DE SORTIE .................................................................................................... 20
6.1 Syntaxe............................................................................................................................................ 20
6.2 Traitement....................................................................................................................................... 21
6.2.1 Exemple............................................................................................................................................. 21
6.2.2 Exercice d’application .................................................................................................................... 21
7. APPLICATIONS ......................................................................................................................................... 21
8. CORRECTIONS DES EXERCICES ............................................................................................................... 23

CHAPITRE 3 LES ACTIONS CONDITIONNELLES............................................................................ 26

1. INTRODUCTION........................................................................................................................................ 26
2. L’ACTION CONDITIONNELLE SIMPLE ..................................................................................................... 26
2.1. Exemple .......................................................................................................................................... 26
2.2. Exercices d’application .................................................................................................................. 27
3. L’ACTION CONDITIONNELLE A CHOIX MULTIPLE .................................................................................. 28
 4. EXERCICES D’APPLICATION.................................................................................................................... 30
5. CORRECTIONS DES APPLICATIONS ......................................................................................................... 30

CHAPITRE 4 LES ACTIONS ITERATIVES........................................................................................ 33

1. INTRODUCTION........................................................................................................................................ 33
2. L’ACTION "TANT QUE" .......................................................................................................................... 33
2.1. Syntaxe............................................................................................................................................ 33
2.2. Traitement....................................................................................................................................... 33
2.3. Exemple .......................................................................................................................................... 33
2.4. Exercice d’application .................................................................................................................... 34
3. L’ACTION "REPETER" ............................................................................................................................ 34
3.1. Syntaxe............................................................................................................................................ 34
3.2. Traitement....................................................................................................................................... 34
3.3. Exemple .......................................................................................................................................... 35
3.4. Exercice d’application .................................................................................................................... 35
4. L’ACTION "POUR" .................................................................................................................................. 35
4.1. Syntaxe............................................................................................................................................ 35
4.2. Traitement....................................................................................................................................... 36
4.3. Exemple .......................................................................................................................................... 36
4.4. Exercices d’application .................................................................................................................. 36
5. EXERCICES D’APPLICATION.................................................................................................................... 37
6. CORRECTION EXERCICES D’APPLICATION ............................................................................................. 38

CHAPITRE5 LES TABLEAUX ................................................................................................................. 41

1. INTRODUCTION........................................................................................................................................ 41
2. DEFINITION D’UN TABLEAU .................................................................................................................... 41
3. TABLEAUX A UNE DIMENSION ................................................................................................................. 41
3.1. Déclaration ..................................................................................................................................... 41
3.2. Accès à un élément du tableau ....................................................................................................... 41
4. TABLEAUX A DEUX DIMENSION ............................................................................................................... 42
4.1. Déclaration ..................................................................................................................................... 42
4.2. Accès à un élément d’une matrice ................................................................................................. 42
5. EXEMPLES ............................................................................................................................................... 43
5.1. Exemple 1 ......................................................................................................................................... 43
5.2. Exemple2 .......................................................................................................................................... 43
5.3. Exemple 3 ......................................................................................................................................... 44
6. RECHERCHE SEQUENTIELLE................................................................................................................... 44
7. EXERCICES .............................................................................................................................................. 44

CHAPITRE 6 LES CHAINES DE CARACTERES ............................................................................... 48

1. INTRODUCTION........................................................................................................................................ 48
2. DEFINITION D’UNE CHAINE DE CARACTERES ......................................................................................... 48
3. DECLARATION ......................................................................................................................................... 48
4. ACCES A UNE CASE .................................................................................................................................. 48
5. FONCTIONS PREDEFINIES SUR LES CHAINES DE CARACTERES ............................................................... 48
5.1. La fonction Longueur .................................................................................................................... 48
5.2. La fonction ASC ............................................................................................................................. 48
5.3. La fonction CHR ............................................................................................................................ 49
6. EXERCICES D’APPLICATION.................................................................................................................... 49

CHAPITRE 7 : LES PROCEDURES ET LES FONCTIONS ..................................................................... 51

 1. INTRODUCTION........................................................................................................................................ 51
2. LES PROCEDURES .................................................................................................................................... 51
2.1. Déclaration ..................................................................................................................................... 51
2.2. Types et modes de passage des paramètres .................................................................................... 51
2.2.1. Types des paramètres formels .................................................................................................................... 51
2.2.2. Modes de passage des paramètres formels ................................................................................................ 51
2.2.3. Appel d’une procédure ................................................................................................................................ 52
2.2.4. Exemple d'un appel d'une procédure.......................................................................................................... 52
2.3. Exercices d’application .................................................................................................................. 53
3. LES FONCTIONS ....................................................................................................................................... 54
3.1. Déclaration ..................................................................................................................................... 54
3.2. Appel d'une fonction ...................................................................................................................... 55
3.3. Exemple d'une fonction ................................................................................................................. 55
4. EXERCICES D’APPLICATION.................................................................................................................... 55

CHAPITRE 8 : LES ENREGISTREMENTS .............................................................................................. 57

1. INTRODUCTION........................................................................................................................................ 57
2. DEFINITION.............................................................................................................................................. 57
3. DECLARATION ......................................................................................................................................... 57
4. ACCES A UN CHAMP D’UN ENREGISTREMENT......................................................................................... 57
5. EXERCICES D’APPLICATION.................................................................................................................... 58
5.1. Exercice 1 ....................................................................................................................................... 58
5.2. Exercice 2 ....................................................................................................................................... 59

CHAPITRE 9 : LES ALGORITHMES DE TRI .......................................................................................... 60

1. INTRODUCTION........................................................................................................................................ 60
2. TRI PAR SELECTION ORDINAIRE ............................................................................................................. 60
2.1 Principe ........................................................................................................................................... 60
2.2 Algorithme de tri par sélection ....................................................................................................... 60
3. TRI PAR INSERTION SEQUENTIELLE........................................................................................................ 61
3.1 Principe ........................................................................................................................................... 61
3.2 Algorithme de tri par insertion séquentielle .................................................................................. 62
3.3 Exemple .......................................................................................................................................... 62
4. TRI PAR INSERTION DICHOTOMIQUE ...................................................................................................... 63
4.1. Principe ........................................................................................................................................... 63
4.2. Algorithme de tri par insertion dichotomique ............................................................................... 63
5. ALGORITHME DE TRI RAPIDE.................................................................................................................. 64
5.1 Présentation .................................................................................................................................... 64
5.2 Choix du pivot................................................................................................................................. 64
5.3 Exemple .......................................................................................................................................... 65
5.4 Algorithme ...................................................................................................................................... 65
6. TRI PAR TAS ............................................................................................................................................. 66
6.1 Définition ........................................................................................................................................ 66
6.2 Exemple .......................................................................................................................................... 66
6.3 Utilisation d’un tas pour le tri ........................................................................................................ 66
6.4 Algorithme de tri par tas ................................................................................................................ 67
ISET Zaghouan Cours Algorithmique 1

Fiche de Présentation de la matière

ALGORITHMIQUE ET STRUCTURES DE DONNEES 1

Spécialité : Technologies de l’informatique

Population : Etudiants de réseau ISETs.
Niveau : semestre 1
crédits : 67 heures et 30 minutes par semestre
Charges horaires : 4h :30 par semaine sur 15 semaines
Nature cours : Cours Intégrés
Prérequis : Néant
Langue : Français

Objectifs du cours
 Fournir aux étudiants des bases rigoureuses en algorithmique, en insistant sur l'aspect
scientifique de la discipline.
 Acquérir les notions fondamentales d’algorithmique (variables, constates, affectation, entrées
sorties, structures conditionnelles, structures itératives, tableaux, procédures, fonctions, tri et
recherche, ...)
 Savoir écrire des algorithmes pour résoudre des problèmes,
 Maîtriser le raisonnement algorithmique
 Formuler les algorithmes de quelques types de tri à savoir le tri par tas, le tri par insertion…
 Comprendre la notion de complexité et apprendre la méthode d’estimation de la complexité
des algorithmes.
 Stimuler la créativité des étudiants en les encourageant à exploiter les solutions vues au cours
pour en élaborer de nouvelles.

Evaluation
 Contrôle continu : il est compté comme 38% de la note finale du candidat et regroupe les notes
suivantes :

Cours ASD 1 5
 ISET Zaghouan Cours Algorithmique 1

 La note de mini projet : chaque candidat est appelé à participer avec un autre binôme
dans un mini projet. Chaque deux binômes sont appelés à présenter leur travail à la fin
du semestre.
 Les notes de tests : un nombre variable de tests au cours des séances de cours.
 Une note pour l’assiduité des candidats
 La note du devoir surveillé : un examen partielle possible de le faire à partir de la
cinquième semaine de cours.
 Examen Final : il s’agit d’un examen de synthèse qui aura lieu à la fin du semestre. Cet
examen est compté comme 62% de la note finale du candidat.

Moyens Pédagogiques
 Support de cours papier.
 Support de cours numérique.
 Série de travaux dirigés : à la fin de chaque chapitre on doit avoir une série d’exercices.
 Sujets d’examens antérieurs.

Répartition horaire des cours

En tenant compte des prédictions de l’avancement au niveau des travaux pratiques du module
Atelier Programmation1 associés aux notions de cours de ce module , la répartition des chapitres est fixée
selon le tableau suivant.

Cours ASD 1 6
 ISET Zaghouan Cours Algorithmique 1

N° Titre Semaine(s)

1 Introduction S1 – S2

2 Action Simples S3

3 Actions Conditionnelles S4

4 Actions Itératives S5 – S6

5 Les Tableaux S6 – S7

6 Les chaînes de caractères S8 – S9

Les procédures et les

7 S10 – S11
fonctions

8 Les Enregistrements S12 – S13

9 Les algorithmes de tri S14

Répartition horaire des cours

Le programme est planifié sur 14 semaines seulement. Nous avons décidé de laisser une dernière
semaine pour remédier les problèmes de décalage. Si tout va bien, cette semaine sera réservée pour une
révision à l’examen final.

Supports et Références Bibliographiques

[1] Le Langage C, Christian Bac, 24 février 2004.

[2] Algorithmique et Bases de la Programmation, Hamrouni M. Kamel, Année : 2004-05.

[3] Algorithmique – Niveau 1, Belhassen GUETTAT, 1er Semestre 2003-2004.

[4] Introduction au langage C norme iso / ansi , Bernard Cassagne, 2.1 de juin 1998

[5] Introduction à l'informatique et programmation en langage C, Jean Fruitet, 1999.

[6] Initiation au Langage C Niveau 1, M . Berthomier Eric, Version 1.1 du 13 Mars 2000
Cours ASD 1 7
ISET Zaghouan Cours Algorithmique 1

[7] Brian W. Kernighan, Dennis M. Ritchie Programmieren in C, 2. Ausgabe, ANSI-C Carl

Hanser Verlag, 1990.

[8] Autoformation, Le Langage C, Joelle Maillefert.

[9] Support de cours : Programmation C – II, Niveau 2 Par BEN ROMDHAN Mourad

[10] Claude Delannoy Exercices en Langage C Edition EYROLLES, 1992.

[11] The C programming language , Second Edition Dennis Ritchie & Brian W. Kernighan,
Edition PRENTICE HALL Informatique, 1988.
[12] Le langage C, Dominique GALLAND, Édition DUNOD Informatique, 1989.

Cours ASD 1 8
 ISET Zaghouan Cours Algorithmique 1

Chapitre 1 Introduction
1. Les étapes de résolution d’un problème en informatique

3.1 Définition et analyse du problème

La première étape de la démarche consiste à analyser le problème, définir les données et leurs
caractéristiques et notamment leurs types, définir les résultats et les relations entre résultats-données et
résultats entre eux. Cette étape définie le cahier des charges du problème.

Supposons par exemple que nous avons à ordonner (ou trier) une suite de nombres entiers.

Les données sont les entiers à ordonner. Le résultat en sortie sera une suite constituée par les
mêmes nombres en entrée mais mis en ordre.

La sortie est donc le résultat d'une permutation ou réorganisation des données en entrée.

3.2 Ecriture d’un algorithme

Définition

Un algorithme est une séquence d'étapes de calcul qui utilise des données en entrée pour arriver à des
résultats en sortie.

Exemple

 L'entrée : suite de n nombres (a1, a2, ...an)

 La sortie : suite de n nombres (b1, b2,... bn) tel que {b1,... bn}={al,…an} et b1<b2<b3...<bn

 Le résultat en sortie est une suite de nombres ordonnés résultant de la permutation ou

réorganisation de la suite en entrée.

Remarque

Un algorithme est correct lorsque, pour chaque donnée en entrée (dite instance), il se termine en
produisant la bonne sortie, c'est-à-dire qu'il résout le problème posé.

3.3 Programmation de l’algorithme

La programmation d'un algorithme consiste à choisir un langage de programmation et ensuite à

traduire l'algorithme et les données sur lesquelles il opère sous forme d'un programme exprimé dans ce
langage.

Cours 1 : Introduction 9
 ISET Zaghouan Cours Algorithmique 1

Un programme est un ensemble d'instructions décrivant les différentes actions d'un algorithme en
respectant des règles d'écriture du langage (syntaxe). On obtient ainsi un fichier (programme source).
C'est un fichier texte créé et modifié par un éditeur de texte.

3.4 Compilation du programme

La compilation consiste à traduire le programme source écrit dans un langage de haut niveau en un
programme exécutable écrit dans un langage binaire de bas niveau.

Au cours de cette traduction, le compilateur détecte des éventuelles erreurs (lexicales et/ou
syntaxiques).

3.5 Exécution et test du programme

Le concepteur de l'algorithme doit s'assurer que le programme donne un résultat correct dans tous
les cas et dans toutes les éventualités. Il faut ainsi valider et tester le programme construit.

Pour ce faire, on procède de la sorte :

 On construit des jeux d'assai, c.-à-d. des échantillons de données de base correspondant
aux différents cas,

 On exécute le programme pas à pas sur l'ordinateur,

 On vérifie l'exactitude des résultats fournis par le programme,

-Si tous les résultats sont valides, Alors, il faut Accepter le programme (Jusqu'à preuve du
contraire) et le documenter.

-Sinon, alors, il faut Réviser l'algorithme et le modifier

2. Structure générale d’un algorithme

Un algorithme comporte essentiellement deux parties :

 Une partie déclarative

 Une partie corps de l'algorithme qui consiste en une séquence d'actions faisant appel à des
opérations de base de l'ordinateur.

Cours 1 : Introduction 10
 ISET Zaghouan Cours Algorithmique 1

Algorithme <nom de l'algorithme>

Constantes
<liste des constantes avec leurs valeurs>
Partie déclarative
Types
<définition des types définis par l'utilisateur>

Variables
<liste des variables suivies de leur type>

Début
Partie corps de
< séquence d’actions>
l'algorithme
Fin

Une action peut être une :

 Action d'affectation,

 Action d'entrée/sortie,

 Action de contrôle conditionnelle simple ou à choix multiple,

 Action de répétition en nombre de fois connu ou inconnu à l'avance

2.1 Définition d’une variable

Une variable est un emplacement mémoire capable de contenir des valeurs de type défini au
préalable. Elle peut être définie comme une boite. Cette boite admet un nom, une taille, un contenu
(valeur) et une adresse. Le nom de la variable s'appelle "identificateur de variable". La taille dépend du
type de la variable (2 octets pour le type entier, 1 octet pour le type caractère, 4 octets pour le type réel,
...etc.).

Dans un algorithme, les variables sont déclarées comme suit :

Var Liste1 variables séparées par «,» : Type1

Liste2 variables séparées par «, » : Type2

Cours 1 : Introduction 11
 ISET Zaghouan Cours Algorithmique 1

Liste i variables séparées par « , » : Type i

Exemple

Déclaration de deux variables à contenir deux valeurs entières.

Var x, y : entier

2.2 Définition d’une constante

La définition d'une constante est identique à celle d'une variable, à la différence que la valeur
d'une constante, reste inchangée dans l'algorithme.

Les constantes apparaissent dans un algorithme comme suit :

const identificateurConstante1 = valeur 1

identificateurConstante2 = valeur 2

identificateurConstante i = valeur i

Exemples

const pi = 3.14

const N = 30

2.3 Les types de base

A une variable est attribué un type. Ce type indique l'espace mémoire qui peut être réservé à cette
variable aussi bien d'un point de vu taille que contenu. Il existe des types simples qui sont prédéfinis tels
que les types entier, réel, caractère ou booléen :

 Le type entier : désigne un ensemble de valeurs entières.

Exemples : -10, -6, 0, 5, 1001...

 Le type réel : désigne l'ensemble des valeurs réelles.

Exemples : 1.55, -224.25 ...

Cours 1 : Introduction 12
 ISET Zaghouan Cours Algorithmique 1

 Le type caractère : désigne l'ensemble de tous les symboles. Exemples : 'a', 'b 'c', 'A', 'B', '*', '+',
';'...

 Le type booléen : désigne un ensemble de deux valeurs : VRAI ou FAUX.

Il existe aussi des types composés définis à partir des types de base tels que les tableaux, les
enregistrements, les chaînes de caractères, etc.

On peut définir un nouveau type et lui attribuer un nouveau nom.

2.4 Exemple d’un algorithme

On veut calculer et afficher le maximum de deux entiers.

 Entrée : deux nombres entiers saisis au clavier

 Sortie : un nombre entier max des deux entiers saisis

 Traitement :

- Enregistrer les deux nombres entiers en mémoire

- Comparer les deux nombres en cherchant le max

- Afficher le résultat

Algorithme Max
var x, y : entier
Début
Ecrire ("Donner deux entiers")
Lire(x, y)
Si x > y alors
Ecrire (X)
Sinon
Ecrire (Y)
Fin si
Fin
Remarque

Trois actions ont été utilisées :

 Une action d'écriture : écrire

 Une action de lecture : lire

 Une action conditionnelle simple : Si Alors Sinon FinSi

Cours 1 : Introduction 13
 ISET Zaghouan Cours Algorithmique 1

Chapitre 2 Les actions simples

1. Introduction
Ce chapitre présente les actions simples utilisant les opérations de base d'un ordinateur. Ces actions sont :

 L'action d'affectation qui permet d'affecter à une variable (enregistrer dans un emplacement
mémoire) une valeur qui peut être donnée ou calculée à partir d'une expression.

 L'action de lecture qui met en œuvre l'opération de lecture d'une valeur à partir de l'entrée standard
d'un ordinateur et de l'enregistrer dans un emplacement mémoire.

 L'action d'écriture qui permet d'afficher, sur la sortie standard d'un ordinateur, un résultat qui peut
être alphabétique ou numérique.

2. L’action d’affectation
L'action d'affectation a pour effet d'écrire la valeur d'une variable dans la zone mémoire réservée à la
variable en question.

2.1. Syntaxe
Une action d'affectation a la forme suivante :

<identificateur de variable> ← <expression>

Nous distinguons deux types d'expressions : arithmétiques ou logiques.

2.2. Traitement
L'exécution d'une action d'affectation consiste d'abord à évaluer la valeur de l'expression et ensuite à
écrire cette valeur dans l'espace mémoire correspondant à la variable en question.

2.3. Compatibilité de types

Une action d'affectation doit se faire entre deux types compatibles. c.à.d. la valeur affectée doit être
d'un type compatible avec celui de la variable identifiée qui reçoit cette valeur (entier à un entier, entier à
un réel, booléen à un booléen,...).

Il n'est pas possible d'affecter un réel à un entier ou un booléen à un caractère,...

Cours2 : Les actions simples Page 14

 ISET Zaghouan Cours Algorithmique 1

2.3.1 Les expressions arithmétiques

Une expression arithmétique peut être :

 Une constante

 Une variable

 <expression_arithmétique> op_arith < expression_arithmétique >

où op_arith désigne un opérateur arithmétique de l'ensemble {+, -, /, *}

Exemple d'expression arithmétique

17, 5*3 + (9-4), a/2 + (b*8)

Exemple d'action d'affectation

S ← 3*a + (b*8)

2.3.2 Les expressions logiques

Une expression logique exp_log est une expression qui peut avoir comme valeur « vrai » ou « faux ».
Elle peut être :

- Une constante booléenne (vraie ou fausse)

- Une variable booléenne

- <exp_arith> op_comp <exp_arith> où op_comp désigne un opérateur de comparaison

appartenant à l'ensemble {<, >, <=, >=, =}

- <exp_log> op_log <exp_log> où op_log est un opérateur logique appartenant à l'ensemble

{ET, OU, NON}

Remarque

On considère exp1 et exp2 deux expressions logiques :

Cours2 : Les actions simples Page 15

 ISET Zaghouan Cours Algorithmique 1

vraie si exp1 est vraie et exp2 est vraie.

exp1 ET exp2
fausse si exp1 est fausse ou exp2 est fausse.

vraie si exp1 est vraie ou exp2 est vraie.

exp1 OU exp2
fausse si non.

vraie si exp est fausse.

NON exp
fausse si non.

Exemple d'expressions logiques

L'expression (x >17) ET (y = 306) vaut vrai si x>17 et y=306. Dans le cas contraire elle vaut faux.

Exemple d'action d'affectation

U ← (x > 17) ET (y = 308)

3. Exercices d’application
3.1 Exercice 1

Quelles seront les valeurs des variables a et b après exécution des actions suivantes ?

Algorithme Ex1
var a,b : entier
Début
a←1
b←a+3
a←3
Fin
3.2 Exercice 2

Quelles seront les valeurs des variables a, b et c après exécution des instructions suivantes ?

Algorithme Ex2
var a, b, c : entier
début
a←5
b←3
c←a+b
a←2
c←b–a
fin

Cours2 : Les actions simples Page 16

 ISET Zaghouan Cours Algorithmique 1

3.3 Exercice 3

Quelles seront les valeurs des variables a et b après exécution des instructions suivantes ?

Algorithme Ex3
var a, b : entier
début
a←5
b←a+4
a←a+1
b←a–4
fin
3.4 Exercice 4

Quelles seront les valeurs des variables a, b et c après exécution des instructions suivantes ?

Algorithme Ex4
var a,b,c :entier
début
a←3
b ← 10
c←a+b
b←a+b
a←c
fin

3.5 Exercice 5

Quelles seront les valeurs des variables a et b après exécution des instructions suivantes ?

Algorithme Ex5
var a,b :entier
début
a←5
b←2
a←b
b←a
fin
Les deux dernières actions permettent-elles d’échanger les deux valeurs de a et b ? Si l’on inverse l’ordre
est-ce que le résultat final change ?

3.6 Exercice 6

Ecrire un algorithme qui permet d’échanger le contenu de deux variables entières x et y.

Cours2 : Les actions simples Page 17

 ISET Zaghouan Cours Algorithmique 1

4. Correction des exercices

4.1 Correction exercice 1

Instructions Valeurs des variables

a←1 a=1 b=?

b←a+3 a=1 b=4

a←3 a=3 b=4

4.2 Correction exercice 2

Instructions Valeurs des variables

a←5 a=5 b= ? c= ?

b←3 a=5 b=3 c=?

c←a+b a=5 b=3 c=8

a←2 a=2 b=3 c=8

c←b–a a=2 b=3 c= 1

4.3 Correction exercice 3

Instructions Valeurs des variables

a←5 a=5 b=?

b←a+4 a=5 b=9

a←a+1 a=6 b=9

b←a–4 a=6 b=2

4.4 Correction exercice 4

Instructions Valeurs des variables

a←3 a=3 b=? c=?

b ← 10 a=3 b = 10 c=?

Cours2 : Les actions simples Page 18

 ISET Zaghouan Cours Algorithmique 1

c←a+b a=3 b = 10 c = 13

b←a+b a=3 b = 13 c = 13

a←c a = 13 b = 13 c = 13

4.5 Correction exercice 5

Instructions Valeurs des variables

a←5 a=5 b=?

b←2 a=5 b=2

a←b a=2 b=2

b←a a=2 b=2

Les deux dernières instructions ne permettent donc pas d’échanger les deux valeurs de b et a,
puisque l’une des deux valeurs (celle de a) est ici écrasée.
Si l’on inverse les deux dernières instructions, cela ne changera rien du tout. En effet, dans ce cas
c’est la valeur de b qui sera écrasée.
4.6 Correction exercice 6

Algorithme Ex5
var x,y,z :entier
début
x←5
y←2
z←x
x←y
y←z
fin

5. L’action de lecture ou d’entrée

Une action de lecture permet à l'utilisateur d'introduire des informations pour effectuer un traitement par
l'ordinateur.
Par exemple, liste de nombres à ordonner, liste de noms d'étudiants à archiver, etc.... Ces informations
sont rangées dans des cases mémoires.

5.1 Syntaxe
L'action de lecture a la forme :

Lire (identificateur de variable)

Cours2 : Les actions simples Page 19

 ISET Zaghouan Cours Algorithmique 1

Ou plus généralement :

Lire (liste d'identificateurs de variables séparés par des virgules ',')

Cette action permet de lire une ou plusieurs valeurs à partir des périphériques d'entrées (par défaut : c'est
le clavier) et puis les ranger dans les cases mémoires associées aux variables identifiées dans l'action.

5.2 Traitement
L'action lire (x) renferme trois opérations internes:

 Lecture d'une valeur à partir du clavier.

 Vérification de la compatibilité du type de la valeur lue avec le type de la variable.

 Ecriture de la valeur dans l'espace mémoire réservé à la variable x.

Remarque

L'action lire (x, y) permet de lire deux valeurs à partir du clavier : la première valeur est pour x et la
deuxième pour y.

6. L’action d’écriture ou de sortie

Une action d'écriture permet d'afficher des résultats sur un périphérique de sortie (par défaut : l'écran).

Un résultat peut être :

 Une chaîne de caractères délimités par des apostrophes

 La valeur d'une variable dont l'identificateur est spécifiée dans l'action

 La valeur d'une expression

6.1 Syntaxe
L'action d'écriture est de la forme :

Ecrire (expression)

Ou plus généralement :

Ecrire (liste d'expressions séparées par des Virgules ',')

Où une expression peut être :

Cours2 : Les actions simples Page 20

 ISET Zaghouan Cours Algorithmique 1

 Une chaîne de caractères délimités par des apostrophes

 Une expression arithmétique.

6.2 Traitement
L'action Ecrire (expression 1, expression2, ..., expression n) amène l'ordinateur, pour chaque i de {1, ...,
n}, à évaluer tout d'abord l'expression numéro i et ensuite à afficher la valeur obtenue.

6.2.1 Exemple
Considérons la séquence suivante d'actions :

Lire(s)
Lire(n)
Ecrire ('La moyenne est: ', s/n)
Pour des valeurs en entrée : 120 et 10, le résultat qui sera affiché est le suivant :

La moyenne est: 12.

6.2.2 Exercice d’application

Ecrire un algorithme qui lit deux variables entières, puis calcule le produit et la somme de ces variables
puis affiche le résultat.

Algorithme calcul
var x, y, p,s : entier
debut
ecrire('donner la valeur de x= ')
lire(x)
ecrire('donner la valeur de y= ')
lire(y)
s←x+y
p←x*y
ecrire('La somme= ',s)
ecrire('Le produit= ',p)
fin

7. Applications
7.1 Exercice 1

Quel résultat produit l’algorithme suivant ?

Algorithme ex1

Cours2 : Les actions simples Page 21

 ISET Zaghouan Cours Algorithmique 1

var x, y : entier
début
x ← 20
y←x*2
ecrire (x)
ecrire (y)
fin
7.2 Exercice 2

Ecrire un algorithme qui demande un nombre à l’utilisateur, puis qui calcule et affiche le carré de ce
nombre.

7.3 Exercice 3

Ecrire un algorithme permettant de calculer et d’afficher le prix d’une marchandise sachant que son prix
hors réduction et le taux de réduction sont saisies au clavier.

7.4 Exercice 4

Ecrire un algorithme permettant de calculer la surface et le périmètre d’un rectangle et de les afficher
sachant que sa longueur et sa largeur sont saisies au clavier.

7.5 Exercice 5

Ecrire un algorithme permettant de calculer et d’afficher la surface et le périmètre d’un cercle sachant que
son rayon est saisi au clavier.

7.6 Exercice 6

Ecrire un algorithme permettant de :

-Lire la valeur de deux entiers a et b.

-Afficher le quotient et le reste de la division entière de a par b.

7.7 Exercice 7

Ecrire un algorithme qui calcule et affiche la résistance équivalente à trois résistances branchées en série
puis en parallèle. Sachant que :

Rsérie  R1  R 2  R3

R1  R 2  R3
R parallèle 
R1  R 2  R1  R3  R 2  R3

7.8 Exercice 8

Ecrire un algorithme qui calcule la somme de quatre entiers saisies au clavier.

 En utilisant une première fois 5 variables

Cours2 : Les actions simples Page 22
 ISET Zaghouan Cours Algorithmique 1

 En utilisant une deuxième fois 2 variables

7.9 Exercice 9

Ecrire un algorithme qui permettant d’échanger le contenu de deux variables entières x et y saisies au
clavier sans utiliser de variables intermédiaires.

8. Corrections des exercices

8.1 Correction exercice 1

On verra apparaître à l’écran 20, puis 40.

8.2 Correction exercice 2

Algorithme carré
var n ,r :entier
Début
Ecrire("Donner un entier:")
Lire(n)
r←n*n
Ecrire("Son carré est : ", r)
Fin
8.3 Correction exercice 3

Algorithme calculPrix
var p ,phr ,taux :réel
Début
Ecrire("Donner le prix hors réduction: ")
Lire(phr)
Ecrire("Donner le taux de réduction: ")
Lire(taux)
p ← (1-taux/100)*phr
Ecrire("Le prix à payer est: ", p)
Fin

8.4 Correction exercice 4

Algorithme rectangle
var l,L,s,p :réel
Début
Ecrire("Donner la longueur du rectangle: ")
Lire(L)
Ecrire("Donner la largeur du rectangle: ")
Lire(l)
s←l*L
p ← (l + L)*2
Ecrire("La surface du rectangle vaut: ",s )
Ecrire("Le périmètre du rectangle vaut: ",p )
Fin
8.5 Correction exercice 5
Cours2 : Les actions simples Page 23
 ISET Zaghouan Cours Algorithmique 1

Algorithme cercle
const pi=3.14
var r,s,p :réel
Début
Ecrire("Donner le rayon du cercle: ")
Lire(r)
s ← pi*r*r
p ← 2*r*pi
Ecrire("La surface du cercle vaut: ",s )
Ecrire("Le périmètre du cercle vaut: ",p )
Fin
8.6 Correction exercice 6

Algorithme calcul
var r,q,a,b :entier
Début
Ecrire("Donner la valeur de a: ")
Lire(a)
Ecrire("Donner la valeur de b: ")
Lire(b)
q ← a div b
r ← a mod b
Ecrire("Le quotient vaut: ",q )
Ecrire("Le reste vaut: ",r)
Fin
8.7 Correction exercice 7

Algorithme calculRésistance
var r1,r2,r3,rs,rp :réel
Début
Ecrire("Donner la valeur de la résistance r1: ")
Lire(r1)
Ecrire("Donner la valeur de la résistance r2: ")
Lire(r2)
Ecrire("Donner la valeur de la résistance r3: ")
Lire(r3)
rs ← (r1+r2+r3)
rp ← (r1*r2*r3)/(r1*r2+r1*r3+r2*r3)
Ecrire("La valeur de la résistance équivalente s’il sont branchées en série est : ",rs )
Ecrire("La valeur de la résistance équivalente s’il sont branchés en parallèle est : ",rp )
fin

8.8 Correction exercice 8

Algorithme saisie5vars
var a1,a2,a3,a4,S: entier
Début
Ecrire("Donner la valeur de l’entier n°1: ")
Lire(a1)
Ecrire("Donner la valeur de l’entier n°2: ")
Lire(a2)

Cours2 : Les actions simples Page 24

 ISET Zaghouan Cours Algorithmique 1

Ecrire("Donner la valeur de l’entier n°3: ")

Lire(a3)
Ecrire("Donner la valeur de l’entier n°4: ")
Lire(a4)
s ← a1+a2+a3+a4
Ecrire("La somme vaut: ", s)
Fin

Algorithme saisie2vars
var a,S: entier
Début
Ecrire("Donner la valeur de l’entier n°1: ")
Lire(a)
s←a
Ecrire("Donner la valeur de l’entier n°2: ")
Lire(a)
s ← s+a
Ecrire("Donner la valeur de l’entier n°3: ")
Lire(a)
s ← s+a
Ecrire("Donner la valeur de l’entier n°4: ")
Lire(a)
s ← s+a
Ecrire("La somme vaut: ", s)
Fin
8.9 Correction exercice 9

Algorithme échange
var x,y: entier
Début
Ecrire("Donner la valeur de x: ")
Lire(x)
Ecrire("Donner la valeur de y: ")
Lire(y)
Ecrire("Avant échange, x= ",x," et y= ",y)
x←x+y
y←x-y
x←x-y
Ecrire("Après échange, x= ",x," et y= ",y)
Fin

Cours2 : Les actions simples Page 25

 ISET Zaghouan Cours Algorithmique 1

Chapitre 3 Les actions conditionnelles

1. Introduction
Ce chapitre présente des actions exploitant les opérations de comparaison qui peuvent être effectuées
par l'ordinateur. Deux actions sont présentées :

 L'action conditionnelle simple qui consiste à évaluer une condition (expression logique à valeur
vrai ou faux) et d'effectuer le traitement relatif à la valeur de vérité trouvée.

 L'action conditionnelle à choix multiple qui consiste à évaluer une expression qui n'est pas
nécessairement à valeur booléenne (elle peut avoir plus de deux valeurs) et selon la valeur
trouvée, effectue un traitement.

2. L’action conditionnelle simple

Une condition est une expression logique. Une action conditionnelle permet d'évaluer une condition et
selon sa valeur elle exécute 0 ou plusieurs actions. Deux formes d'actions conditionnelles sont
considérées.

Forme 1

Si condition Alors
action(s)
Fin si

Dans cette forme, la condition est évaluée. Si elle vaut vrai alors c'est la séquence d'actions qui est
exécutée sinon c'est l'action qui suit l'action conditionnelle dans l'algorithme qui est exécutée.

Forme 2

Si condition Alors
action(s)1
Sinon
action(s)2
Fin si

Dans cette forme, la condition est évaluée. Si elle vaut vrai alors c'est la première séquence d'actions
qui est exécutée sinon c'est la deuxième qui est exécutée.

2.1. Exemple
Ecrire un algorithme qui lit un nombre entier et qui affiche sa valeur absolue.

Cours 3 : Les actions Conditionnelles Page 26

 ISET Zaghouan Cours Algorithmique 1

Algorithme absolue
var n, a : entier
Début
Ecrire("Donner un entier:")
Lire(n)
si (n>0)
alors
a←n
sinon
a ← -n
Ecrire("la valeur absolue de ",n," est : ",a)
Fin

2.2. Exercices d’application

Exercice1

Ecrire un algorithme qui lit trois nombres entiers et qui affiche leur maximum.

Algorithme max3Ver1
var x,y,z,m :entier
Début
Ecrire("Donner la valeur de l’entier n°1: ")
Lire(x)
Ecrire("Donner la valeur de l’entier n°2: ")
Lire(y)
Ecrire("Donner la valeur de l’entier n°3: ")
Lire(z)
si (x>y et x>z) alors
m←x
finsi
si (y>x et y>z) alors
m←y
finsi
si (z>y et z>x) alors
m←z
finsi
Ecrire("Le maximum est: ",m)
Fin

Algorithme max3Ver2
var x,y,z,m :entier
Début
Ecrire("Donner la valeur de l’entier n°1: ")
Lire(x)
Ecrire("Donner la valeur de l’entier n°2: ")
Lire(y)

Cours 3 : Les actions Conditionnelles Page 27

 ISET Zaghouan Cours Algorithmique 1

Ecrire("Donner la valeur de l’entier n°3: ")

Lire(z)
si (x>y et x>z) alors
m←x
sinon
si (y>x et y>z) alors
m←y
sinon
m←z
finsi
finsi
Ecrire("Le maximum est: ",m)
Fin

Exercice 2

Ecrire un algorithme pour la résoudre une équation du premier degré de la forme ax+b=0.

Algorithme equationPremierDegré
var a, b, x : réel
Début
Ecrire ("Donner la valeur de a: ")
Lire(a)
Ecrire ("Donner la valeur de b: ")
Lire(b)
Si (a=0) Alors
Si (b=0) Alors
Ecrire ("L’ensemble des solutions est toute |R")
Sinon
Ecrire ("L’ensemble des solutions est Ø ")
Finsi
Sinon
x ← -b/a
finsi
fin

3. L’action conditionnelle à choix multiple

Une action conditionnelle à choix multiple permet d'exécuter un bloc d'actions parmi plusieurs selon
la valeur produite par une expression qui joue le rôle d'un sélecteur.

La forme générale de cette action est la suivante:

Selon <sélecteur> faire

valeur1 : action(s)
valeur2 : action(s)
valeur3 : action(s)

Cours 3 : Les actions Conditionnelles Page 28

 ISET Zaghouan Cours Algorithmique 1

valeurn : action(s)
Sinon action(s) /* facultative */
Fin selon

Le préfixe sinon peut ou non apparaître et il regroupe les valeurs qui n'ont pas été explicitement
spécifiées. Il constitue le dernier choix.

Exemple 1

Ecrire un algorithme qui saisit un entier compris entre 0 et 9 et affiche cet entier en toute lettre.

Algorithme entierLettre
var n : entier
Début
Ecrire("Donner la valeur de l’entier: ")
Lire(n)
Selon (n) faire
1 : Ecrire("L’entier saisie est: un")
2 : Ecrire("L’entier saisie est: deux")
3 : Ecrire("L’entier saisie est: trois")
4 : Ecrire("L’entier saisie est: quatre")
5 : Ecrire("L’entier saisie est: cinq")
6 : Ecrire("L’entier saisie est: six")
7 : Ecrire("L’entier saisie est: sept")
8 : Ecrire("L’entier saisie est: huit")
9 : Ecrire("L’entier saisie est: neuf")
Fin selon
fin

Exemple 2

Ecrire un algorithme qui saisit un numéro de couleur de l’arc-en-ciel et d’afficher la couleur

correspondante. 1-rouge, 2-orangé, 3-jaune, 4-vert, 5-bleu, 6-indigo, 7-violet.

Algorithme arc-en-ciel
var c : entier
Début
Ecrire("Donner l’ordre de la couleur: ")
Lire(c)
Selon (c) faire
1 : Ecrire("La couleur correspondante est: rouge")
2 : Ecrire("La couleur correspondante est: orangé")
3 : Ecrire("La couleur correspondante est: jaune")
4 : Ecrire("La couleur correspondante est: vert")
5 : Ecrire("La couleur correspondante est: bleu")
6 : Ecrire("La couleur correspondante est: indigo")
7 : Ecrire("La couleur correspondante est: violet")

Cours 3 : Les actions Conditionnelles Page 29

 ISET Zaghouan Cours Algorithmique 1

fin selon
fin

4. Exercices d’application
4.1 Exercice 1

Ecrire un algorithme qui saisit un entier relatif et permettant de déterminer s’il est positif, négatif ou nul.

4.2 Exercice 2

Ecrire un algorithme qui demande la saisie de deux nombres à l’utilisateur et affiche le signe de leur
produit.

Note : ne pas calculer le produit des deux nombres.

4.3 Exercice 3

Ecrire un algorithme qui demande l’âge d’un enfant à l’utilisateur. Ensuite, il l’informe de sa catégorie :

 "Poussin" de 6 à 7 ans
 "Pupille" de 8 à 9 ans
 "Minime" de 10 à 11 ans
 "Cadet" après 12 ans

4.4 Exercice 4

Ecrire un algorithme permettant de résoudre une équation du second degré de la forme ax 2  bx  c  0 .

5. Corrections des applications

5.1 Correction exercice 1

Algorithme signe
var n : entier
Début

Ecrire("Donner la valeur de l’entier: ")

Lire(n)
Si (n>0) Alors
Ecrire("l’entier saisie est positif")
Sinon
si (n<0) Alors
Ecrire("l’entier saisie est négatif")
sinon
Ecrire("l’entier saisie est nul")
Finsi
Cours 3 : Les actions Conditionnelles Page 30
 ISET Zaghouan Cours Algorithmique 1

Finsi

fin
5.2 Correction exercice 2

Algorithme Signeproduit
var a,b : entier
Début
Ecrire("Donner la valeur de l’entier a: ")
Lire(a)
Ecrire("Donner la valeur de l’entier b: ")
Lire(b)
Si (a>0 et b>0) ou (a<0 et b<0) Alors
Ecrire("le signe du produit est positif")
Sinon
Ecrire("le signe du produit est négatif")
Finsi
fin
5.3 Correction exercice 3

Algorithme catégorie
var a : entier
Début
Ecrire("Donner l’âge de l’enfant: ")
Lire(a)
Si (a>=12) Alors
Ecrire("Catégorie Cadet")
Sinon Si (age>=10) Alors
Ecrire("Catégorie Minime")
Sinon Si (age>=8) Alors
Ecrire("Catégorie Pupille")
Sinon Si (age>=6) Alors
Ecrire("Catégorie Poussin")
Finsi
Finsi
Finsi
Finsi
fin

5.4 Correction exercice 4

Algorithme equationSecondDegré
var a,b,c,x1,x2,d :réel
Début
Ecrire("Donner la valeur de a: ")
Lire(a)
Ecrire("Donner la valeur de b: ")
Lire(b)
Ecrire("Donner la valeur de c: ")
Lire(c)

Cours 3 : Les actions Conditionnelles Page 31

 ISET Zaghouan Cours Algorithmique 1

Si (a=0) Alors
Si (b=0) Alors
Si (c=0) Alors
Ecrire("L’ensemble des solutions est toute |R")
Sinon
Ecrire("L’ensemble des solutions est Ø")
Finsi
Sinon
x1 ← -c/b
Ecrire("solution unique x=",x1)
Finsi
Sinon
d ← b*b-4*a*c
Si (d=0) Alors
x1 ← -b/(2*a)
Ecrire("solution double x=",x1)
Sinon Si (d>0) Alors
x1 ← (-b-sqrt(d))/(2*a)
x1 ← (-b+sqrt(d))/(2*a)
Ecrire("solution distinctes x1=",x1," et x2= ",x2)
Sinon
Ecrire("pas de solutions dans |R")
Finsi
Finsi
Finsi
fin

Cours 3 : Les actions Conditionnelles Page 32

 ISET Zaghouan Cours Algorithmique 1

Chapitre 4 Les actions itératives

1. Introduction
Ce chapitre présente les actions qui permettent de répéter un traitement (séquence d'actions) un
nombre de fois connu ou inconnu à l'avance.

On trouve ainsi, pour le nombre de fois inconnu à l'avance, les actions suivantes :

 Tant que qui permet de répéter un traitement tant qu'une condition est vraie.

 Répéter qui permet de répéter un traitement jusqu'à ce qu'une condition devienne vraie.

 Pour qui permet de répéter un traitement un nombre de fois connu à l'avance.

2. L’action "Tant que"

L'action itérative (ou répétitive ou de répétition) Tant que permet de répéter l'exécution d'un bloc d'actions
0 ou plusieurs fois.

2.1. Syntaxe
Elle a la syntaxe suivante :

Tant que condition faire

action (s)

Fin tant que

Où condition est une expression logique.

2.2. Traitement
Tant que la condition fournit la valeur vrai, le bloc d'actions est exécuté et on revient pour répéter la
même chose. Si la condition fournit la valeur faux alors c'est l'action qui suit l'action tant que dans
l'algorithme est exécutée.

2.3. Exemple
Algorithme saisiePositif
var n : entier
Début
n ← -1

Tant que (n<0)

Cours 4 : Les actions itératives Page 33
 ISET Zaghouan Cours Algorithmique 1

Ecrire("Donner une valeur positive de n: ")

Lire(n)
Fin tant que
Ecrire("Bravo, vous avez saisie l’entier positif : ",n)
fin

2.4. Exercice d’application

Ecrire un algorithme qui demande à l’utilisateur un nombre compris entre 1 et 10 jusqu’à ce que la réponse
convienne.
Algorithme saisieInterval
var n : entier
Début
n←0
Tant que (n<0)
Ecrire("Donner un entier compris entre 1 et 10")
Lire(n)
Si (n<1 ou n>10) Alors
Ecrire("Saisie erronée. Recommencez svp !!")
finsi
Fin tant que
fin

3. L’action "Répéter"
L'action itérative (répétitive ou de répétition) répéter permet de répéter l'exécution d'un bloc d'actions une
ou plusieurs fois.

3.1. Syntaxe
L'action Répéter a la forme générale suivante :

Répéter

action (s)

Jusqu’à condition

3.2. Traitement
Le bloc d'actions est exécuté la première fois. Ensuite la condition est évaluée. Tant que la condition
fournit la valeur vraie, le bloc d'actions est exécuté.

Autrement dit le bloc d'actions continu à s'exécuter au moins une fois et jusqu'à ce que la condition
devienne fausse.

Tableau comparatif entre les actions itératives tant que et répéter

Cours 4 : Les actions itératives Page 34

 ISET Zaghouan Cours Algorithmique 1

Tant que Répéter

La condition est évaluée avant le bloc d'actions La condition est évaluée après le bloc d'actions

Le bloc d'actions est exécuté au moins 0 fois Le bloc d'actions est exécuté au moins 1 fois

3.3. Exemple
Algorithme saisiePositif
var n : entier
Début
Répéter
Ecrire("Donner une valeur positive de n: ")
Lire(n)
jusqu’à (n>0)
Ecrire("Bravo, vous avez saisie l’entier positif : ",n)
fin

3.4. Exercice d’application

Ecrire un algorithme qui demande à l’utilisateur un nombre compris entre 1 et 10 jusqu’à ce que la réponse
convienne.
Algorithme saisieInterval
var n : entier
Début
Répéter
Ecrire("Donner un entier compris entre 1 et 10")
Lire(n)
Si (n<1 ou n>10) Alors
Ecrire("Saisie erronée. Recommencez svp !!")
finsi
jusqu’à (n>=1 et n<=10)
fin
4. L’action "Pour"
L'action itérative (ou répétitive ou de répétition) pour permet d'exécuter un bloc d'actions un nombre n
de fois connu à l'avance avec n>=0.

4.1. Syntaxe
L'action Pour a la forme générale suivante :

Pour compteur de valeur initiale à valeur finale [pas valeur] faire

action (s)
Fin pour

Cours 4 : Les actions itératives Page 35

 ISET Zaghouan Cours Algorithmique 1

4.2. Traitement
Un compteur identifié par un identificateur de variable est initialisé à <valeurInitiales> et qui
s'incrémente jusqu'à atteindre <valeur finale>.

Le traitement est répété de <valeur compteur> égale à <valeur initiales> jusqu'à <valeur compteur> égale à
<valeur finale>.

Initialement le compteur reçoit <valeur initiale>. Ensuite les actions suivantes sont répétées

Évaluer la condition <valeur compteurs> <= <valeur finale> si le pas est positif, et <valeur
compteur> >= <valeur finale> si le pas est négatif.

Si la condition est évaluée à vrai alors

 le bloc d'actions est exécuté

 la valeur du compteur est mise à jour avec le pas d'incrémentation et cette étape est répétée.

Une fois la condition devient fausse, l'action suivante à exécuter est celle qui suit l'action pour.

Remarque

 [Pas valeur] est optionnel. Il explicite le pas d'incrémentation quand il est positif et de
décrémentation quand il est négatif.

 Le pas d'incrémentation est un nombre entier relatif (quand il est négatif, c'est une
décrémentation). Par défaut le pas d'incrémentation est égale à 1, dans quel cas on n'a pas à
spécifier <pas valeurs>.

4.3. Exemple
Algorithme message
var i : entier
Début
Pour i de 1 à n faire
Ecrire("Bonjour ",i," fois")
Fin pour
fin

4.4. Exercices d’application

Ecrire un algorithme pour calculer la somme des n premiers entiers. La valeur de n étant saisie au clavier.

Algorithme SommeEntier
var n,s : entier
Début

Cours 4 : Les actions itératives Page 36

 ISET Zaghouan Cours Algorithmique 1

s←0
Répéter
Ecrire("Donner une valeur positive de n: ")
Lire(n)
jusqu’à (n>0)
Pour i de 1 à n faire
s ← s+i
Fin pour
Ecrire("La somme vaut: ",s)
Fin

5. Exercices d’application
5.1 Exercice 1

Ecrire un algorithme pour calculer la factorielle d’un entier en s'assurant que l'entier est > 0.

Notez que n!=n*(n-1)! et que 0!=1.

5.2 Exercice 2

Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu’à ce que la réponse convienne. En cas
de réponse supérieure à 20, on fera apparaître un message : « Plus petit ! », et inversement, « Plus grand ! » si le
nombre est inférieur à 10.
5.3 Exercice 3

Ecrire un algorithme qui calcul et affiche la moyenne des notes d'une classe

5.4 Exercice 4

Ecrire un algorithme qui saisit un entier et affiche sa table de multiplication.

5.5 Exercice 5

Ecrire un algorithme permettant de vérifier si un entier saisi au clavier est premier ou non.

5.6 Exercice 6

On considère la suite de Fibonacci dont le terme général est le suivant :

F0  0
F1  F2  1
Fn  Fn1  Fn2

C’une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent.

Ecrire un algorithme permettant de calculer la valeur de la suite à l’ordre n.

5.7 Exercice 7

Cours 4 : Les actions itératives Page 37

 ISET Zaghouan Cours Algorithmique 1

On considère la suite suivante :

U1  1
1 n
U n1   (U n  )
2 Un
Cette suite converge vers racine carrée de n.

Ecrire un algorithme permettant de calculer la racine carrée d’un entier positif saisi au clavier en utilisant
cette suite.

6. Correction exercices d’application

6.1 Correction exercice 1

Algorithme factorielle
var n,f : entier
Début
f←1
Répéter
Ecrire("Donner une valeur positive de n: ")
Lire(n)
jusqu’à (n>0)
Pour i de 1 à n faire
f ← f*i
Fin pour
Ecrire("La factorielle de ",n," est: ",f)
fin
6.2 Correction exercice 2

Algorithme saisieIntervalle
var n : entier
Début
Répéter
Ecrire("Donner un entier compris entre 10 et 20: ")
Lire(n)
Si (n<10) Alors
Ecrire("Plus grand !")
Sinon
Si (n>20) Alors
Ecrire("Plus petit !")
FinSi
Finsi
jusqu’à (n>=10 et n<=20)
fin
6.3 Correction exercice 3

Algorithme saisieIntervalle
const N 30
var note,i,s : entier
m :réel
Début
s←0

Cours 4 : Les actions itératives Page 38

 ISET Zaghouan Cours Algorithmique 1

pour i de 1 à N faire
Ecrire("Donner la note de l’étudiant n°",i, ": ")
Lire(note)
s ← s + note
fin pour
m ← m/N
Ecrire("La moyenne de la classe est: ",m)
fin
6.4 Correction exercice 4

Algorithme tableMultiplication
var n,i,p : entier
Début
Ecrire("Donner la valeur de n= ")
Lire(n)
pour i de 1 à n faire
p ← n*i
Ecrire(n,"*",i,"= ",p)
fin pour
fin
6.5 Correction exercice 5

Algorithme premier
var n,i : entier
p : booléen
Début
Répéter
Ecrire("Donner un entier positif: ")
Lire(n)
Jusqu’à (n>0)
p ← vrai
Si (n=0 ou n=1) alors
p ← faux
finsi
pour i de 2 à (n/2) faire
si (n mod i =0) alors
p ← faux
finsi
finpour
si (p=vrai) alors
ecrire("L’entier ",n," est premier")
sinon
ecrire("L’entier ",n," est non premier")
finsi
fin

6.6 Correction exercice 6

Algorithme Fibonacci
var u,v,w,n : entier
Début
Répéter
Ecrire("Donner l’ordre de la suite : ")
Lire(n)

Cours 4 : Les actions itératives Page 39

 ISET Zaghouan Cours Algorithmique 1

Jusqu’à (n>=3)
u←1
v←1
pour i de 1 à (n-2) faire
w ← u+v
U←v
v←w
fin pour
ecrire("la suite à l’ordre ",n," vaut: ",w)
fin

6.7 Correction exercice 7

Algorithme racineCarrée
var n: entier
u,v :réel
conv : booléen
Début
Répéter
Ecrire("Donner un entier strictement supérieur à 1: ")
Lire(n)
Jusqu’à (n>1)
u←1
conv ← faux
Répéter
v ← 1/2(u+n/u)
si (abs(u-v)>0,01) alors
u←v
sinon
conv ← vrai
finsi
jusqu’à (abs(u-v)<=0,01) et conv=vrai)

Ecrire("la racine carrée de ",n," vaut: ",v)

fin

Cours 4 : Les actions itératives Page 40

 ISET Zaghouan Cours Algorithmique 1

Chapitre5 Les tableaux

1. Introduction
Nous avons vu et manipulé dans les chapitres précédents les types simples de données à savoir les
types : entier, réel, caractère et booléen. Il existe des types de données composés construits sur la base des
types simples pour structurer plusieurs informations ayant des types simples. Nous allons voir dans ce
chapitre le type tableau comme type composé. Plus particulièrement les tableaux à une ou à deux
dimensions.

Pour chacun des types, nous présentons la déclaration, la manipulation et quelques exemples
d'utilisation.

2. Définition d’un tableau

Un tableau est une structure de données homogène qui sert à stocker, dans une même variable, un
nombre fini d'éléments de même type.

En mémoire, est associé à cette variable un espace mémoire dimensionné à un nombre fini de cases
consécutives pouvant contenir ces éléments. La variable identifiée est de type tableau.

Nous distinguons deux types de tableau : les tableaux à une dimension et les tableaux à deux dimensions.

3. Tableaux à une dimension

3.1. Déclaration
var identificateur : Tableau [indice 1.. indice2] de type_contenu

Exemple

var T : Tableau [l.. 10] de entier

On vient de déclarer un tableau de 10 entiers.

3.2. Accès à un élément du tableau

Les cases d'un tableau à une dimension sont accessibles en utilisant l'identificateur de la variable ainsi
que l'indice (ou le numéro de la case) comme référence. Cet indice doit être entre indice1 et indice2.

Tab[expression] désigne une case du tableau Tab. Le numéro de la case est donné par la valeur de
l'expression.

Exemple

Cours 5 : Les Tableaux Page 41

 ISET Zaghouan Cours Algorithmique 1

On considère le tableau T déclaré ci-dessus, alors :

T [2] désigne la case numéro 2 du tableau T

T [10] désigne la case numéro 10 du tableau T

T[i] désigne la case numéro i du tableau T avec i une variable devant avoir une valeur entre 1 et 10.

4. Tableaux à deux dimension

4.1. Déclaration

Var identificateur:Tableau [indice_lig_1.. indice_lig_2, indice_col_1.. indice_col_2] de type_contenu

Exemple:

var M : Tableau[1 .. 5 , 1 .. 3] de entier

On vient de déclarer une matrice de 5 lignes et 3 colonnes.

4.2. Accès à un élément d’une matrice

Les cases d'un tableau à deux dimensions sont accessibles en utilisant l'identificateur du tableau,
l'indice de la ligne et l'indice de la colonne comme référence.

Le premier indice doit être entre indice_lig_1 et indice_lig_2 et le deuxième doit être entre
indice_col_1 et indice_col_2.

M[exp1, exp2] désigne la case du tableau M. Le numéro de ligne de cette case est la valeur de exp1 et
le numéro de la colonne est la valeur de exp2.

Exemple

On considère le tableau M déclaré ci-dessus, alors :

M[2, 3], désigne la case de la ligne 2 et la colonne 3 du tableau M.

M[i, j], désigne la case de la ligne i et de la colonne j du tableau à deux dimensions M avec i (resp. j) une variable
ayant des valeurs entre 1 et 5 (resp. entre 1 et 3).

Cours 5 : Les Tableaux Page 42

 ISET Zaghouan Cours Algorithmique 1

5. Exemples

5.1. Exemple 1
On désire calculer la moyenne des notes de 8 étudiants.

Algorithme moyenne_8_etu_version1_avec tableau

var Note : Tableau [1.. 8] de réel
i : entier
S, M : réel
début
S←0
Pour i de 1 à 8 faire
Ecrire('Note de l'étudiant numéro ',i,' :')
Lire(Note[i])
S ← S + Note[i]
Fin pour
M = S/8
Ecrire ( La moyenne de la classe est : ',M)
Fin

Dans le cas de cet exemple l'utilisation de la structure de données tableau n'est pas nécessaire comme on n'a
pas besoin de garder une trace des nombres saisis pour un traitement qui suit. On peut avoir une version en utilisant
une seule variable réelle Note.

Algorithme moyenne_8_etu_version2_sans_tableau
var Note, S, M : réel
i : entier
Début
S←0
Pour i de 1 à 8 faire
Ecrire ('Note de l'étudiant numéro ',i,' :')
Lire (Note)
S ← S + Note
Fin pour
M = S/8
Ecrire ( La moyenne de la classe est : ',M)
Fin

5.2. Exemple2
Ecrire un algorithme qui calcule la moyenne des notes de 8 étudiants et affichage du nombre d'étudiants ayant une
note supérieure ou égale à cette moyenne. Cet exemple nécessite un enregistrement des notes saisies.

Algorithme moyenne_affichage_nombre
var Note : Tableau [1.. 8] de réels
S, M, i : entier
Cours 5 : Les Tableaux Page 43
 ISET Zaghouan Cours Algorithmique 1

Début
S←0
Pour i de 1 à 8 faire
Ecrire ('Note de l'étudiant numéro ',i,' :')
Lire (Note[i])
S ← S+N[i]
Fin pour
M=S/8
Ecrire ('La moyenne de la classe est ', M)
S←0
Pour i de 1 à 8 faire
Si (Note[i]>=M) Alors
S←S + 1
Fin Si
Fin pour
Ecrire('Le nombre d'étudiants ayant une note supérieure ou égale à la moyenne : ', M, 'est :',S)
Fin

5.3. Exemple 3
Ecrire un algorithme pour calculer le produit scalaire de deux vecteurs de taille 10.

Algorithme produit_scalaire
Type Tab: tableau [1 ...10] de entier
Var v1, v2: Tab
S, i : entier
Début
S←0
Pour i de 1 à 10 faire
Ecrire ('entrer élément num',i,' du vecteur V1 : ')
Lire (v1[i])
Ecrire ('entrer élément num',i , ' du vecteur V2 : ')
Lire (v2[i])
S ← S + v1[i]*v2[i]
Fin pour
Ecrire ('Le produit scalaire des deux vecteurs est : ', S)
Fin
6. Recherche séquentielle
La recherche séquentielle d'un élément dans un tableau consiste à parcourir les cases du tableau du début jusqu'à
la fin, et de comparer à chaque fois l'élément contenu dans la case à l'élément recherché.

Une fois l'élément est trouvé, l'algorithme s'arrête et affiche une réponse positive. Si le tableau a été entièrement
parcouru sans que l'élément soit trouvé, une réponse négative est, dans ce cas, affichée.

7. Exercices
Exercice 1

Cours 5 : Les Tableaux Page 44

 ISET Zaghouan Cours Algorithmique 1

Ecrire un algorithme permettant de remplir un tableau d’entier de taille N et permettant de vérifier si un entier
saisie existe dans le tableau ou pas.

Algorithme recherche_séquentielle
const N = 10
var x,i : entier
T : Tableau[1..N] de entier
Début
i←1
Tant que (i<=N) faire
Ecrire('Donner l'élément numéro ', i)
Lire(T[i])
i←i+1
Fin Tant que
Ecrire('Donner la valeur à chercher: ')
Lire (X)
i←1
Tant que (T[i]<>x et i<=N) faire
i ← i+1
Fin Tantque
Si (i>N) Alors
Ecrire (x," n’existe pas dans ce tableau")
Sinon
Ecrire (x," est un élément du tableau")
Fin si
fin

Exercice 2

Ecrire un algorithme calculant la somme des valeurs d’un tableau d’entiers.

Algorithme sommeTab
const N = 10
var i,S : entier
T : Tableau[1..N] de entier
Début
S←0
pour i de 1 à N faire
Ecrire('Donner l'élément n°', i,': ')
Lire(T[i])
S ← S + T[i]
Fin Tant que
Ecrire('Somme= ', S)
fin

Cours 5 : Les Tableaux Page 45

 ISET Zaghouan Cours Algorithmique 1

Exercice 3
Ecrire un algorithme calculant le produit des valeurs d’un tableau d’entiers.

Algorithme produitTab
const N = 10
var i,p : entier
T:Tableau[1..N] de entier
Début
p←1
pour i de 1 à N faire
Ecrire('Donner l'élément n°', i,': ')
Lire(T[i])
p ← p * T[i]
Fin Tant que
Ecrire('produit= ', p)
fin

Exercice 4

Ecrire un algorithme qui calcule la somme de deux matrices carrées de tailles N.

Algorithme sommeMatrice
const N = 10
var i,j : entier
A,B,S:Tableau[1..N,1..N] de entier
Début
pour i de 1 à N faire
pour j de 1 à N faire
Ecrire('Donner l'élément A[', i,',',j, ']: ')
Lire(A[i][j])
Ecrire('Donner l'élément B[', i,',',j, ']: ')
Lire(B[i][j])
S[i][j] ← A[i][j]+B[i][j]
Fin pour
Fin pour
Ecrire('la matrice somme=')
pour i de 1 à N faire
pour j de 1 à N faire
Ecrire(S[i][j], ' ')
Fin pour
Ecrire('') //retour à la ligne
finpour
fin

Exercice 5

Cours 5 : Les Tableaux Page 46

 ISET Zaghouan Cours Algorithmique 1

Ecrire un algorithme qui calcule la transposée d’une matrice carrée tailles N.

Algorithme transposéeMatrice
const N = 10
var i,j : entier
A,T:Tableau[1..N,1..N] de entier
Début
pour i de 1 à N faire
pour j de 1 à N faire
Ecrire('Donner l'élément A[', i,',',j, ']: ')
Lire(A[i][j])
T[j][i] ← A[i][j]
Fin pour
Fin pour
Ecrire('la matrice transposée=')
pour i de 1 à N faire
pour j de 1 à N faire
Ecrire(T[i][j], ' ')
Fin pour
Ecrire('') //retour à la ligne
Fin pour
fin

Cours 5 : Les Tableaux Page 47

 ISET Zaghouan Cours Algorithmique 1

Chapitre 6 Les chaînes de caractères

1. Introduction
Ce chapitre présente le type de données chaîne de caractères qui peut être manipulé comme un tableau de
caractères mais qui diffère dans la déclaration.

2. Définition d’une chaîne de caractères

Une chaîne de caractères est une structure de données homogène qui sert à stocker, dans une même variable, un
nombre fini d'éléments de types caractères.

3. Déclaration
var identificateur : chaine

Exemple

var nom : chaine

4. Accès à une case

Les cases d'une chaîne de caractères sont accessibles en utilisant l'identificateur de la variable chaîne et le numéro
de la case.

Exemple :

nom[1], nom[8]

5. Fonctions prédéfinies sur les chaînes de caractères

5.1. La fonction Longueur

Après la saisie d'une chaîne de caractères, le nombre de caractères lus est donné par la fonction Longueur
(identificateur) où identificateur est le nom de la variable chaîne.

Exemple :

Longueur ('Bonjour') renvoie 7.

5.2. La fonction ASC

Elle renvoie le code ASCII correspondant à un caractère donné.

Exemple:

Cours 6 : Les chaînes de caractères Page 48

 ISET Zaghouan Cours Algorithmique 1

ASC('A') renvoie 65.

5.3. La fonction CHR

Elle renvoie le caractère correspondant à un code ASCII donné.

Exemple:

CHR('65') renvoie A.

6. Exercices d’application
Exercice 1

Ecrire un algorithme qui demande un mot à l’utilisateur et qui affiche le nombre de lettres de ce mot.
Réponse

Algorithme Nb_lettre
var mot: chaîne
n: entier
Début
Ecrire('Donner un mot: ')
Lire(mot)
n ← Longueur(mot)
Ecrire('Ce mot contient ',n,' lettres')
Fin

Exercice 2

Ecrire un algorithme permettant de lire une chaîne de caractères et d'afficher le nombre d'occurrences d'un caractère
donné.

Réponse

Algorithme Nb_occurrences
var ch: chaîne
c: caractère
n, i: entier
Début
Ecrire('Donner une chaîne de caractères: ')
Lire(ch)
Ecrire('Donner le caractère recherché: ')
Lire(c)
n←0
i←1
Tant que (i<=Longueur(ch)) Faire
Si (ch[i]=c) Alors
n←n+1

Cours 6 : Les chaînes de caractères Page 49

 ISET Zaghouan Cours Algorithmique 1

Fin Si
i←i+1
Fin Tant que
Ecrire ("Le nombre d'occurrences du caractère: " , c, " dans la chaîne " , ch, , " est: " ,n)
Fin

Exercice 3

Ecrire un algorithme qui demande une phrase à l’utilisateur et qui affiche à l’écran le nombre de
mots de cette phrase. On suppose que les mots ne sont séparés que par des espaces.
Réponse

Algorithme Nb_mots
var ph: chaîne
n,i: entier
Début
Ecrire('Donner votre phrase: ')
Lire(ph)
n←0
pour de 1 à Longueur(ph) Faire
Si (ph[i]=" ") Alors
n←n+1
Fin Si
Fin Pour
Ecrire ("votre phrase contient: ", n+1, " mots")
Fin

Exercice 4

Ecrire un algorithme qui demande une phrase à l’utilisateur et qui affiche à l’écran le nombre de voyelles
(a,e,i,o,u,y) contenues dans cette phrase.
Réponse

Algorithme Nb_voyelles
var ph: chaîne
n,i: entier
Début
Ecrire('Donner votre phrase: ')
Lire(ph)
n←0
pour de 1 à Longueur(ph) Faire
Si (ph[i]="a" ou ph[i]="e" ou ph[i]="i" ou ph[i]="o" ou ph[i]="u" ou ph[i]="y") Alors
n←n+1
Fin Si
Fin Pour
Ecrire ("votre phrase contient: ", n, " voyelles")
Fin

Cours 6 : Les chaînes de caractères Page 50

 ISET Zaghouan Cours Algorithmique 1

Chapitre 7 : Les procédures et les fonctions

1. Introduction
Quand on a à écrire un algorithme pour la résolution d'un problème complexe, nous avons intérêt à
décomposer le problème en des sous- problèmes. Pour chacun de ces sous problèmes on écrit un sous-programme
qui sera appelé par l'algorithme principal. Un sous-programme peut être une procédure ou une fonction.

Un sous-programme est spécifié par un nom et éventuellement une liste de paramètres formels (paramètres
déclaratifs). Les paramètres formels, s'ils existent, ils spécifient des données et/ou des résultats du sous problème à
résoudre.

2. Les procédures
L'action itérative (ou répétitive ou de répétition) Tant que permet de répéter l'exécution d'un bloc
d'actions 0 ou plusieurs fois.

2.1. Déclaration
Une procédure a la forme générale suivante :

Procédure Nom (liste de paramètres formels avec leurs types séparés par des ',')
Déclaration des variables locale de la procédure
Début
Liste des actions de la procédure
Fin

2.2. Types et modes de passage des paramètres

2.2.1. Types des paramètres formels

Il existe trois types de paramètres dans un sous-programme :

 Paramètres données : ils ne changent pas de valeur dans le sous-programme. Leurs valeurs sont
plutôt utilisées.

 Paramètres résultats : ils n'ont une signification qu'après l'exécution du sous-programme.

 Paramètres données / résultats : ils ont une valeur avant l'exécution du sous-programme et qui
peut changer après l'exécution.

2.2.2. Modes de passage des paramètres formels

Il existe deux modes de passage de paramètres :

Cours 7 : Les Procédures et les Fonctions Page 51

 ISET Zaghouan Cours Algorithmique 1

 Passage par valeur : (paramètres données) le paramètre formel représente une variable locale au
sous-programme et tout changement de paramètre n'a pas d'effet sur le paramètre effectif. A
l'appel, les valeurs des paramètres effectifs sont récupérés dans les paramètres formels sur lesquels
le traitement s'effectue.

Dans la déclaration suivante :

procedure test(p1:type1, p2:type2,…, pn:typen) les paramètres p1,p2,…, pn sont passés par valeur.

 Passage par adresse : (paramètres données/résultats ou paramètres résultats) le principe consiste

à associer aux paramètres formels l'adresse des paramètres effectifs. Toute modification apportée
aux paramètres formels affecte les paramètres effectifs.

Dans la déclaration suivante :

procedure test(p11:type11, p12:type12,…, p1n:type1n ,varp21:type21, var p22:type22,…,var p2n:type2n)

les paramètres p11,p12,…, p1n sont passés par valeur et les paramètres p21,p22,…, p2n sont passés par
adresse.

Remarque

Les paramètres passés par adresse sont précédés du mot clé var.

2.2.3. Appel d’une procédure

Dans un algorithme principal, une procédure est appelée dans une action en spécifiant son nom et ses
paramètres qui deviennent des paramètres effectifs avec le mode de passage respectif (ou réels).

Ainsi, si une procédure est déclarée avec l'entête

procédure test(p11:type11, p12:type12,…, p1n:type1n ,varp21:type21, var p22:type22,…,var p2n:type2n) alors, au

moment de l'appel avec les paramètres réels ou effectifs q11,…,q1n passés par valeur et les paramètres q21,
...q2n passés par adresse, l'action prend la forme :

test(q11,…,q1n,&q21,…,&q2n)

Remarque

Les paramètres formels et les paramètres effectifs peuvent porter le même nom.

2.2.4. Exemple d'un appel d'une procédure

Ecrire une procédure pour le calcul et l'affichage de la somme des n premiers entiers.

Cours 7 : Les Procédures et les Fonctions Page 52

 ISET Zaghouan Cours Algorithmique 1

Procédure Somme (n : entier)

Var i, S : entier
Début
S←0
Pour i de 1 à n faire
S←S+i
Fin pour
Ecrire ('la somme des ',n,' premiers entiers est: ',S)
Fin

Un algorithme principal qui fait appel à cette procédure effectue la saisie d'une valeur pour n et
fait appel à la procédure dans une action en spécifiant le nom de la procédure et une valeur de n qui
devient un paramètre effectif

Algorithme calculSommeN_premiers_Entiers
Var n : entier
Début
Ecrire ('Donner une valeur pour n ')
Lire(n)
Somme(n)
Fin

2.3. Exercices d’application

Exercice1

Ecrire une procédure qui permet de calculer la factorielle d'un entier positif n.

procédure factoriel(n : entier, var f : entier)

var i : entier
Début
f←1
i←1
Tant que (i<=n) faire
f←f*i
i←i+1
Fin Tantque
Fin

Un algorithme principal qui fait appel à cette procédure pour calculer et afficher la factorielle d'un
nombre entier saisi au clavier peut être le suivant :

Algorithme factoriel_principal
Var i, n, fact : entier
Début
Répéter
Ecrire ('Entrer un entier :')
Cours 7 : Les Procédures et les Fonctions Page 53
 ISET Zaghouan Cours Algorithmique 1

Lire (n)
Jusqu'à (n>= 0)
factoriel(n,fact)
Ecrire (' La factorielle de ',n,' est = ', fact )
Fin

Exercice 2

Ecrire une procédure qui permet d’échanger le contenu de deux variables entières x et y reçu en
paramètre.

procédure echange(var a:entier,var b:entier)

var tmp : entier
Début
tmp ← a
a←b
b ← tmp
fin

Algorithme echange_principal
Var x,y : entier
Début
Ecrire('Donner la valeur de x:')
Lire(x)
Ecrire('Donner la valeur de y:')
Lire(y)
Ecrire('avant appel de la procédure x= ',x,' et y= ',y)
Echange(x,y)
Ecrire('après appel de la procédure x= ',x,' et y= ',y)
Fin

3. Les fonctions
Une fonction est un sous-programme qui rend un résultat unique de type scalaire (entier, réel,
caractère, booléen).

3.1. Déclaration
Une fonction a la forme générale suivante :

Fonction Nom (liste de paramètres formels avec leurs types séparés par des ',') : type_résultat
Déclaration des variables locale de la Fonction
Début
Liste des actions de la fonction
Fin

Remarque

Cours 7 : Les Procédures et les Fonctions Page 54

 ISET Zaghouan Cours Algorithmique 1

Les paramètres formels de la fonction ne peuvent être que des paramètres donnés.

3.2. Appel d'une fonction

Comme une fonction rend un résultat unique, son appel s'effectue dans un algorithme principal en
affectant le résultat retourné à une variable déclarée dans cet algorithme.

L'appel prend la forme suivante :

Identificateur ← Nom_fonction(listeDeParamètresEffectifs)

Remarque

Les types de la variable identifiée et du résultat retourné doivent être compatibles.

3.3. Exemple d'une fonction

Une fonction pour le calcul de la somme des n premiers entiers.

fonction Somme (n : entier) : entier

var i, S : entier
Début
S←0
Pour i de 1 à n faire
S←S+i
Fin pour
Somme ← S
Fin
Un algorithme principal qui fait appel à cette fonction effectue la saisie d'une valeur pour n et fait
appel à la fonction dans une action qui affecte le résultat qu'elle retourne à une variable déclarée dans
l'algorithme.

Algorithme calculSommeN_premiers_Entiers
var n,S:entier
Début
Ecrire('Donner une valeur pour n ')
Lire(n)
S ← Somme(n)
Ecrire('la somme des ',n,' premiers entiers est: ',S)
Fin

4. Exercices d’application
4.1. Exercice 1

Ecrire une procédure qui affiche la table de multiplication d’un entier reçu en paramètre.
procédure tableMulti(n:entier)
var n,i,p : entier

Cours 7 : Les Procédures et les Fonctions Page 55

 ISET Zaghouan Cours Algorithmique 1

Début
pour i de 1 à n faire
p ← n*i
Ecrire(n,"*",i,"= ",p)
fin pour
fin

4.2. Exercice 2

Ecrire une fonction qui reçoit en paramètre deux entiers a et b et permettant de calculer ab.

fonction puissance(a:entier, b:entier) :entier

var p, i : entier
Début
p←1
Pour i de 1 à b faire
p←p*a
Fin pour
puissance ← p
Fin

4.3. Exercice 3

Ecrire une fonction qui calcule la surface d’un rectangle.

fonction surface(a:entier, b:entier) :entier
var s : entier
Début
s←a*b
surface ← s
Fin

4.4. Exercice 4

Ecrire une procédure qui calcule la surface d’un rectangle.

procédure surface(a:entier, b:entier,var s:entier)
var s : entier
Début
s←a*b
Fin

Cours 7 : Les Procédures et les Fonctions Page 56

 ISET Zaghouan Cours Algorithmique 1

Chapitre 8 : Les enregistrements

1. Introduction
Ce chapitre présente le type de données enregistrement qui est utilisé pour représenter, dans une même variable, un
nombre fini de données de types hétérogènes.

2. Définition
Un enregistrement est une structure de données qui sert à stocker, dans une même variable, un nombre fini
d'éléments de types hétérogènes. En mémoire, cette variable est associée à un espace mémoire dimensionné à un
nombre fini de cases de dimensions hétérogènes pouvant contenir ces éléments. Une variable de type enregistrement
est dite une variable composée.

3. Déclaration
Une variable de type enregistrement est déclarée ainsi :

Type nom_type = Enregistrement

Champ 1: TypeElm1
Champ 2: TypeElm2
……………………
Champ n: TypeElmn
Fin
var identificateur: nom_type

Exemple

Type personne = Enregistrement

nom: chaîne
prénom: Chaîne
cin : entier
age: entier
adresse: chaîne
Fin
var etudiant: personne
4. Accès à un champ d’un enregistrement
Les champs d'une variable de type enregistrement sont accessibles en utilisant l'identificateur de la variable et le nom
du champ.

Exemple

etudiant.nom
etudiant.adresse

Cours 9 : Les Enregistrements Page 57

 ISET Zaghouan Cours Algorithmique 1

Etant donné que les champs d'un enregistrement correspondent à un espace consécutif d'octets, ils jouent le rôle de
variables. On peut ainsi les utiliser dans des actions d'affectation, de lecture, d'écriture, … etc.

Exemple:

Etudiant.CIN ← 02895275
Lire (etudiant.nom)
Ecrire (etudiant.nom)

5. Exercices d’application

5.1. Exercice 1
On considère que la fiche d’un étudiant est définie par les informations suivantes: nom, prénom, age, cin, tel et
adresse.

Ecrire un algorithme permettant de remplir un tableau de N étudiants, de rechercher un étudiant de cin donnée et
afficher son nom, prénom et adresse.

Réponse

Algorithme ficheEtudiant
const N=10
Type personne = Enregistrement
nom: chaîne
prenom: Chaîne
age: entier
cin: entier
tel: chaine
adresse: chaîne
Fin
var E : tableau[1..N] de personne
i : entier
x : chaine
trouve : booléen
debut
pour i de 1 à N faire
ecrire("Donner le nom de l’étudiant n°",i,": ")
lire(E[i].nom)
ecrire("Donner le prénom de l’étudiant n°",i,": ")
lire(E[i].prenom)
ecrire("Donner le l’âge de l’étudiant n°",i,": ")
lire(E[i].age)
ecrire("Donner le cin de l’étudiant n°",i,": ")
lire(E[i].cin)
ecrire("Donner le tel de l’étudiant n°",i,": ")
lire(E[i].tel)
ecrire("Donner l’adresse de l’étudiant n°",i,": ")

Cours 9 : Les Enregistrements Page 58

 ISET Zaghouan Cours Algorithmique 1

lire(E[i].adresse)
fin pour
ecrire("Donner le cin de l’étudiant à rechercher: ")
lire(x)
trouve ← faux
i←1
répéter
si (x=E[i].cin) alors
ecrire("Etudiant trouvé)
ecrire("Nom : ",E[i].nom," prénom : ",E[i].prenom, "adresse : ",E[i].adresse)
trouve ← vrai
finsi
i←i+1
jusqu’à (i>N ou trouve=vrai)
si (trouve=faux) alors
ecrire("Etudiant non trouvable")
fin si
fin

5.2. Exercice 2
Sachant qu’un nombre complexe est défini par sa partie réelle et sa partie imaginaire.

Ecrire un algorithme permettant de remplir un tableau de nombre complexe, calculer leur somme et afficher le
résultat à l’écran.

Réponse

Algorithme sommeComplexe
const N=10
Type complexe = Enregistrement
re: réel
im: réel
Fin
var C : tableau[1..N] de complexe
z : complexe
debut
z.re ← 0
z.im ← 0
pour i de 1 à N faire
ecrire("Donner la partie réelle du complexe n°",i,": ")
lire(C[i].re)
ecrire("Donner la partie imaginaire du complexe n°",i,": ")
lire(C[i].im)
z.re ← z.re + C[i].re
z.im ← z.im + C[i].im
fin pour
ecrire("La somme vaut: ",z.re, "+ i",z.im)
fin

Cours 9 : Les Enregistrements Page 59

 ISET Zaghouan Cours Algorithmique 1

Chapitre 9 : Les algorithmes de tri

1. Introduction

On désigne par "tri" l'opération consistant à ordonner un ensemble d'éléments en fonction de clés
sur lesquelles est définie une relation d'ordre.

Les algorithmes de tri ont une grande importance pratique. Ils sont fondamentaux dans certains
domaines, comme l'informatique de gestion où l'on tri de manière quasi-systématique des données
avant de les utiliser.

2. Tri par sélection ordinaire

2.1 Principe

L’algorithme initialise un vecteur V formé de N entiers par les valeurs initiales du tableau à trier.
Et il utilise un autre vecteur VT (vecteur trié) formé aussi de N entiers, qui va servir pour le stockage
des valeurs du tableau V ordonnées dans l’ordre ascendant. Au départ le tableau VT n’est pas initialisé
ensuite, on remplit les N cases de la 1ère vers la dernière et dans chaque case on met la bonne valeur.
En appliquant les étapes suivantes :

 Initialisation : Chercher le plus grand élément dans le vecteur initial V, le stocker dans une
variable MAX.
 Itération : Pour i (l’indice de parcourt de VT) allant de 1 à N-1 faire les 3 étapes suivantes :
 Etape 1 : Chercher le plus petit élément dans le vecteur V.
 Etape 2 : Le mettre dans le vecteur VT dans la case d’indice i.
 Etape 3 : Le remplacer par le plus grand élément dans le vecteur V (pour qu'il ne sera plus le
minimum).
 Etape finale : mettre le MAX de V dans la Nième case de VT.

2.2 Algorithme de tri par sélection

Procedure lire_vecteur (var T : Tableau [1..N] de entier)
Var
Debut
Pour i de 1 a N faire
Lire (T[i])
FinPour
Fin

Evaluations Page 60
 ISET Zaghouan Cours Algorithmique 1

Fonction Max_vecteur (T : Tableau [1..N] de entier) : entier

Var max : entier
Debut
max  T[1]
Pour i de 2 à N FAIRE
Si max < T[i] Alors
max  T[i]
FinSi
FinPour
Retourner (max)
Fin

ALGORITHME TRI_SELECTION
CONST N = 100
VAR
V, VT : Tableau [1..N] de entier
i, j, i_min, MIN, MAX : entier
DEBUT
Lire_vecteur (V)
MAX  Max_vecteur (V)
POUR i de 1 à N-1 FAIRE
{Recherche du MIN de V}
MIN  V [1]
i_min  1
Pour j de 2 à N faire
Si MIN > V[j] ALORS
MIN  V[j]
i_min  j
FinSi
FinPour
{Mettre le MIN dans VT[i]}
VT[i]  MIN
V [i_min]  MAX
FinPour
{Remplir la case N de VT par MAX}
VT [N]  MAX
{Affichage du résultat}
Pour i de 1 a N Faire
Ecrire (VT[i])
FinPour
FIN

3. Tri par insertion séquentielle

3.1 Principe
L’algorithme lit une suite de N entier et les insère dans un tableau V formé de N entier de telle sorte
qu’après chaque insertion d’une valeur le tableau reste toujours trié. Cet algorithme utilise un seul
tableau et non pas 2 comme l’algorithme de tri par sélection.

Evaluations Page 61
 ISET Zaghouan Cours Algorithmique 1

Pour chaque valeur lue on l’insère dans le tableau en suivant les étapes suivantes :

 On cherche la position p d’insertion qui est la position du 1er élément > la valeur lu.
 On décale d’une case tous les éléments du tableau à partir de l’indice p.
 On met la valeur lue dans la case N° p.

3.2 Algorithme de tri par insertion séquentielle

ALGORITHME TRI_insertionS
CONST N = 100
VAR
V : Tableau [1..N] de entier
e, i, j, k, p : entier
trouve : booleen
DEBUT
Pour i de 1 à N Faire
Lire(e)
{chercher la position d'insertion p}
j 1
trouve  faux
pi
Tantque (j < i) et (trouve = faux) Faire
Si (V[j] > e) Alors
pj
trouve  vrai
FinSi
jj+1
FinTantque
{decaler les cases entre p et i}
Pour k de i a p+1 Pas (-1) Faire
V[k]  V[K-1]
FinPour
{mettre la valeur lu dans la case p}
V[p]  e
FinPour
{affichage du résultat}
Pour i de 1 a N Faire
Ecrire (V[i])
FinPour
FIN

3.3 Exemple
Les grandes étapes d’évolution du tableau au fil de l'algorithme. En bleu, le tableau trié, en rouge, la
valeur de la mémoire qui contient la valeur à insérer.

Evaluations Page 62
 ISET Zaghouan Cours Algorithmique 1

4. Tri par insertion dichotomique

4.1. Principe
L’algorithme lit une suite de N entier et les insère dans un tableau V formé de N entier de telle sorte
qu’après chaque insertion d’une valeur le tableau reste toujours trié.
Pour chaque valeur lue on l’insère dans le tableau en suivant les étapes suivantes :
 On fait une recherche dichotomique de la position p d’insertion qui est la position du 1 er élément >
la valeur lu.
 On décale d’une case tous les éléments du tableau à partir de l’indice p.
 On met la valeur lue dans la case N° p.

4.2. Algorithme de tri par insertion dichotomique

ALGORITHME TRI_InsertionD
CONST N = 100
VAR
V : Tableau [1..N] de entier
bi, bs, e, i, j, k, p : entier
trouve : booleen
DEBUT
Pour i de 1 à N Faire
Lire(e)
{chercher la position d'insertion p}
j 1
bs  i
bi  i DIV 2
trouve  faux
pi

Tantque (j < i) et (trouve = faux) Faire

Si( e <= V[j] ) Alors
pj
trouve  vrai
Sinon
Si (e > V[bi]) Alors
j  bi + 1
bi  (bi + bs) DIV 2
Evaluations Page 63
 ISET Zaghouan Cours Algorithmique 1

Sinon
jj+1
bs  bi
bi  bs DIV 2
FinSi
FinSi
FinTantque
{decaler les cases entre p et i}
Pour k de i a p+1 Pas (-1) Faire
V[k]  V[K-1]
FinPour
{mettre la valeur lu dans la case p}
V[p]  e
FinPour
{affichage du résultat}
Pour i de 1 a N Faire
Ecrire (V[i])
FinPour

FIN
5. Algorithme de tri rapide

5.1 Présentation

L'algorithme de tri rapide, "quick sort" en anglais, est un algorithme de type dichotomique. Son
principe consiste à séparer l'ensemble des éléments en deux parties. Pour effectuer la séparation,
une valeur pivot est choisie. Les valeurs sont réparties en deux ensembles suivant qu'elles sont
plus grandes ou plus petites que le pivot. Ensuite, les deux ensembles sont triés séparément,
suivant la même méthode. L'algorithme, est récursif, mais il n'est pas nécessaire de fusionner les
deux ensembles. Le résultat du tri est égal au tri de l'ensemble dont les valeurs sont inférieures au
pivot concaténé à l'ensemble des valeurs supérieures au pivot.

5.2 Choix du pivot

Le choix du pivot est le problème central de cet algorithme. En effet, l'idéal serait de pouvoir
répartir les deux ensembles en deux parties de taille à peu près égales. Cependant, la recherche du
pivot qui permettrait une partition parfaite de l'ensemble en deux parties égales aurait un coût trop
important. C'est pour cela que le pivot est choisi de façon aléatoire parmi les valeurs de
l'ensemble. Dans la pratique, le pivot est le premier ou le dernier élément de l'ensemble à
fractionner. En moyenne, les deux ensembles seront donc de taille sensiblement égale.

Evaluations Page 64
 ISET Zaghouan Cours Algorithmique 1

5.3 Exemple

Les grandes étapes de l'évolution du tableau au fil de l'algorithme : En bleu, les valeurs déja
positionnées, en rose, les valeurs qui servent de pivot pour passer à la ligne suivante.

5.4 Algorithme

Fonction Partition (var T : tableau [1..N] de entier, deb, fin : entier) : entier
Var
i, j, v, p: entier
Debut
i deb-1
j fin
p  T[fin]

Repeter
Repeter
i  i+1
Jusqu'à ( T[i] ≥ p )
Repeter
j  j-1
Jusqu'à ( T[j] ≤ p )
Si ( i< j) Alors
v  T[i]
T[i]  T[j]
T[j]  v
FinSi
Jusqu'à ( i ≥ j )
T[fin]  T[i]
T[i]  p
Retourner (i)
Fin

Evaluations Page 65
 ISET Zaghouan Cours Algorithmique 1

Procedure Tri_Rapide (var T : tableau[1..N] de entier, deb, fin :entier)

Var
Pos : entier
Debut
Si (deb < fin) Alors
Pos  Partition (T,deb,fin)
Tri_Rapide (T,deb,pos-1)
Tri_Rapide (T,pos+1,fin)
FinSi
Fin

6. Tri par tas

6.1 Définition
Un tas est un arbre binaire complet dans lequel il existe un ordre entre un nœud et ses
descendant.
Un arbre binaire complet est un arbre dont le ième niveau contient 2^i nœuds sauf éventuellement
le dernier niveau où les feuilles sont regroupés à gauche. Ainsi au niveau de la racine qui représente le
niveau 0 on a 2^0 c'est-à-dire 1 seul nœud, au niveau 1 on a 2^1 c'est-à-dire 2 nœuds, et ainsi de suite
jusqu’à l’avant dernier niveau, le seul niveau qui respecte pas cette règle et peut contenir moins de 2^i
éléments est le dernier niveau.
Un tas est un arbre binaire complet qui respecte la relation d’ordre suivante : pour chaque nœud
on a une valeur ≥ aux valeurs de chacun de ses fils.
Remarque :
Les éléments qui se trouvent au dernier niveau sont placés dans les feuilles les plus à gauches.

6.2 Exemple
10

8 7

2 3 6

6.3 Utilisation d’un tas pour le tri

L'idée de base consiste à insérer les éléments du tableau à trier dans un tas. Il reste alors à ressortir
les éléments du plus grand au plus petit en vidant le tas progressivement et on obtient ainsi un tableau
trié.

Evaluations Page 66
 ISET Zaghouan Cours Algorithmique 1

Les 2 opérations de base qu’on va faire sur un tas sont l’ajout d’un élément et la suppression du
nœud ayant la valeur maximale dans le tas.

Pour l’ajout dans un tas, on ajoute l'élément sur la première feuille libre de manière à ce que l'arbre
binaire reste toujours complet. Et on rétablit la propriété d’ordre en échangeant l'élément avec son père
si la valeur de ce dernier est inférieure, et en propageant ce type d'échange aussi loin qu'il le faut
jusqu’à ce qu’on atteint la racine.

Pour la suppression du maximum, on remplace l'élément racine qui contient le maximum par le
dernier élément (dernière feuille) de manière à ce que l'arbre binaire reste toujours complet. Et on
rétablit la propriété d’ordre en effectuant si nécessaire des échanges des pères avec le plus grand de
leurs fils, en partant de la racine de l'arbre vers les feuilles.

Ainsi l’algorithme de tri par tas est basé sur l’utilisation d’une procédure appelée Insert qui fait les
insertions successives dans le tas et d’une fonction appelé SuppMax qui fait les suppressions
successives des éléments des plus grands vers les plus petits.

Remarque :
On peut représenter un tas par un tableau T à une dimension à condition que les propriétés suivantes
restent vérifiées sur le tableau :
T [1] désigne la racine du tas.
T [i div 2] désigne le père de T[i].
T [2i] et T [2i + 1] sont les fils de T[i].
Si le tas a N nœuds avec N = 2i, alors T[i] n'a qu'un seul fils qui est T[p].
Si i > N div 2, alors T[i] est une feuille.

6.4 Algorithme de tri par tas

Procedure Insert (k : entier)
Var

Evaluations Page 67
 ISET Zaghouan Cours Algorithmique 1

V, j : entier
Debut

V  T [k]
j  k DIV 2
Tantque ( j > 0 et T [j] <= V) Faire
T [k]  T [j]
k  k DIV 2
j  k DIV 2
FinTantque
T [k]  V
Fin

Fonction SuppMax (M : entier) : entier

Var
j, max, v : entier
Debut
max  1
Pour j de 1 à M Faire
Si (T[j] > T[max]) Alors
max  j
FinSi
FinPour
v  T[max]
T[max]  T [M]
Retourner (v)
Fin

------------------------------------****************************-----------------------------------

ALGORITHME TRI_TAS
CONST N = 100
VAR
S, T : tableau [1..N] de entier
N, i : entier
DEBUT
Lire_vecteur (S)
Pour i de 1 a N Faire
T[i]  S[i]
Insert (i)
FinPour
Pour i de N a 1 PAS (-1) Faire
T[i]  SuppMax (i)
FinPour
Affiche_vecteur(T)
FIN

Evaluations Page 68