Eni Algorithmique Technique de Programmation en Python 2ed... Wawacity - Tokyo
Eni Algorithmique Technique de Programmation en Python 2ed... Wawacity - Tokyo
Eni Algorithmique Technique de Programmation en Python 2ed... Wawacity - Tokyo
Algorithmique
Techniques fondamentales
de programmation
Exemples en Python
{nombreux exercices corrigés)
Nouvelle édition
En téléchargement
DUT Informatique
Ludivine CREPIN
Ressou rces informatiq ues
Algorithmique
Techniques fondamentales
de programmation
Exemples en Python
(nombreux exercices corrigés)
Nouvelle édition
Avant-propos
Pour chaque chapitre, vous pouvez tester vos connaissances avec un quiz
corrigé et vous pouvez mettre en pratique avec de nombreux exercices corri-
gés.
Ce livre est principalement dédié aux lycéens qui suivent l'option de spéciali té
numérique et sciences informatiques et aux étudiants qui commencent leur
formation en informatique, entrant donc en première an née de Licence, DUT
ou BTS informatique. Cependant, il n'est pas nécessaire d'étudier l'in forma-
tique pour apprendre le développement. Ce livre est donc ouvert à tout e
personne étant à l'aise avec l'utilisation d'un ordinateur.
Table des matières --------1
Avant-propos
Chapitre 1
Introduction à l'àlgorithmique
1. Les fondements de l'informatique .... . .......... . .. .... .. . . .. 15
1.1 Architecture de l'ordinateur . .... ... ...... ... ..... ...... . 15
1.2 Implémentation de la mémoire .... . . .... ... . . .. . ... . .... 17
1.2.1 Différentes mémoires ............ . ........... ... . 18
1.2.2 Programme et mémoire ........ . . ........ .. ....... 18
2. L'algorithmique, l'art de programmer ....... . . . ..... .. ....... . 19
2.1 L'algorithmie, commente! pourquoi? .... . .... .. ......... 19
2.1.1 Exemples de la vie courante ... . ... ... . .. ..... ..... 19
2.1.2 Algorithmes .... . .. . ............ ... . .. .... ...... 20
3. Les langages, la mise en œuvre .... . .......................... 21
3.1 La programmation ........... .... . ... ..... .... ... .. ... 21
3 .2 Les différents types de langages ........... ..... ... .... ... 22
3.2.1 Programmation procédurale ........ . . . .... ...... . . 22
3.2.2 Programmation orientée objet ... . ..... ..... .. . . .. . 22
3.2.3 Programmation fonctionnelle ..... .. .. .. . . . .. . .. .. . 23
3.3 Python ....... .... ...... . .. .... ................... ... 23
2---------Algorithmique
Techniques fondamentales de programmation
Chapitre 2
Les variables et opérateurs
1. Les variables simples ... . ..... . ..... .. .. . .. .. . .. .. .. . . .. . ... 25
1.1 Types, déclaration et affectation . . ........ . . .. . . .. . . . .... 26
1.1.1 Les nombres ou numériques . . . .... . .. . ... . . .. ... . . 27
1.1.2 Les caractères . .. . . . .... .... . .. ... ... .... .... ... . 28
1.1.3 Les booléens .... ... ..... . ..... . .. . .... . ......... 30
1.1.4 Les ch aînes de caractères .... . ...... . ... . . . .... . ... 30
1.2 Saisie et affichage . . .... . . .. ... ... .... .. . . . . . . . ... .. . . . 31
1.3 Les constan tes . . . .. . . . . .. . .. . .. ... . .... . ......... . . . . . 33
2. Utiliser les variables .. . ... . . ...... ..... .. ... . ... . .. . . .. .. .. 34
2.1 Opérateurs mathématiques communs ..... . ... ... .. ... ... 34
2.2 Opérateurs spécifiques aux entiers .. .. . .... . . . . . . . .... .. . 35
2.3 Opérateur spécifi que aux réels . .... ... .. .. .... . . . .... . ... 36
2.4 Opérateurs de comparaison . .. ......... . .. . ...... ... .... 36
2.5 Opérateurs logiques pour les booléens . .. .. . . ...... . . .. ... 37
2.6 Opérateurs sur les caractères ............ .. .. . ... . .. .. . . . 38
3. Les opérations sur les chaînes . . .... . . .. .. . . . . . .. . .... ..... .. 39
3.1 Concaténation . . . . . .. .. .. '. .. . . . . . . .... . .. ... . .. . . ... . 39
3. 2 Extraction . .. ................ ...... . . . .. .. . . . .... ... . 40
3.3 Longueur .. . . .. .. .. .. .. .. . .. ... . ... . .. . .. . .. .. ... .... 40
4. Et avec les langages ? ...... . .. . . .. . . ... . . ... .. .. ..... . . .. . . 41
4.1 T y page ... . .. . .. . .. . ... . .. . ........... . ... . . .. ..... . . 41
4.1.1 Les langages à typage statique . .... . . . .... . . . ...... 42
4.1.2 Les langages à ty page dynamique ... . ........... .. .. 42
4.1.3 Langages fortement ty pés .. ... . ... . ... . .......... . 42
4.1.4 Langages fa iblement ty pés .. .. . . ... .. . . .. .. . .... .. 43
4.2 Opérateurs . ..... ....... .. .. ... . .. .. . . . . . .. . . .. .. .. .. 43
4.3 Gestion de la mémoire . ... . . ........ .. . . .... .. . ... .. . .. 44
4.4 La gestion des réels .. . ... .. . ... . .. ... .. .. ... .. . . ... .... 45
Table des matières _______3
Chapitre 3
Conditions, tests et booléens
1. Les tests et conditions ........ ... . ........ · .. .. . ...... . ..... 57
1.1 Les conditions sont primordiales ........ .. . .. ..... . ...... 57
1.2 Structures conditionnelles .... . . . .. . . .. ...... ... .' .. . . ... 58
1.2.1 SI ALORS SINON .... . ...... .. .. ...... . ....... .. 59
1.2.2 CAS PARMI . ........ . ...... . .. . ............. . .. 61
2. La logique booléenne . . ......... . .... . ...... ... .. . . ..... . .. 64
2.1 Conditions multiples .......... ...... . . . . . .... . . .. .. ... 64
2.2 Algèbre ou logique de Boole . . .. . ... .. . ..... . ........... . 65
2.2.1 ET logique .......... . .. . . .. . ... . .... . . ......... 65
2.2 .2 OU logique . .. .......... . ... . ................... 66
2.2.3 NON logique ....... .. ...... . ..... . ..... .. ... . .. 67
2.2.4 Règles de priorités .... . ... . ... . ........ . ..... .. .. 68
2.2.5 Un exemple concret ... ... .... . .... . .... .. . . ..... . 69
3. Les blocs en python . .. ..... . .. . . .... ..... . .... ... .. .. . . . . . 71
3.1 L'importance de l'indentation . .. ..... .. . .. . .. . . . . . .. . ... 71
3.2 Visibilité des variables .. . .. . ... . ........... . ........... 72
3.3 Conditions en Python .. . . . .' ........ ......... . ...... . .. 74
3.4 Instructions conditionnelles ........ . ... ... ... . ... ... . .. 74
3.4.1 SI ALORS SINON . .. ... ... ... .. .. ... . .. . . .... . .. 74
3.4.2 Opérateur ternaire ..... ... .... . .. .............. . . 76
3.4.3 CAS PARMI. .. . .... ......... . . . ... ...... . ... ... 77
4. Exercices ...... ..... . ....... . . ... .. . .... . .. .. . .. ...... . . . 77
4 .1 Exercice 1........ .. ....... ... . ... ... . ............. . . . 77
4.2 Exercice 2 ... .... ... .. .. .. .... .. .. . ..... . ............. 78
4.3 Exercice 3 .. ........ . ..... . ........... ... ... . ... ... . .. 78
4 .4 Exercice 4 ....... . ...... . . . . ... . ......... .. . .. ....... . 78
Table des matières ________5
Chapitre 4
Les boucles
1. Les structures itératives ... ....... ... . ...... ..... ... .... .... 79
1.1 Itérer pour mieux programmer ............. . .. . .... . . .. . 79
1.2 Comment itérer proprement? ............ . ... : .. ........ 81
2. Tant Oue .... .. ...... ... ................. . ............... 81
2.1 Principe et syntaxe . . .. .. . . ... . ...... ... .. . .... . .. . . . .. 81
2.2 Exemples ......... .... ... . ....... .. . ...... .. .. .. .. .. . 82
3. Répéter ... Jusqu'à .... . ....... ... ........ . ...... .... ... . ... 84
3.1 Principe et syntaxe ........ ....... . .. . ..... . .. .. . .. .... 84
3.2 Exemple .. ......... ... ... .. .... . . .. .... ............. . 85
4. Pour .................. .. ....... .. . . . .... .. ..... .. . .. .... 85
4.1 Principe et syntaxe . .... ...... .... . .................... 85
4.2 Exemples ......... ... .............. . ...... ......... .. 86
5. Structures itératives imbriquées . . ..... . .... ... ....... ...... . 87
6. Attention danger .... .... . . ............ . .... . . .. ... ..... . . 89
7. Itérons en python ...... . ......... . . . ....... . ...... .. . . .... 91
7.1 Pour ... ..... .... .... . : . .... .... . .. . . . .......... . .. .. 91
7.2 Tant que .... . ....... .. ..... . .. . .... . ..... ........ . .. 92
7.3 Répéter jusqu'à .... ... ........... . . ..... . . ............ 93
7.4 Boucles imbriquées .... .... ... . ................ . .. . .... 93
7.5 Pour aller plus loin ... . . .... . .. ..... . .. .. ..... .. . . ..... 94
7.5.1 Break ........... . .. ... .... ...... . .... .. . . ... . .. 94
7.5 .2 Continue . ..... .... . .... .... . ... .. . . ...... . .... 94
7.5.3 Boucle-else ...... . .. ... .. ...... . .... . . . ... ... ... 95
8. Exercices ... ..... . . . . .... .. . ..... ... . . .. ..... . . .......... 96
8.1 Exercice 1 . ....... . ................... .... .... . . .. . ... 96
8.2 Exercice 2 . . .... ... ... ... . .. .. .... .... .. .............. 96
8.3 Exercice 3 . ..... . . . .... .. . . . . ................ . ........ 96
8.4 Exercice 4 ......... . ....... . ...... . . . . .. . ... .... .... . . 96
8 .5 Exercice 5 ....... .. .. . .. . .... . . . ............. . ........ 96
6---------Algorithmique
Techniques fondamentales de programmation
Chapitre 5
Les tableaux et structures
1. Introduction ... . ........ . ....... ... . .......... . . .. . ... . .. 99
2. Les tableaux . ...... ....... . .... . . . . .. . . .. . . . . . ...... ...... 99
2.1 Tableaux à une dimension ........ .. . . .. . ..... . ...... .. 100
2.2 Tableaux à deux dimensions .. .. ... . ........ . .. .. .... .. 102
2.3 Tableaux à n dimensions ......... . . .. .. .. .... . ... . .... 104
3. Manipulations simples des tableaux ....... . .. ........... .... 105
3.1 Tableaux à une dimension .. . . ..... ... .. ... . . . . .. . . .. .. 105
3.1.1 Parcours . .. . ... . . .... . ... .. ...... . . . . . ........ 105
3.1 .2 Recherche . . . .. . .. ...... .. . .. . ... . . .. .... .. . ... 105
3.1 .3 Réduction . .. ......... . .... .... . .. ....... .... .. 107
3.2 Tableaux à n dimensions . .. . ........ ... .. . . .. . ....... . 108
3 .2 .1 Parcours ..... . ... .. , .......... .. . .. . ...... . . . . 108
3.2.2 Recherche . . .............. .. ..... . ..... .... .... 108
4. Structures et enregistrements ...... ... .. ... . ... . . ........ .. 110
4.1 Structures ... . ..... .. ....... ... ..................... 110
4.2 Structures imbriquées ... . .. . ... . ....... . .. . .......... 112
4.3 Structures et tableaux .................... . ... . . . . ... . 11 3
4.3. 1 Structure contenant un tableau .......... .... ..... 11 3
4. 3.2 Tableau de structures ............ . .. . ........... 114
5. Mettons en pratique avec Python .. ... .. . ..... . ....... . . . ... 114
5.1 Tableau =liste .... ......... . .... ..... . . .. .... . . . ... . 114
5.1.1 Parcours ....... .... ...... .. . . ................. 116
5.1.2 Opérations sur les listes .... . . . ... .. .. ... .. ... ... 117
5 .1.3 Copie ...................................... . . 118
5.1.4 Pour aller plus loin : l'intention ...... . . ...... ... . . 119
Table des matières _______7
5.2 Tuple ................. . ... ... ........ ... ... .... .... 120
5.3 Slicing ................. ... . . . .... . ........ . ........ 121
5.3.1 Listes et tuples .... . .. . .. ........ . . . . .. .. . .. .... 121
5.3. 2 Retour sur les chaînes .. . ................ . . .... .. 122
5.4 Dictionnaire .............. ...... ...... . .... . . ..... .. 122
5.4.1 Déclaration et accès ............................. 123
5.4.2 Opérations ............ .. . ............ . ........ 123
5.4.3 Parcours . . ..... .. ..................... . ....... 124
5.4.4 Pour aller plus loin : l'intention .............. . .... 125
6. Exercices .... . ........... ....................... .. . . .... 125
6.1 Exercice 1 ............ . . .. .. . ...... . ........... .... .. 125
6.2 Exercice 2 . .... . ........ .. .. . ... . .................... 125
6.3 Exercice 3 ....... ....... . ...... ... .. . ......... ....... 125
6.4 Exercice 4 .... . ...... . .. ....... ...... ......... ... .... 126
6.5 Exercice 5 ........... ...... ...... . . .. .. . . .. ........ .. 126
6.6 Exercice 6 .... ..... .. ... . .. .. .. . ... . . ......... .... ... 126
6.7 Exercice 7 .................. . ........................ 126
6.8 Exercice 8 ... ..... ... ....... ... ............ . ... . . .... 126
6.9 Exercice 9 . . . .. .. ... ... , .... .. .... . ...... . ........... 127
6.10 Exercice 10 ...... . .............. .. . . .. . .... .......... 127
Chapitre 6
Les sous-programmes
1. Procédures et fonctions .. . .......... ....... . ........ . . .. .. 129
1.1 Les procédures ......... . ... . . .. .. ........ . .. . ........ 132
1.1.1 Paramètres ................ .. .. .... .. . ......... 132
1.1.2 Déclaration .. .... ... .. ...... .. . ...... . ......... 133
1.1.3 Appel . .. .. . .. .... .... .......... . ............. 135
1.1.4 Les tableaux en paramètres .. ........ . . .. ......... 138
1.2 Les fonctions .......... .. ....... . ...... .......... . ... 138
1.2.1 Déclaration .................................... 138
1.2.2 Appel ...... .... . .. . . .... . .... .... ...... . ..... 141
8---------Algorithmique
Techniques fondamentales de programmation
Chapitre 7
Passons en mode confirmé
1. Les pointeurs et références ......... ... .. ·. .... . ............ . 171
1.1 Implémentation de la mémoire .. .. . .... . ........ . ...... 171
1.2 Gestion des pointeurs ......... . ... . .... .. ... ." ......... 172
2. Les listes chaînées ... .. ..... . . .. . . .. ..... ................. 175
2.1 Listes simplement chaînées .. .. .. .. . ......... ... ... .... 175
2.1.1 Création .. .. . .. ... ........... . ..... . . .. .. . .. .. 176
2.1.2 Parcours . . ....... . .. . ... . . . . . . . . .. . .... ... ... . 177
2.1.3 Ajout d'un élément ....... .. ............. ... .... 178
2.1.4 Suppression d'un élément .. ... ......... ...... .. . . 181
2.1.5 Insertion d'un élément ....... ..... .............. 187
2.2 Listes chaînées circulaires ........ ........ .............. 190
2.2.1 Création et parcours . ... .......... . .... .. ... .. .. 190
2.2.2 Ajout d'un élément ......... . .. .. . . . .. ... .... . .. 192
2.2 .3 Suppression d'un élément ............. . . ..... . ... 195
2.2.4 Insérer un élément ........... ..... ............. . 198
2.3 Listes doublement chaînées ....... . .. ... .... . . ... . ..... 198
2.3.1 Création et parcours ...... . ... ... . .. .... . ....... 199
2.3.2 Ajout et insertion d'un élément . ... . .............. 200
2.3.3 Suppression d'un élément . ......... . ..... . . . ..... 202
2.4 Piles et Files ............ . ..... . . ...... ...... .... ... .. 205
2.4.1 Piles ou LIFO .. . .......... ..................... 205
2.4.2 Files ou FIFO .... .. ....... .. . ... . ............. . 207
3. Les arbres ........ . ... ........ ..... . .. . .... .. ... . ........ 210
3.1 Principe . ..... .. . .. ...... ... . . . ... ................. . 210
3.2 Création ............. ......... . . . .. . . ............... 211
3.3 Parcours en largeur ..... .... . ....... ...... . .......... . 212
3.4 Parcours en profondeur ........ . ...... . . .. .. . ... ..... . 212
3.5 Parcours en infixe ... . .. . ..... . .. .. ... . ....... . . . ... .. 213
3.6 Parcours en postfixe .... . ......... . ... . . . ... .......... 213
3.7 Insertion d'une feuille ..... . ............. .... ......... 213
10---------Algorithmique
Techniques fondamentales de programmation
Chapitre 8
Les fichiers
1. Le système de fichiers . ... . .. . . .. . ........... . ...... . ..... . 227
1.1 Préambule ... . .... ..... . .. . .. . . ....... .. .. .......... 227
1.2 Répertoire et fichier ........ . ..... .. ......... ... .. . .. . 227
1.3 Arborescence de fichiers ...... .......... . . . ............ 229
1.4 Chemin absolu ou relatif ........ . . .. .. .. . .. .. . ..... .. . 230
2. Les différents types de fichiers .... . .. . .. .... . .. . ........ . ... 231
2.1 Texte non formaté ..... .. .... . . . ... .. .. .. . .... .. .. ... 232
2.2 Texte formaté ... . ............ . .. . ....... .... . . . . .. . . 232
2.2.1 csv ..... ........ ... .. ..... ...... .... ........ 233
2.2 .2 XML ... .. ..... . .. ... .. ..... . . ... .. .. . .. . ... . . 234
Table des matières --------11
2.2.3 JSON ......... . . .. . . . . .. .. . . .. ... . ..... . .. ... . 235
3. Manipulation de fichiers ...... ..... . . : .. ..... .. . ..... . . .. . 236
3.1 Ouvrir et fermer un fichier. ... ...... . . ... .. . .... .... . . . 236
3.2 Lire un fichier .......... . ...... . . ... ... .. . . ...... ... . 238
3.3 Écrire dans un fichier .. ... ...... .. .. . ... ... . ... ... . . . . 239
3.4 Pour aller plus loin .. . ........... . . .. .... .. . .. ........ 240
4. Accédons à des fichiers avec Python .... .. . . .. ... .. . ..... . . .. 241
4 .1 Ouvrir et fermer un fichier. . ......... . ... .. . . . .. . .... .. 241
4.2 Lire un fichier ........... ... ........... .. .... . ... . .. . 242
4.2.1 read () ................... . .. . ...... . .... .... . . 242
4.2.2 readline() . . . .. . .... ..... .... . . .. ........ . ..... 243
4.2 .3 readlines() ............ .. ....... . . .. . . .. . ....... 243
4.2.4 for in . .. .. . .......... . ......... . ..... .... . .... 244
4.3 Écrire dans un fichier ................................. 246
4.3.1 write(chaîne) .... .. .. . .. ........ . ... . .. ... .. ... 246
4.3.2 print () .............. . .................. . ...... 246
4.4 Parcourir l'arborescence . .. .. . . .. ... . . ......... . . ...... 247
4.4.1 Module .. . ..... ... .. . ... .. . . . ... . ... ..... ..... 247
4.4.2 Utilisation de walk- ....... ... .. . ........... .. ... 248
5. Exercices ... . ... .... . . . . .. ................... . .......... 249
5.1 Exercice 1 ... . . .... . ....... ..... .. ................... 249
5.2 Exercice 2 ........................... . . .... ... .... .. . 249
5.3 Exercice 3 . ...... .. ....... .. ........................ . 249
5.4 Exercice 4 . . . .. . . .. .. .. ........ .. . ... .. . . . ....... .. .. 249
5.5 Exercice 5 .. ...... . .. ... ... ... . ... .. . .. . .. . .......... 249
5.6 Exercice 6 . ......... . .... .. . ....... . . ... . .. . .. . ...... 250
5.7 Pour aller plus loin . . . . .. . . . . ... ... .. . ... . .. .. ........ 250
5.7.1 Exercice 7 ............. . . . ..... ... ... ........ .. 250
5.7.2 Exercice 8 . ... ......... . . ....... . .. ... .... ..... 250
12---------Algorithmique
Techniques fondamentales de programmation
Chapitre 9
Commencer avec l'objet
1. Préambule ........ .. .... .. . . .. . ... . ....... . . . . .. ..... . .. 251
2. le naturel de l'objet . ............ . ... ..... .... ... . . ....... 252
2.1 Introduction ... .. ...... . . .. . ........... . . ... .... .... 252
2.2 l'objet et la classe ... .... . .. . ... . ....... .. ... .... ... . . 253
2.3 Méthodes ....... .. .... .. . .. .. . .. .... .. ...... . .... .. 254
2.4 Visibilité des attributs et méthodes ... .. ..... . .. .. ....... 255
2.5 Un aperçu de l'UMl ......... ........ . .... . . . .. .. . .. .. 256
3. Travailler avec les.objets .... ... . . .. .. . ...... . ... . . . . . . .... 258
3.1 Introduction .. ..... .... . .. .. . . ......... . . . ....... ... 258
3.2 Instanciation et allocation mémoire . .. . ......... . ....... 258
3.2.1 Constructeur .. . .......... ... . . . ..... .. ...... . . 259
3.2.2 Destructeur .. . . ... . .. ...... . .. . . .. .. .. .. ... . . . 260
3.3 Appeler les méthodes ........ .. .. . .. . .... .. .. .. . . . .... 262
3.3.1 listes et composition/ agrégation . . ... . .. . . ...... .. 263
3.3.2 Arbres binaires en orienté objet ....... .. ... .... ... 268
3.4 Héritage simple ..... .. . ................ ...... ...... . . 271
.
4. Pour aller plus loin . .. .. ......... . ... . .. . .. . ...... . .. . .... 275
4.1 Polymorphisme ... . ...... . .. . .............. . . .. ... . .. 275
4.1.1 Objet ..... . ...... . .. . . . .. . . ... . .. ... . . . ...... 275
4.1.2 Surcharge de méthodes ... . ...... ... ...... .... . . . 276
4.1.3 Réécriture de méthodes ... . ..... . . . ....... .. .. . .. 278
4.2 Héritage multiple ...... . ...... . .... .. .......... . . .. .. 281
5. l 'objet en Python . . ...... .. .. ... ... ......... ....... .... .. 283
5.1 Objet et classe en Python . . .. .......................... 283
5.2 Utilisation de self pour les méthodes ... .. ............ ... 284
5.3 Agrégation et composition . ............. ... ... .. .. .. .. . 286
5.4 Héritage simple et polymorphisme . . . ...... .. ... . . .. . . . . 287
Table des matières --------13
5.5 Pour aller plus loin .. .. ......... ..... ....... .......... 289
5.5.1 Visibilité privée ..... ..... ...... ... ... .... .. ... . 289
5.5.2 Héritage multiple ..... . ........... .. .. . .... ..... 290
5.5 .3 Surcharge des opérateurs .......... . ..... .. ....... 291
6. Exercices .. .. .. ..... .. . . ...... . . ... . . .. .. . .. ... . . . .... .. 293
6.1 Exercice 1 .... . ... . ........ . . . .... . .. . .. .. ....... .... 293
6.2 Exercice 2 .... ... . ........ .. ......... ... ... . . .... . ... 293
6.3 Exercice 3 . . ....... ..... .... ... . .. ..... . .... . .... . ... 294
6.4 Exercice 4 . ... . ... ... ..... .... ..... .. . .... ....... ... . 295
Chapitre 1
Introduction à l'algorithmique
Unité
Unité de
arithmétique - contrôle
et logique
Entrée
Sortie
Nous utilisons tous les jours des algorithmes sans même savoir que ce sont des
algorithmes. les premiers algorithmes formalisés remontent à l'Antiquité
pour la gestion de l'eau dans les fontaines et depuis nous n'arrêtons pas d'en
créer et de les appliquer.
2.1.2 Algorithmes
Par définition, un algorithme est une suite finie d'instructions appliquan t
des opérations non ambiguës sur un ensemble de variables . Cont raire-
ment à la notice de mont age et à la recette de cuisine, l'ordinateur comprend
parfaitement un algorithme du premier coup et l'exécute sans jamais se trom-
per.
D 'un point de vue plus général, un algorithme propose une solution compré-
hensible et applicable pour résoudre un problème, comme pour le passage
piéton.
Voyez l'algorithmie comme le langage universel de tous les programmes et
langages de programmat ion. T out algorithme peut être traduit dans un
programme et vice-versa .
Avec l'apprentissage de l'algorithmie, vous apprenez également comment
communiquer avec l'ordinateur: ce qu'il peut comprendre, comment lui
donner les informations, comment le guider dans l'exécution du programme.
Tout comme vous apprenez à un enfant à traverser une route, vous allez indi-
quer dans un algorithme ce que l'ordinateur peut faire ou ne pas faire, les
conditions à tester, les comportements à répét er et dans quels cas les répéter,
etc.
Introd uction à l'algorithmique _ _ _ __ _ _ __ 21
Chapitre 1
3.1 La programmation
■ R emarque
Le premier programme a été inventé avant même que l'ordinateur soit créé .
Ada Lovelace, comtesse anglaise née en 1815, développa le premier
programme sur un ancêtre de /'ordinateur, la machine analytique de Charles
Babbage. Il s'agit des premières instructions qu 'un être humain ait données à
une machine. Pour lui rendre hommage, le langage de programmation Ada
porte son nom.
3.3 Python
Nous avons fait le choix de mettre en pratique nos algorithmes avec le langage
Python dans sa version 3. Ce choix a été guidé par les raisons suivantes :
- Il est gratuit.
- Sa sy ntaxe est simple.
- Il est multiplateforme : il peut s'exécuter sur les sy stèmes DOS (Windows)
et Unix (Linux et macOS).
- Il est indépendant du sy stème d'exploitation grâce à son interpréteur.
- Il évolue sans cesse grâce à une importante communauté très active.
- Il permet de programmer en procédù rale et en orienté objet .
Nous n 'en dirons pas plus sur ce langage dans cette introduction pour laisser
le lecteur le découvrir au fur et à mesure des chapitres de cet ouvrage .
- - - - - - -- ----25
Chapitre 2
Les variable s et opérateurs
Nous utilisons l'opérateur <- pour affecter une valeur à une variable : les
pommes sont au nombre de six (pommes <- 6). Au fur et à mesure que nous
allons intégrer les pommes à la tarte, le nombre de pommes restantes va dimi-
nuer. Une variable, comme son nom l'indique, a une valeur qui peut changer
dans le temps et sert à mémoriser cette valeur avec un label donné .
■ Remarque
Par convention en algorithmie, les caractères accentués ne sont pas autorisés
et le caractère "_" permet de séparer deux mots dans un nom de variable ou
de programme pour qu'il soit plus lisible.
Parmi ces surcouches, il existe les types de données pour indiquer ce que la
variable représente comme type d'information :
- les nombres ou numériques
- les caractères
- les booléens (le type le plus simple)
- les chaînes de caractères
En algorithmie, une variable a toujours le même type du début à la fin de
l'algorithme. Le typage est dit fort de ce fait.
Explorons maintenant ces différents types de variables.
Les entiers sont des numériques sans chiffre après la virgule, ce que nous
appelons communément les chiffres et nombres ronds . Un entier se déclare
par son identifiant suivi du type ENTIE R:
1 mon_ en t ier : ENTI ER
■ Remarque
Un caractère est forcément représenté par un nombre binaire. Pour ce fa ire,
une convention existe : la table ASCII pour les caractères anglophones et la
table ASCII étendue qui lui ajoute les caractères accentués et les caractères
spéciaux à une langue. Ces deux tables indiqu ent quelle est la valeur b inaire
pour chaque caractère utilisable en informatique comme le montre la figure
ci-après.
Les variables et opérateurs _ _ _ _ _ _ _ _ _ __ 29
Chapitre 2
ASCII TABLE Oe<::i™ l HcMd"eci_..,al Si na r Oc tal Char ~ ci Nl HeM deci>Ml 8111,tr Oc t al Char
0- 0 ◊ 48 3:0 .uoooo 60 0 96 60 llOMOO l',O
l 1 l 49 Jl 110001 61 1 97 61 11.0QJOl l.-!.l a
2 lO 2 so 32 1:0010 62 '2 98 62 l 100010 li-2 b
3 n 3 51 3::! 1';.0011 63 ~ 99 !:d llOOOl.l 143
4 JOO .; 52 34 !10.WO 64 100 64 ll.00100 144
S 101 S ':d 3.5 11Cl01 65 101 f;5 11001m 1-'-S
6 HO é- 54 36 l'WlW 66 102 66 11(;0HO 1.4-6
7 111 7 55 37 1101'.i.l 67 10, 67 11Mll1 l.t7
e 1wo 10 56 38 111000 70 10 4 68 lHHôûO 130
9
10 A
lWl
lOHl
1l
12
57
58
.39
3A
l.11001 71
UlOHl 72
105
10<
••
6A
l1Cl001
l !01010
151
15]
i
J
11 :S HIH 13 59 3B lllOl l 73 107 68 ll0Wll l.S3 k
12 C 1 100 14 60 JC 111100 '4 10 8 6C 1101100 154 1
13 0 1 10 1 15 61 3D 111101 75 109 60 1101101 1.55
14
15
Hi
E
F
lO
ll l O
11!1
10000
15
ll
~O
62
63
&l
3E
:JF
40
llUl◊
lillll
!000000100
76
77 l
@
l!O
111
11.2
.,
6(
70
llOlHO 156
1101111 l.57
1110000 :.60
17 11 10..rOl :ll 65 41 100000l 101 A m 11 .UHWOl 161
66 ~2 1000010 102 8 w 1110010 162 r
,,""
IR l'i: 1001.0 22
19 13 lC--011 23 67 ~) 1000(H1103 C m tnoon 163
20 14 10100 2-1 6$ 44 1000100 10,\ Cl l l6 lllOlOO lM
21 l5 lOlGl 25 69 45 lOOOlOl 105 f 11 7 75 1110101165
n .H> lOHO 26 10 .;6 100\i.: 10 106 f 11 8 76 111('1110 Hi6
23 17 Hilll 11 11 47 1000111 '107 G 119 n 1110111 167 w
24
25
18
19
11000 30
HOOl 31
n
73
tS
t9
1001000
1001001
110
11:;
H
~
120
121 ,.
76 1111000 170
lllHIOl lH
X
Les manipulations possibles sur ce type seront vues dans une section dédiée de
ce chapitre un peu plus tard. Pour le moment, nous allons utiliser les chaînes
de caractères uniquement comme des indications pour l'utilisateur.
Nous sommes maintenant prêts pour écrire notre premier algorithme !
Les variables et opérateurs _ _ _ _ _ __ _ _ _ 31
Chapitre 2
Pour pouvoir interagir avec un utilisateur 1 nous - devons lui demander les
valeurs sur lesquelles notre algorithme doit travailler et lui indiquer les chan-
gements de valeurs afin de lui transmettre les informations qu'il demande . La
saisie sert à récupérer les valeurs grâce à une entrée clavier (l'utilisateur rentre
sur le clavier la valeur demandée) et l'affichage envoie sur une sortie 1 l'écran1
une valeur sous forme de texte pour l'utilisateur.
Avant de communiquer avec l'utilisateur 1 il nous faut voir comment définir
un algorithme. La machine est stupide 1 elle ne fait que ce que nous lui disons !
De ce fait 1 nous devons lui indiquer quand commence l'algorithme (D EBUT ) et
quand il finit (FIN) .
Tout comme les variables 1 chaque algorithme doit avoir un identifiant unique
pour que l'ordinateur sache le trouver pour le faire tourner et il doit être de
type PROGRAMME.
Nous devons également lui définir clairement où sont les variables : les
variables sont toujours déclarées en début d'algorithme dans la section VAR.
En informatique 1 ce type de section est appelé bloc . Vous ne pouvez pas uti-
liser une variable sans la déclarer dans ce bloc.
Voici notre premier algorithme qui déclare une variable x et lui affecte la
valeur 3,67 :
PROGRAMME Ex emple
VAR
x : REEL
DE BUT
X < - 3 , 67
FIN
■ Remarq ue
Les variables doivent être déclarées obligatoirement dans le bloc VAR mais
leur affectation initiale peut se faire lors de la déclaration ou dans /'algorithme.
32---------Algorithmique
Techniques fondamentales de programma tion
■ Remarq u e
Une variable qui n'a jamais été initialisée avec une première voleur ne peut
pas être utilisée dons des instructions outre que son initialisation (première
affectation de voleur).
■ Re m arqu e
En olgorithmie, les opérations et opérote,,urs "complexes" sont toujours repré-
sentés par des verb es à l'infinitif.
■ Re marque
L'espace qui suit une parenthèse est facultatif, nous l'ajoutons uniquement
pour la lecture humaine que ce soit dons un algorithme ou dons un
programme.
FIN
34---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
Tous les opérateurs fonctionnent soit avec des variables, soit a vec des voleurs,
soit avec une variable et une voleur.
Un opérateur est dit binaire s'il a deux opérandes, c'est-à-dire qu 'il fonctionne
avec deux valeurs. Un opérateur unaire n'a qu'un opérande.
res <- a x b
ECRIRE ( " La multiplication d e a e t b vaut " res )
ECRIRE ( z + y)
ECRIRE ( z - y)
ECR IRE(z x 3 . 89 )
FIN
■ Remarque
Vous pouvez remorquer dons l'algorithme précédent que l'opérateur ECRIRE
permet d 'afficher la voleur du résultat d 'une opération sons l'obligation de la
stocker dons une outre variable.
■ Remarque
Pour ajouter des commentaires dons notre algorithme afin d 'indiquer des
informations o u lecteur, nous utilisons le symbole / / . Grâce à ce symbole, un
outre développeur comprend qu 'il ne s'agit pas d 'une instruction mois d 'une
indication sur le comportement de l'algorithme.
36---------Algorithmique
Techniques fondamentales de programmation
Comme les entiers ont une division entière, les réels ont une division réelle
avec l'opérateur / classique.
PROGRAMME Operateur_reel
VAR
n : REEL< - 3 0 . 87
rn : REE L <- 4 . 65
DEBUT
ECR I RE ( " n divisé par rn vaut " )
ECRIRE ( n / rn ) // affiche 6 , 6387 0 96 774
F IN
DE BUT
ECRIRE ( " Egalité • Il
a= b ) // FAUX
EC RIRE ( " Différence : 11 1 a? b ) // VRAI
ECRIR E ( " In f ér i orité : ", a < b ) / / VRAI
Les variables et opérateurs _ _ _ _ _ _ __ _ __ 37
Chapitre 2
■ Remarque
En olgorithmie, nous ne pouvons comparer que deux voleurs de même type.
Retournons un peu à la vie réelle pour expliquer les opérateurs sur les
booléens. Lorsque vous décidez de sortir de chez vous par exemple, vous
prenez votre décision en fonction de plusieurs critères. Vous regardez si la
sortie vous intéresse ou si elle est nécessaire et si le temps vous permet de
sortir. Vous effectuez donc des calculs logiques en prenant en compte ces
critères. Ces liens entre les conditions sont représentés en informatique par les
opérateurs logiques.
L'opérateur binaire OU renvoie VRA I si au moins un des deux opérandes est
VRAI.
PROGRAMME Exemple_operateurs_logiques
VAR
interet : BOOLEEN<- FAUX
necessaire : BOOLEN <- VRAI
DEBUT
ECRIRE ( " OU l ogique : ", int ere t OU nec essa ire ) II VRAI
ECRIRE ( " ET logique : ", i n te ret ET necessaire ) II FAUX
ECRIRE ( " NON logique : ", NON necessaire ) Il FAUX
F IN
La logique de ces trois opérateurs sera un peu plus approfondie dans le chapitre
' suivant.
38---------Algorithmique
Techniques fondamentales de programmation
3.1 Concaténation
40---------Algorithmique
Techniques fondamentales de programmation
3.2 Extraction
- La chaîne existante.
- La position du caractère à partir duquel nous voülons commencer à reco-
pier la chaîne.
- Le nombre de caractères à recopier dans la sous-chaîne à partir de la posi-
tion indiquée.
PROGRAMME Exemple_Extraire
VAR
chainel : CHAINE< - " Hello World "
res : CHAINE
DEBUT
r es <- EXTRAIRE (chainel, 7 , 2 )
ECRIRE ( res ) / / Wor
FIN
3.3 Longueur
Cet opérateur ne vous semble pas forcément utile maintenant mais nous
allons voir au cours de cet ouvrage qu'il est primordial dans tout algorithme
ou programme qui manipulent des chaînes de caractères.
4.1 Typage
■ Remarque
Ces quatre classes de langage peuvent vous paraître compliquées à gérer au
départ mais rassurez-vous, une fo is que vous commencerez à programmer, le
type de typage deviendra naturel et vous ne vous poserez plus de questions.
4.2 Opérateurs
La plupart des langages actuels utilisent les opérateurs classiques d'une calcu-
latrice pour les calculs mathématiques : +, - , *, /. Pour la division, vous
pouvez retrouver la division entière avec le symbole // et la division réelle avec
le symbole /. Le reste de la division euclidienne, le modulo, est généralement
représenté par l'opérateur % . Vous retrouvez également une affectation plus
classique avec le symbole = au lieu de la flèche.
Vous devez donc vous demander maintenant comment gérer l'égalité. Tout
simplement avec le double égal : ==. Et la différence ? Avec ! = . Les opérateurs
d'infériorité et de supériorité restent les mêmes qu'en algorithmie.
■ Remorque
En programmation, le ! représente le NON logique. La différence étant
l'inverse de l'égalité, donc un non égal, il nous suffit de faire suivre un ! par un
= pour la représenter.
44---------Algorithmique
Techniques fondamentales de programmation
En algorithmie, nous n'avons que le type REEL pour représenter les nombres
à virgules. En prograµimation , une question peut se poser selon le langage :
flottant ou décimal ?
Ces deux types représentent le type REEL en programmation. Il y a cependant
une légère nuance entre les deux, nuance qui peut provoquer quelques
surprises et sueurs froides au développeur.
Le flottant est un nombre réel qui est représenté en machine avec une
écriture scientifique binaire. Sans rentrer dans les détails, le flottant est
calculé pour ne garder que les puissances significatives du réel. Ce calcul rend
donc le flottant quelques fois inexact par rapport à la valeur attendu. Par
exemple, nous voulons stocker 0, 1 avec un flottant et en l'affichant, nous
obtenons 0,100000000001, ce qui peut donc provoquer quelques erreurs si
nous n'y prêtons pas gare. Cette erreur de précision vient du calcul que fait la
machine pour stocker notre valeur réelle .
Le décimal est un nombre à virgule fixe . Ici la machine stocke aussi les
chiffres avant la virgule et ceux après tels quels. Le décimal apporte donc une
valeur exacte contrairement au flottant. Cependant, il est largement plus
gourmand en mémoire.
46---------Algorithmique
Techniques fon damentales de programmation
5.1 Installation
Python n 'est installé d'office que sur les ordinateurs possédan t comm e
système d'exploitation Linux ou macOS.
Pour les développeurs qui· sont sous Window s, vous devez installer Py thon en
suivant les instructions sur le site officiel: https ://www.python.org/
Cl Pour vérifi er que Python est bien installé, lancez une console/ un terminal ou
cmd et tapez la ligne de commande python (ou p y thon3 selon l'installa-
tion). Vous devriez avoir accès à ce que nous appelons la calculette Python,
comme le montre la figure suivante. Cette calculette permet de lancer rapi-
dement des instructions en Py thon, notamment pour les tester rapidement.
Pour sortir de la calculette, tapez l'instruction exit () .
0 f; O ludivine - •bash - 89•24
iMac-de -Ludivine-2:- lu divine$ pythan3 :t9
Python 3 . 9 . 6 (default, Oct 18 2022, 12 : 41:40 )
[ Cl ang 14.0. 0 (c lan g-1400 . 0.29 .202 )] on da r win
11 11 11
Type help 11 , copy ri gh t'' , credi ts 11 or '1 1icense" for more informa t ion.
»> a = 1
>>> a
1
>» exit()
Calculette Python
Les va riables et opérateurs _ _ _ _ _ __ _ _ _ 47
Chapitre 2
■ Re marque
Un IDE est logiciel qui va vous aider et vous conseiller pour écrire votre
programmation. Il facilite votre travail en connaissant la syntaxe du langage
dons lequel vous programmez. Ainsi, il indiquera vos erreurs plus rapidement et
il vous permettra de lire plus rapidement votre code grâce à la coloration syn-
taxique. Certains IDE vous proposent en plus de compléter automatiquement
votre code avec un système d'outocomplétion pseudo-intelligente.
IDLE
CIPour créer un nouveau script, allez dans le menu Fichier - Nouveau et
enregistrez votre script avec l'extension .py.
Cl Cliquez sur le menu Run pour exécuter votre code.
Vous n'êtes pas dans l'obligation d'utiliser IDLE. Vous pouvez également coder
avec SublimeText ou PyCharm par exemple. Il existe un assez grand nombre
d'IDE pour Python, à vous de choisir celui qui vous convient le mieux.
48 - --------Algorithmiq ue
Techniques fondamentales de programmation
■ Remarque
Il est conseillé d'installer /'avant-dernière version du langage afin d'assurer la
compatibilité avec les librairies tierces pour les jours futurs où votre niveau vous
permettra de les utiliser pour aller plus loin.
■ Remarque
À la différence des langages interprétés, il existe les langages compilés où le
code est analysé avant son exécution et où il n 'est possible d 'exécuter un
code que si sa syntaxe est correcte, c'esr-à-dire que le code compile.
■ Remarque
Python est un langage dit sensible à la casse, c 'est-à-dire q ue l'identifiant a
n 'est pas le même que l'identifiant A les majuscules et minuscules ont donc
leur importance .
Les variables et opérateurs _ _ _ _ _ _ _ __ _ 49
Chapitre 2
Nous remarquons que les chaînes peuvent être entre simples ou doubles
quotes, peu importe .
Il est également possible en Python de faire des déclarations multiples en une
simple instruction grâce à la virgule entre les variables et celle entre les valeurs.
Les valeurs seront affectées dans les variables dans l'ordre de déclaration.
Les constantes en Python n'existent pas réellement. Nous indiquons que la
variable est une constante en mettant son identifiant en majuscule, mais le
langage ne nous empêche pas par la suite d'en modifier sa valeur.
- les expressions en paramètres peuvent être des valeurs ou des variables, peu
importe, sachant que seules les valeurs seront affichées et non le nom des
variables.
- sep (optionnel) indique ce qui va séparer ces expressions, par défaut il s'agit
d'un espace.
- end (optionnel) indique ce qui sera affiché après toutes les expressions, par
défaut il s'agit d'un retour à ligne (\ n).
a = 1
X= 8 . 7
s = " hello "
print ( " mes variabl es s ont a avec l a valeur ", a , ' b
avec la valeur ', b , ' et s = ', s )
# affiche "mes variables s ont a avec la valeur 1 b
ave c la val e ur 8.7 et s hello "
print ( " a sans espace par defaut ", a , sep= '' )
# a ff iche " a sans es pace pa r de f autl "
print ( " sans saut ", end= " " )
pr i nt ( " de l i gne " )
# affiche so u s " saut de ligne "
52---------Algorithmique
Techniques fondamentales de programmation
5.4.2 LI RE en Python
La fonction i nput permet de lire l'entrée clavier. Elle est donc la traduction
de LIRE de l'algorithmie.
Par défaut, input retourne une chaîne de caractères de type s t r voulant dire
string (chaîne en français ) :
1 var= input (expressio n)
5.5 Opérateurs
■ Remarque
L'opérateur+ s'applique aussi sur les booléens et effectue un OU logique .
1 print ( l != 1 )
print ( l > 1 )
# affiche False
# affiche False
54---------Algorithmique
Techniques fondamentales de programmation
1 print (l == 1 or False )
print(not False )
# affiche Tr ue
# affiche True
Python possède une multitude d'opérations sur les chaînes de caractères. Nous
ne décrivons ici que les principales et nous renvoyons le lecteur à la documen-
tation officielle de Python pour plus d'informations .
Soient deux chaînes s et t, un caractère x et un entier n :
- x in s : teste six appartient à s .
- x not in s : teste six n'appartient pas à s.
- s + t : concaténation de s et t.
- s * n ou n * s : concaténation de n copies de s .
- len ( s) : retourne un entier représentant la longueur de s .
- s . coun t ( x : retourne un entier représentant le nombre d'occurrences de
x dans s.
- s . index ( x) : retourne un entier représentant l'indice de x dans s.
s = "h e llo world "
print (l en (s )) # 11
print (s . index ( ' h ' )) # 0
print (s . count( ' o ' )) # 2
res s + " coucou " # res vaut hello world coucou
res = s * 2 il
TT res vaut hello worldhello world
■ Rem arque
Attention, en programmation, contrairement à l'algorithm ie, nous com m en-
çons à compter à O et non 1. Le premier caractère d'une chaîne de carac-
tères a donc la position O en Python .
Les variables et opérateurs _ __ _ _ _ _ _ _ _ 55
Chapitre 2
6. Exercices
6.1 Exercice 1
6.2 Exercice 2
6.3 Exercice 3
6.4 Exercice 4
■ Remarque
Pensez à tester tous les cos possibles dans vos scripts Python pour ne pas avoir
de mauvaises surprises lors d'une exécution non prévue.
5 6 - - - -- ----Algorithmique
Techniques fondamentales de programmation
6.5 Exercice 5
6.6 Exercice 6
Chapitre 3
Conditions, tests et booléens
Dans notre vie, notre comportement est dirigé par une multitude de décisions
à prendre . Tou jours avec l'exemple du passage piéton, nous allons traverser si
le voyant piéton est vert, sinon nous allons attendre s'il est rouge. Il en va de
même pour un algorithme et un programme, nous devons guider l'ordinateur
pour qu 'il puisse prendre les bonnes décisions et donc exécuter correctement
nos instructions.
Souvenez-vous que nous devons tout expliquer à la machine, elle ne prendra
jamais une décision par elle-même, sauf peut-être le fait de s'éteindre en cas de
court-circuit. Vous devez indiquer à l'ordinateur dans quels cas il peut exécu-
ter vos instructions. Par exemple comme quand un adulte apprend à un jeune
enfant à dessiner : l'adulte lui montre comment tenir le crayon, quel est le
bout qui permet de dessiner, qu'on ne peut dessiner que sur une feuille et non
sur une table ou un mur, etc . L'avantage de la programmation pour nous est
que nos explications sont beaucoup plus simples à formuler et que la machine
nous écoute forcément sans jamais en faire à sa tête et surtout comprend par-
faitement du prem ier coup.
5 8 - - - - - - -- -Algorithmique
Techniques fondamentales de programmation
Les tests et conditions représentent une idée de base très simple pour bien
guider notre programme : choisir d'exécuter telle ou telle instruction selon la
validité d'une condition. Nous testons donc la validité d'une condition pour
donner l'autorisation ou non de continuer le déroulement du programme
comme : si le feu piéton est vert (condition), alors je traverse (instruction).
Le test peut également contenir une ou plusieurs alternatives : si le feu piéton
est vert (condition), alors je traverse (instruction) sinon j'attends que le feu
piéton passe au vert.
Oui dit condition, dit booléen. Les booléens sont les types les plus simples en
informatique. Ils ne peuvent prendre que deux valeurs: VRAI ou FAUX . La
relation entre une condition et un booléen est donc totalement explicite car
une condition est toujours une expression de type booléenne.
Une condition est systématiquement le résultat d'une comparaison ou de
plusieurs comparaisons reliées entre elles par les opérateurs logiques (ET , OU,
NON) .
Commençons par étudier les structures conditionnelles avec une seule compa-
raison pour introduire par la suite la logique booléenne (ou algèbre de Boole)
pour gérer des tests avec plusieurs conditions.
■ Remarq ue
Nous rappelons l'importance de l'indentation d'un algorithme ou d 'un pro-
gramme. L'indentation permet d'avoir une lecture simplifiée car nous pouvons
voir sans réfléchir où commence un bloc et où il finit. Pour le moment, vous ne
pouvez pas vraiment vous rendre compte de son importance, mais dans la
suite de cet ouvrage, cela deviendra plus que pertinent avec nos premiers
programmes complexes et complets.
1 ...
F INSI
Il est vrai e
Exemple :
PROGRAMME Entier_positif
VAR
x : ENTIER
DEBUT
ECRIRE ( " Entr ez un entier de votr e choi x" )
x <- LIRE ()
SI x > 0
ALORS
ECRIRE ( " Votr e ent i e r est po s it if " )
F INSI
FIN
60---------Algorithmique
Techniques fondamentales de programmation
Avec deux SI à la suite, l'algorithme teste quoiqu'il advienne les deux condi-
tions, si l'entier est positif puis si l'entier est négatif, ou inversement selon
l'ordre des deux SI .
Cependant, nous sommes d'accord, un entier ne peut pas être positif et négatif
à la fois. Ajoutons donc simplement un SINON à notre algorithme pour les
négatifs :
PROGRAMME Entier_ pos i t if_negatif
VAR
x : ENTIER
DEBUT
ECRIRE ( "Entrez un entie r de vo tre choix " )
x <- LIRE ()
SI x > 0
ALORS
ECRIRE ( " Votre entier es t po s iti f " )
SINON
ECRIRE ( " Votre e nt ier es t négatif " )
FINSI
FIN
Notre algorithme devient de plus en plus juste mais il nous reste un point à
définir : l'entier valant zéro. Zéro n'est ni positif ni négatif, c'est donc un cas
particulier.
Nous pouvons ajouter un SI au début de l'algorithme pour tester la valeur
zéro mais cette solution n'est pas optimale. Effectivement, quelle que soit la
valeur de l'entier, il sera testé deux fois : une pour l'égalité et une pour la supé-
riorité à cause des SI qui se suivent.
Une solution propre et optimisée est de définir le zéro comme cas par défaut
du S I NON en y ajoutant un nouveau SI, testant si l'ent ier est négatif SINON
c'est qu'il est à zéro (ni positif ni négatif). Mettre un S I dans SI est appelé im-
briquer des instructions ou tests imbriqués.
PROGRAMME Entier_ pos i tif_ negat if nul
VAR
x : ENT IE R
DEBUT
ECR I RE ( " En tr ez un e nti er d e votre choix " )
x <- LIRE()
SI x > 0
Conditions, tests et booléens _ _ _ _ _ _ _ _ _ 61
Chapitre 3
ALORS
ECRIRE ( " Vot re entier est positif " )
SINON
SI x < 0
ALORS
ECRIRE ( " Votre entier es t n é gatif " )
SINON
ECRIRE( " Vo tre en tier est nul " )
F' INSI
F'INSI
F'IN
■ Remarq u e
Pensez toujours à limiter vos instructions et vos variables dons vos algorithmes
et programmes afin d'optimiser la gestion de la mémoire pour les raisons évo-
quées ou chapitre précédent et donc de rendre vos codes plus performants.
PARDEF'AUT
Il instructions à réaliser par dé fa u t . Optionnel
F'INCASPARMI
Vous pouvez tester autant de cas que nécessaire. Le cas par défaut est tout à
fait facultatif.
6 2 - - - - - - -- -Algorithmique
Techniques fondamentales de programmation
PROGRAMME Mo i s_cas_parmi
VAR
mois : ENTIER
DEBUT
ECRIRE ( " Entre r un ch iffr e entre 1 et 6 comp r is " )
mois< - LI RE ()
CAS moi s PARMI
CAS : 1
ECRIRE ( " J anv i er " )
CAS : 2
ECR IRE ( "Février " )
CAS : 3
ECRIRE ( "Mars" )
CAS : 4
ECRIRE ( " Avri l" )
CAS : 5
ECRIRE ( "Mai " )
PARDEFAUT
ECRIRE ( " Juin " )
FINCASPARM I
FIN
2. La logique booléenne
Écrire une condition qui teste la validité d'un seul fait est assez logique, voire
simple. Les conditions augmentent en complexité dès lors que nous augmen-
tons le nombre de fais à valider, que ce soit dans la vie de tous les jours ou en
informatique.
Lorsque nous testons des conditions multiples en tant qu'être humain, notre
cerveau raisonne tellement vite que nous n'avons pas l'impression de réfléchir
ni même de résoudre une ·équation. Et pourtant ...
Reprenons l'exemple du passage piéton. Il vous paraît normal, avant de traver-
ser à un feu , de vérifier que le voyant piéton est vert et d'également vérifier
qu'aucune voiture ne grille le feu. Vous analysez donc deux conditions et avez
l'impression de les faire en même temps avec une seule et unique condition.
Mais votre cerveau reçoit bien deux conditions à vérifier, donc il résout ces
deux conditions dans une équation.
Comme nous l'avons indiqué dans le chapitre d'introduction de cet ouvrage,
vous devez tout décrire à la machine, faire du vrai pas-à-pas, aucun raccourci
n'est possible. Il nous faut donc une manière simple de représenter les condi-
tions multiples.
Pour formuler correctement cette équation avec plusieurs conditions, George
Boole, un mathématicien du XIXe siècle, créa une algèbre binaire que Claude
Shannon utilisa plus d'un siècle plus tard en informatique. L'algèbre de Boole,
appelée aussi logique booléenne selon le contexte, permet d'analyser plusieurs
conditions en même temps dans une même équation, donc dans une même
structure conditionnelle. Vous comprenez maintenant d'où vient le nom du
type booléen.
L'implémentation de cette algèbre est quasiment naturelle en informatique.
Un ordinateur fonctionnant par impulsion électrique, le FAUX est donc repré- q:
2.2.1 ET logique
Le ET logique représente la multiplication de deux booléens 1 donc de deux
conditions, donc de deux comparaisons en informatique . Il faut que les deux
booléens du ET soient à VRAI pour que le tout soit VRA I. Par exemple 1 il faut
que le feu piéton soit au vert et que le passage soit libre pour traverser.
■ Remarq ue
Le ET logique est plus précisément une analogie du signe de la multiplication
de deux nombres: si les deux nombres sont positifs, le résultat sera positif sinon
il sera négatif.
Grâce à cette table de vérité, nous pouvons poser notre condition multiple à
l'ordinateur pour qu'il la résolve :
PROGRAMME Et_ logiqu e
VAR
fe u_pie to n_vert : BOOLEEN
passage_libre : BOOLEEN
DEBUT
ECRI CRE ( " Le feu est - il v er t ? VRA I ou FAUX " )
feu_pieton_ vert <- LIRE ()
ECRICRE ( " Le passage est - il l ibr e? VRAI ou FAUX " )
passage_ l ibre <- LIRE ()
SI fe u_pieton_ v ert ET passage_ libre
ALORS
ECRIRE ( " Vous pouvez trave rser" )
SINON
ECRIRE ( " Vou s ne dev ez pas traverser " )
FINSI
FIN
2.2.2 OU logique
Le OU logique est la représentation de l'addition en mathématiques classiques .
Il suffit que l'un des deux opérandes booléens soit VRAI pour que le résultat
soit VRAI , comme le montre la table de vérité du OU dans la figure ci-dessous.
a NON a
VRAI FAUX
FAUX VRAI
Ciel
so ett - - -- - ----llluie-- - - - - - - .
Température
normafei
.in
• •
Arbre de décision du cas: dois-je sortir ou·non
Dans cet exemple, nous ne sortons pas si le ciel est couvert. S'il fait soleil, notre
sortie dépendra de la température : si elle est normale, nous sortons, si elle est
élevée nous ne sortons pas. En cas de pluie, le vent sera décisionnaire : nous
sortons avec un vent faible et nous restons à l'intérieur avec un vent fort.
Traduisons toute cette réflexion en algorithme.
PROGRAMME So r tir_ou_ rester_ no n _ optimise
VAR
ciel : CHAINE
te mpera t u re : CHAINE
vent : CHAINE
DEB UT
ECRIRE ( " Entre z la va l eur du ciel : co u vert , pluie ou so l e il" )
ciel <- LIRE ()
ECRIRE ( " Entrez la valeur de l a température : normale o u elevee " )
te mperat u re <- LIRE ()
ECRIRE ( " Entrez l a vale u r du vent : faible o u for t " )
70---------Algorithmique
Technique s fond amentales de programmation
ve n t <- LIRE ()
SI ciel = "c ouvert "
ALORS
ECRIRE ( " Nou s restons à l ' intérieur " )
SINON
SI ciel = "s oleil "
ALORS
SI temperature = " normale "
ALORS
ECRIRE ( " Nou s s o r ton s dehors " )
SINON
SI temperature = " elevee "
ALORS
ECRIRE ( " Nous rest o ns à l ' inté rieur" )
FINSI
FI NSI
SINON
SI ciel = "pl u ie"
ALORS
SI vent= " faible "
ALORS
ECRIRE ( "N ous sortons dehors " )
SINON
SI vent = " fort "
ALORS
ECRIRE ( " Nous restops à l ' intérieur " )
FINSI
FINSI
FINSI
FI NSI
FINSI
FIN
Tou tes les bases théoriques sur la gestion des conditions étant posées, passons
maintenant à son implémentation en Py thon.
Bloc 1 :
instructions
Tabulatio n Bloc 2:
Q instructions
Cette notion de bloc impose d'aborder la visibilité des variables, appelée encore
la portée ou le scope.
Les variables d'un algorithme peuvent être utilisées dans n'importe quelle ligne
car elles sont toutes connues de tout l'algorithme grâce à leur déclaration dans
le bloc VAR avec le début de l'algorithme. Ces variables sont dites globales .
Conditions, tests et booléens _ _ _ _ _ _ _ _ _ 73
Chapitre 3
Blocl:
a=l
Bloc 2:
b=3
Bloc 3:
a=6
b=O
c=3
Bloc 2 suite:
a=2
If accès à c interdit
Bloc l suite :
// accès à b et c interdit
Variables et blocs
74---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
Attention à ne pas utiliser de parenthèses pour une condition simple. Nous
verrons par la suite que l'abus de parenthèses en Python peut provoquer une
confusion à la lecture du script par l'interpréteur et par l'humain.
■ Remarque
Selon vos besoins, vous pouvez également imbriquer des tests dans d 'autres
tests, aucune règle de syntaxe ne vous en empêche.
Conditions, tests et booléens _ _ _ _ _ _ _ __ 75
Chapitre 3
1 if X> Ü :
pr i nt ( " x es t positif " )
76---------Algorithmique
Techniques fondamentales de progra mmation
Les deux algorithmes qui affichent le nom du mois en fonction de son numéro
deviennent donc le seul script suivant :
mois = i n t( input ( ' Entrer un entier entre 1 et 6 ' ))
if mois== 1 :
print ( ' Janvier ' )
elif mois== 2 :
print ( ' Février ' )
elif mois== 3 :
print ( ' Mars ' )
e l if mois= = 4 :
pri n t ( ' Avr i l ' )
elif mois== 5 :
print ( ' Mai ' )
e lse :
print ( ' Juin ' )
4. Exercices
4.1 Exercice 1
4.2 Exercice 2
4.3 Exercice 3
4.4 Exercice 4
Écrivez un algorithme qui détermine si une année entrée par l'utilisateur est
bissextile. Une année bissextile est un entier divisible par quatre seulement s'il
ne représente pas une année de centenaire (2000, 1900, 1800, etc.). Dans ce
cas, l'entier doit être également divisible par 400. Codez le script Python
correspondant.
_ _ _ _ _ _ _ _ __ __ 79
Chapitre 4
Les boucles
Dans le chapitre précédent, nous avons appris à guider notre algorithme en lui
demandant de tester des conditions àfin d'exécuter ou non des instructions.
Ce fut le premier pas d'une réflexion importante pour communiquer quoi faire
et surtout quand le faire à la machine. Passons maintenant au deuxième pas
primordial : les itérations.
Reprenons les deux exemples du premier chapitre : la notice de montage d'un
meuble en kit et la recette de la tarte aux pommes .
Dans le cas d'une notice de montage, il est souvent demandé de répéter les
mêmes actions sur les mêmes types de pièces. Un exemple est représenté par
la figure suivante : il nous est demandé d'insérer quatre vis dans une planche
et de le faire pour les quatre planches . Il s'agit bien des mêmes actions à faire
quatre fois , donc une itération de quatre tours. Le x4 de cette figure indique
ce nombre d'itérations et nous semble parlant et tout à fait logique . Nous
allons découvrir comment le traduire pour l'ordinateur dans la suite de ce
chapitre.
80---------Algorithmique
Techniques fondamentales de programma tion
0
8=> c)
Une étape d'une notice de montage de meuble en kit
Pour la recette de cuisine, les répétitions se trouvent dans la gestion des
pommes : pour chaque pomme, l'éplucher et la couper en tranches qui seront
disposées dans la tarte. Nous n'arrêtons pas ces actions tant qu 'il y a encore
des pommes pour la tarte. Nous pouvons également dire que nous continuons
ces actions jusqu'à qu'il ne reste plus de pommes.
À travers ces deux exemples, nous avons vu les trois grands cas d'itérations
possibles en informatique: avec un nombre fixe d'itérations et avec le test
de la validité d'une condition, avant ou après la répétition des actions .
L'ordinateur, tout comme nous, est amené à exécuter plusieurs fois des actions
identiques, ce que vont permettre les instructions itératives, souvent appe-
lées boucles par les développeurs. L'itération représente ici une séquence
d'instructions à exécuter plusieurs fois , avec un nombre fixe de répétitions ou
une condition à valider pour arrêter ou continuer les itérations.
Les boucles _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ 81
Chapitre 4
■ R e morque
Les structures itératives sont également présentes pour éviter le copier-coller
d 'instructions. En effet, si vous devez copier un certain nombre d 'instructions
identiques et les coller les unes après les autres, ce la peut vouloir dire que vous
devez utiliser une structure itérative. Par exemple, pour afficher un compte à
rebours de 10 à 0, il est plus simple çle boucler sur la décrémentation d 'un
entier et son affichage que de réécrire onze fois sa décrémentation et son
affichage.
2. Tant Que
82---------Algorithmique
Techniques fondamentales de programma tion
Revenons en cuisine avec notre tarte aux pommes . Une manière de gérer les
pommes avec cette structure serait la suivante :
TANT QUE il reste des pomme s
FAIRE
Prendre une pomme
Ép luche r la pomme
Couper la pomme e n tranches
FINTANTQUE
2.2 Exemples
cp t <- cp t + 1
1 FIN
FINTANTQUE
Un dernier exemple est un menu utilisateur qui se répète à moins que l'utili-
sateur entre une chaîne de caractères J?récise. Dans notre cas, nous allons faire
un menu simpliste qui demande à l'utilisateur de continuer (entrée égale à oui)
ou d'arrêter (entrée égale à non).
PROGRAMME Me nu_ t a nt_qu e
VAR
r eponse : CHAINE
DEB UT
ECRIRE ( " Vou l e z - v o us continu er ? (oui / no n) " )
repon se <- LI RE ()
TANT QUE repons e = " ou i"
FA I RE
ECRI RE ( " Vou l ez - vou s conti nu e r? (ou i / non ) " )
repons e <- LIRE ()
FINTANTQUE
FIN
.. 1
84---------Algorithmique
Techniques fondamentales de progra mma tion
3. Répéter .. . Jusqu'à
Le REPETER JUSQU 'A peut être considéré comme un TANT QUE inversé :
les instructions sont d'abord répétées une fois avant de tester la condition.
Quelle que soit la validité de la condition, les instructions du bloc sont forcé-
ment exécutées une fois.
REPE. T.E.R
Notre deuxième version pour la gestion des pommes de notre tarte est donc la
suivante:
REPETER
FAIRE
Prendre une pomme
Éplucher la pomme
Couper la pomme en tranches
J USQU ' A il ne reste plus de pommes
■ Re m arqu e
Nous pouvons remorquer que les conditions du TANT QUE et du REPETER
JUSQU ' A sont des conditions inverses. Nous testons s'il reste des pommes avec
le TANTQUE alors que nous testons s'il ne reste plus de pommes avec le
REPETER JUSQU ' A
Les boucle s _ _ _ _ _ _ _ _ _ _ _ __ _ 85
Chapitre 4
3.2 Exemple
Nous remarquons bien avec cet algorithme que le REPETE R JU S QU 'A est plus
approprié à notre menu utilisateur car les opérateurs L IRE et ECR IRE ne sont
plus écrits qu'une seule fois avec le même résultat que l'algorithme précédent.
4. Pour
■ Re marqu e
Si vous voulez écrire un POUR décroissant, qui décrémente donc le compteur,
il vous suffit de déclarer un pas négatif.
VAR compteu r : ENTIER
POUR compteur ALLANT de . . . à ... AU PAS DE
FAIRE
1 ...
FINPOUR
Il suite d ' in stru ctions à répéter
4.2 Exemples
Maintenant que vous connaissez le POUR, vous devez vous poser des
questions sur notre algorithme Comptage_ tant_ q u e. Vous paraît-il non
approprié à la logique? La réponse est évidemment oui : qui dit compter
jusqu'à une fin donnée, dit un compteur, donc une structure POUR.
PROGRAMME Comptage
VAR
cpt : ENTIER< - 1
borne : ENTIER
DEBUT
ECRIRE ( " Entrez un nombre supérieur à l " )
borne <- LIRE ()
POUR i ALLANT de 1 à borne AU PAS DE 1
FAIRE
ECRIRE ( cpt )
FINPOUR
FIN
Cet algorithme est plus sûr que celui utilisant le TANT QU E : l'incrémentation
du compteur étant gérée automatiquement par le POUR, nous sommes sûrs
que cette boucle se terminera alors que le TANT QUE laisse à la charge du
développeur cette incrémentation, ce qu'il risque d'oublier, d'où le risque de
boucle infinie.
■ Remarque
Pour les structures POUR imbriquées, il est de convention d 'utiliser les lettres i, j,
k, 1... pour les compteurs, comme en mathématiques.
Les boucles _ __ _ _ _ _ __ _ __ _ _ _ __ 89
Chapitre 4
6. Attention danger
Le premier danger des structures conditionnelles est la boucle infinie. Vous
devez êt re certain que votre condition de sortie sera validée au cours de
, l'exécution de l'algorithme ou que votre compteur atteindra la borne maxi-
male.
Prenons deux exemples de boucles infinies.
Le premier est un comptage avec la boucle TANT QUE :
PROGRAMME Comptage_infini
VAR
cpt : ENTIER< - 1
borne : ENTIER
DEBUT
ECRIRE ( "Entr e z un nombre supér i e ur à l " )
borne< - LIRE ()
TANT QUE cpt? borne
FAIRE
ECRIRE (cpt )
FINTANTQUE
FIN
9 0 - - - - -- ---Algorithmique
Techniques fondamentales de programmation
■ Remarque
Si vous avez un nombre d 'itérations fixes, utilisez toujours une structure POUR
Nous avons glissé une petite erreur de logique dans cet algorithme : le pas du
compteur est de -1 et non de 1. Le compteur aura donc comme valeur 1, 0, -1 ,
-2, -3, . .. et n'arrivera jamais à la valeur 10. La boucle sera donc infinie, affi-
chant à l'écran pour une entrée utilisateur de 10: 10, 0, -10, -20, -30 ...
Pensez donc bien à bien choisir les éléments de vos structures itératives pour
éviter les boucles infinies.
Un dernier danger vient de l'imbrication de plusieurs structures itératives.
Plus vous allez imbriquer de structures les unes dans les autres, plus les opéra-
tions vont être répétées et donc plus l'ordinateur devra retenir ces
instructions, les résultats intermédiaires et les valeurs des compteurs entre
autres . Selon l'objectif de ces imbrications, par exemple un calcul complexe
avec six imbrications de POUR itérant 1000 fois chacune, vous pouvez saturer
la mémoire de l'ordinateur. Une fois saturée, le programme ne pourra plus
fonctionner, vous aurez atteint les limites de la machine . Ce problème est
appelé dépassement de mémoire et vous ne pourrez rien y faire sauf revoir
votre logique.
Les boucles _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ 91
Chapitre 4
7. Itérons en python
7.1 Pour
Commençons par itérer sur une chaîne de caractères (qui est bien un ensemble
de caractères) :.
fo r carac in " hell o world " :
Utilisons donc ce range pour écrire en Python notre st ructure itérat ive POUR.
for i in range (10) :
prin t (i , end= '' ) # affiche 0 1 23456789
print () # juste un saut de li gn e
for i i n range ( l , 11 )
print (i , e nd ='' ) # affiche 12345678910
print ()
f or i in ra nge ( l , 11 , 2 )
print (i , e nd = '' ) # affiche 13579
p ri nt ()
Nous retrouvons bien notre structure itérative POUR de l'algorithmie avec une
syntaxe moins verbeuse : par défaut, le compteur commence à 1 et le pas est l.
de 1.
■ Re m arq u e
Par convention, en programmation, les bornes maximales ne sont jamais
incluses, sauf quelques rares exceptions.
1 f or i in range (1 , 11 ) :
print (i , ' x ' , table , '=', tab l e · *i )
Tout comme les tests imbriqués sont possibles en Python, les boucles imbri-
quées le sont également.
Codons un script pour générer les tables de multiplication de 1 à 10 :
for i in range (1 , 11 ) :
f or j in range ( l , 11 ) :
print (i , 'x ', j , '=', j *i )
7.5.1 Break
Le mot-clé break est utilisé dans un for ou un whil e dans l'objectif
d'interrompre la boucle courante.
for i in range (1 0) :
1 print (i )
b r ea k
f o r i~ ~n =:a;g7 (l O)
break
1 print (i )
Le script précédent affiche les valeurs Oà 4 et interrompt les itérations dès que
la variable i prend comme valeur 5.
■ R e marqu e
Le break est à utiliser que si ne pouvez pas faire autrement, il ne s'agit pas
d 'une bonne technique de programmation.
7.5.2 Continue
Le continue est un court-circuit : il permet de sauter l'itération courante et
de passer à la suivante automatiquement sans exécuter les instructions du
bloc de la boucle. Il est toujours utilisé dans une structure conditionnelle.
fori~ :n=:a;g7 (1 0)
1 continue
pri n t (i )
Les boucles _ _ _ __ _ _ __ _ _ _ _ _ 95
Chapitre 4
■ Remarque
Le continue, comme le break, est à utiliser que si ne pouvez pas faire
autrement, il ne s'agit pas d'une bonne technique de programmation.
7.5.3 Boucle-else
Python permet de gérer plus finement les boucles interrompues par un brea k
avec les "boucle-else". Le principe est assez simple : la boucle est suivie d' un
else. Les instructions du bloc else sont exécutées après la boucle unique-
ment si cette dernière n'a pas exécuté de b reak, c'est-à-dire qu'elle s'est dérou-
lée normalement. Ce e l se peut s'appliquer autant au f o r qu'au while .
for i in range ( lO )
if i == 5
break
print (i )
els e :
print ( " je rentre dans le else du for " ) # pas exécuté car le
# for est inter r ompu
while i < 10
p r int(i)
i += 1
els e :
print( " je rentre dans le e l s e du while " ) # e x écuté car le
# while n ' est pas
# interrompu
8. Exercices
8.1 Exercice 1
8.2 Exercice 2
8.3 Exercice 3
8.4 Exercice 4
Écrivez un algorithme qui affiche les n premiers carrés, n étant un entier entré
par l'utilisateur. Codez le script Python correspondant .
8.5 Exercice 5
8.6 Exercice 6
8.7 Exercice 7
8.8 Exercice 8
Chapitre 5
Les tableaux et structures
1. Introduction
Jusqu'à présent, nous nous sommes préoccupés de variables qui n'avaient
aucun lien logique entre elles. Dans ce chapitre, nous allons étudier comment
stocker et manipuler plusieurs valeurs qui sont liées entre elles afin de pousser
encore plus loin notre réflexion et surtout nos algorithmes et programmes. ·
2. Les tableaux
Imaginez une liste de courses simple : vous devez acheter douze œufs, du
beurre demi-sel, une salade, deux barquettes de fraises et trois tablettes de
chocolat. Chaque élément de cette liste est un produit à acheter.
Avec ce que nous avons appris, votre premier instinct serait de créer une
variable pour chaque produit :
PROGRAMME Liste cou r se var
- -
VAR
produitl CHAINE
produit2 CHAI NE
produit3 CHAINE
produit4 CHAINE
produ it 5 CHAINE
i : ENTIER
...
l QQ _ _ _ _ _ __ _ _ Algorithmique
Techniques fondamen tales de programmation
DEBUT
ECRIRE ( " Entrer un produit à a ch e t e r )
p r o d u itl <- LI RE ( )
EC RI RE( "Entrer un produ i t à a chet e r )
produ it 2 <- LIRE ()
FIN
Cet algorithme paraît lourd, rébarbatif, peu judicieux .. . Si vous devez ajouter
un produit à acheter, vous allez devoir réécrire cet algorithme en ajoutant une
variable produi t 6 et la valeur finale du compteur de la structure itérative
POU R. Vous allez en fait réécrire cet algorithme à chaque fois que vous voulez
ajouter ou enlever un produit.
Cette logique va à l'inverse de l'algorithmie : l'algorithme doit prendre en
compte le plus de cas possibles pour être le plus générique possible.
Pour pallier ce problème, il existe une structure de données particulière qui
permet de stocker plusieurs valeurs de même type : les tableaux. Avec cette
nouvelle structure, vous allez également simplifier la saisie et la manipulation
de ces valeurs tout en écrivant un algorithme plus compréhensible et donc
maintenable.
Une variable de type tableau peut contenir plusieurs valeurs, la seule obliga-
tion est que ces valeurs soient de même type en algorithmie. Les tableaux se
déclarent en même temps que les autres variables . Un tableau à une dimen-
sion représente une liste de valeurs. Un tableau à deux dimensions peut être
vu comme la feuille d'un tableur avec un nombre de colonnes par ligne
(chaque ligne a toujours le même nombre de colonnes) en plus du nombre de
lignes (toujours la première dimension par convention en informatique).
Les dimensions sont des valeurs entières qui vont indiquer le nombre de
lignes et/ ou de cases de la dimension.
Nous commencerons par les tableaux à une dimension, ce que nous appelons,
être humain, une liste.
Les tableaux et structures _ _ _ _ _ _ _ _ _ _ lQl
Chapitre 5
Une variable de type TABLEAU doit être déclarée avec ses dimensions, (chaque
dimension étant fixée dans la déclaration), et le type des valeurs qu'il va
stocker.
VAR
1 tab : TABLEAU [ l...d i m] : typ e
Nous avons déclaré précédemment une variable tab de type TABLEAU qui
possède une dimension qui commence à 1 et finit à la valeur dim, donc de dim
cases. Chaque valeur de tab sera du type "typ e" .
Pour accéder à une valeur du tableau, que ce soit en lecture ou en écriture, il
existe l'opérateur d'indexation : [ ] . le numéro de la case du tableau est
appelé son index, qui peut être une variable ou une valeur du type entier.
Pour accéder au premier élément d 'un tableau, nous utilisons l'opérateur [ l]
sur le tableau. De manière plus générale, pour accéder au ième éléments d'un
tableau tab, il faut utiliser tab [ i]. Avec cet opérateur, chaque élément du
tableau se comporte comme une variable normale.
■ Remorque
En olgorithmie, le premier indice a comme voleur 1 : nous commençons à
compter à partir de 1, ce qui est différent dons la programmation, comme
nous l'avons déjà remorqué . ·
Vous pouvez, comme pour les variables, initialiser un tableau lors de sa décla-
ration grâce à une paire d'accolades.
VAR
1
, Il , Il Il , Il Il , Il Il , , 11 Il , Il
Jours <- { lundi , mardi , mercredi , J e udi , vendredi ,
11 11
"same di ", dimanche } : TABL EAU [ l. .. 7] : CHAINE
FAIRE
EC RI RE ( " Entr er le produit à ach e t e r " )
prod ui ts [ i ] <- LI RE ()
1 F IN
F INPO UR
Avec cet algorithme, l'utilisateur va entrer les produits les uns après les autres :
12 œufs
1 salade
1 beurre demi-sel
1
2 barquettes de fraises
1
3 tablettes de chocolat
Il est dommage qu'il y ait deux informations distinctes dans chaque case : le
nom du produit et la quantité.
Les tableaux à deux dimensions vont nous permettre de mieux entrer not re
liste de courses en séparent le nom de la quantité, tout en gardant le lien sé-
mantique entre les deux (le 12 sera pour œuf, et non pour salade par exemple).
Nous avons déclaré précédemment une variable matrice de type TABLEAU qui
possède deux dimensions : dirnl lignes qui ont chacune d i rn2 colonnes .
Les tableaux et structures _ _ _ _ _ _ _ _ _ _ 103
Chapitre 5
FIN
Votre liste de courses informatisée est donc bien plus élégante maintenant :
Œufs 12
Salade 1
Beurre demi-sel 1
Barquettes de fraises 2
Tablettes de chocolat 3
Vous pouvez créer des tableaux avec plus de deux dimensions, il n 'existe
aucune limite, sauf celle de la mémoire de la machine. Il suffit d'ajouter une
dimension avec la paire de crochets lors de la déclaration du tableau.
Cependant, comprenez bien que plus votre tableau aura de dimensions, plus
sa manipulation sera complexe.
Par exemple, nous souhaitons construire un tableau afin de mémoriser les
superficies de chaque pièce des appartements d'un pâté d'immeuble. Il y a
9 immeubles, 6 étages par immeuble, 3 appartements par étage et 3 pièces par
appartement.
PROGRAMME immeuble
VAR
i , j , k, l ENTIER
superficies TABLEAU [l. . . 9] (1. . . 6] (1. .. 3 ] ( 1. . . 3] ENTIER
DEBUT
ma t [ 7 J [ 6 l [ 1 l [ 2 l < - 4 o
POUR i ALLANT de 1 à 9 AU PAS DE 1 FAIRE
POUR j AL LANT de 1 à 6 AU PAS DE 1 FAIRE
POUR k ALLANT de 1 à 3 AU PAS DE 1 FAIRE
POUR l ALLANT de 1 à 3 AU PAS DE 1
FAIRE
ECRIRE ( " Entr e z la superf i c ie de l ' immeuble "
i , " étage ", j , " appartement ", k, " p ièce ", 1 )
superficies [ i l [j] [ k ] [ l ] <- LIRE ()
FINPOUR
FINPOUR
FINPOUR
FINPOUR
FIN
3.1.1 Parcours
Pour parcourir un tableau, nous devons aller de la première case de la ligne à
la dernière. Cela indique donc que nous devons déclarer un compteur et, qui
dit compteur, dit structures itératives POUR.
PROGRAMME Parcours - tableau - une - dimension
VAR
jours< - { " lundi ", " mardi ", " mercredi ", " jeudi ", " vendredi ",
" samedi ", " dimanche " } : TABLEAU[l ... 7 ] : CHAINE
i : ENTIER
DEBUT
POUR i ALLANT DE 1 A 7 AU PAS DE 1
FAIRE
ECRIRE( " Le jour ",i," e s t ", jou rs [i ])
FINPOUR
FIN
3.1.2 Recherche
La recherche d'une valeur est une opération courante en informatique. Elle se
fait avec un parcours de tableau. À chaque case du tableau, nous allons vérifier
si la valeur de l'élément courant est égale à la valeur recherchée.
PROGRAMME Recherche tableau une dimension
- - -
VAR
jours < - { " 1 undi ", " mardi ", " mercredi ", " jeudi ", " vendredi " ,
" samedi", " dimanch e" } : TABLEAU [ 1 . .. 7] : CHAINE
jour_ a_chercher : CHAINE
i : ENTIER
trouve< - FAUX : BOOLEEN
DEBUT
ECRIRE ( " Entrer le nom du jou r à chercher " )
...
106-- - ------Algorithmique
Techniques fondamentales de programmation
SI t rouve= VRAI
ALORS
ECRIRE ( " le jour ", jou r _ a_chercher , " est présent " )
SINON
ECRIRE ( " l e jou r ", jou r a chercher , " est absent " )
FINSI
FIN
,
La logique pour rechercher dans ce tableau est la suivante : nous partons de
l'hypothèse que la valeur ne se trouve pas dans le tableau (t r ouve est
initialisé à FAUX lors de sa déclaration). Puis nous parcourons notre tableau en
comparant ses valeurs à celle que nous recherchons. Si la valeur recherchée
apparaît dans le tableau, la variable t r ouve prend comme valeur VRAI et
sinon elle reste à FAUX.
Pourquoi ne pas partir de l'hypothèse que la valeur se trouve dans le tableau
(initialiser trouve à VRAI) ? En partant de cette hypothèse, nous devrons
passer tr ouve à FAUX si la valeur actuelle n 'est pas celle recherchée. Avec
cette affectation, nous aurons de grandes chances de déclarer que la valeur
n'est pas présente alors qu'elle l'est. En effet, avec cette hy pothèse de départ,
le test fatidique sera toujours la comparaison de la valeur de la dernière case
du tableau .
Le s tableaux et structures _ __ _ _ _ _ _ _ __ 107
Chapitre 5
3.1.3 Réduction
Réduire un tableau revient à calculer une valeur à partir des valeurs présentes
dans le tableau . L'exemple le plus facile pour assimiler ce concept est le calcul
de la somme des valeurs des cases d'un tableau.
PROGRAMME Somme tableau
VAR
tab : TABLEAU[l ... 12] ENTIER
i , somme : ENTI ER
DEB UT
// Saisie des valeurs du tableau
POUR i ALLANT de 1 à 12 AU PAS DE 1
FAIRE
ECRIRE ( " Entrez la valeur ", i , " du tableau " )
tab [i] < - LIRE ()
FI NPOUR
// calcul d e l a s omme
somme< - tab[l]
POUR i ALLANT d e 2 à 12 AU PAS DE 1
FAI RE
somme< - somme + t ab [ i]
FINPOUR
FINPOU R
ECRIRE ( " La s omme du tableau .est : ", s omme )
FIN
Dans la réduction d'un tableau, il est déconseillé d'initialiser avec une valeur
par défaut la variable de la réduction lors de sa déclaration, sauf avec l'élément
neutre de l'opération de réduction. Prenons l'exemple de la somme que vous
calculez en tant qu'être humain. Quand vous lisez un tableau à sommes, vous
commencez par dire que la somme est égale au premier élément, puis vous lui
ajoutez le deuxième, puis le troisième ... jusqu'au dernier. Ce calcul est naturel
pour un être humain et vous ne vous rendez pas forcément compte de ses
étapes. La logique est la même pour la machine. Quelle que soit la réduction
que vous cherchez à faire (la somme, la moyenne, la plus petite valeur ... ),
cette réduction est toujours initialisée avec la valeur d'une case du tableau, et
généralement avec la valeur de la première case du tableau . Cela permet de
travailler uniquement avec des valeurs justes, i.e. contenues dans le tableau,
et donc ne pas exécuter une réduction fausse due à une mauvaise initialisa-
tion.
...
108---------Algorithmique
Techniques fon d amentales d e progra mmation
3.2.1 Parcours
Pour tout parcours de tableaux à n dimensions, il existe une règle simple à
retenir : une dimension = une structure itérative POUR. Deux dimensions
donnent un parcours avec deux POUR imbriqués, trois dimensions trois POUR
imbriqués, etc.
PROGRAMME Parcours - tableau - deux - dimensions
VAR
matrice : TABLEAU[l. .. 12 ] [ 1. . . 31 ] : REELS
i , j : ENTIER
DEBUT
// Saisie d es valeu rs de la matrice
POUR i ALLANT de 1 à 12 AU PAS DE 1
FAIRE
POUR j ALLANT de 1 à 31 AU PAS DE 1
FAIRE
ECRIRE ( " Entrez la valeur de la ligne ", i , "
et d e la case " , j , " du tableau " )
matrice [ i ] [ j ] <- LIRE ()
FINPOUR
FINPOUR
/ / Affichage des valeurs de la matrice J
1
POUR i ALLANT de 1 à 12 AU PAS DE 1
FAIRE
POUR j ALLANT de 1 à 31 AU PAS DE 1
FAIRE
ECRIRE (matrice [ i J [ j J )
FINPOUR
FIN POUR
FIN
3.2.2 Recherche
La recherche dans un tableau d'une dimension ou den dimensions repose sur
la même logique que celle pour un tableau à une dimension. Nous partons du
principe que la valeur n'est pas dans le tableau avec un "flag"de type booléen
à FAUX. Nous parcourons le tableau et si nous trouvons la valeur nous passons
le flag à VRAI . À la fin du parcours, il ne nous reste plus qu'à tester la valeur
du flag pour savoir si la valeur est présente ou non dans le tableau.
Les tableaux et structures _ _ _ _ _ _ _ _ _ __ 109
Chapitre 5
4. Structures et enregistrements
4.1 Structures
FIN STRUCTURE
Le s tableaux et structures _ _ _ __ __ _ __ _ 111
Chapitre 5
1 qu a ntité : ENTIER
FIN STRUCTURE
À la différence des autres types de variables, les variables de type ST RUC TURE
ne doivent pas initialiser une valeur unique mais toutes les valeurs de tous
leurs champs . Pour y accéder, nous utilisons l'opérateur "." qui permet de
manipuler les champs comme des variables simples.
Pour saisir un produit, il faut saisir son nom et sa quantité :
PROGRAMME saisie_ produit_liste_ cours e s
VAR
mon_produit : produ i t
DEBUT
ECR IRE ( " Entr ez l e nom du p r odu i t " )
mon_produit . nom <- LIRE ()
ECRIRE ( " Entre z la quantité du produit " )
mon_produ it . quantite < - LIRE ()
ECRIRE (mon_ produit . nom , " a vec un e quant i té de "
mon_produit . quantit e )
FIN
112---------Algorithmique
Techniques fondamentales de programmation
Les champs d'une structure peuvent être de n'importe quel type de donnée,
donc pourquoi pas de type STRUCTURE. Dans ce cas, la structure imbriquée
doit être déclarée avant la structure qui la contient (sinon elle ne sait pas
qu'elle existe) et nous devons toujours utiliser l'opérateur pour accéder
f i . fi
aux champs. Modélisons une personne avec sa date de naissance. Une date
étant composée de trois valeurs, nous la représentons donc avec une structure.
PROGRAMME Pers onne structure
STRUCTURE dat e
DEBUT
jour : ENTIER
moi s : ENTIE R
annee : ENT IER
FINSTRUCTURE
STRUCTURE perso nn e
DEBUT
prenom : CHAINE
nom : CHAINE
nai ssance : Date
FINSTRUCTURE
VAR
toto : personne
DEBUT
ECRIRE ( " Saisie de l ' iden t i t é d e tot o " )
ECRIRE( " Ent r er le nom de t o t o " )
pe rs onn e. nom< - LIRE ()
ECRIRE ( "E ntrer le pr é nom d e toto " )
personne . pre om <- LIRE ()
// Troi s saisies pour la dat e de naissance , car trois champs
ECRIRE ( " Entrer le jour de naissance de toto " )
t o to . naissance . jou r <- LIRE ()
ECRIRE ( " Entrer l e mois de n aissance de t o to " )
toto . naissance . mois< - LIRE ()
ECRIRE ( " Entrer l ' année de n aissa nce de toto " )
to t o . naissance . annee <- LI RE ()
ECRIRE (toto . nom , " ", toto . prenom , " est né le "
toto . naissance . jour ," / ", toto . na issa nc e . mois , " / ",
toto . nai ssan ce . jour )
FIN
Les tableaux et structures - - -- -- -- --113
Chapitre 5
Nous pouvons voir que la logique de manipulation des tableaux reste la même,
que les tableaux soient des variables ou des champs.
...
114---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
Le langage Python n'implémente pas cette structure, il utilise pour la
remplacer la programmation orientée ob]et dont nous ferons une introduction
au chapitre Commencer avec l'objet de cet ouvrage.
Une liste a également un autre avantage sur le tableau : elle est de taille
dynamique, nul besoin d'en déclarer la taille ! La gestion des indices se fait
également automatiquement. )
■ Remarque
Dans tous les langages de programmation, hors les implémentations du lan-
gages SOL comme par exemple TronsactSQL, nous commençons à compter
à partir de O. Le premier élément d'une liste est donc d 'indice O (à la position
0 de la liste) en Python.
116---------Algorithmique
Techniques fon d amentales de progra mmation
f o r co l i n l i n e
pri n t (col , e nd=" " )
1 p ri nt ( )
5.1.1 Parcours
En Python, il existe trois méthodes principales pour parcourir une liste :
- f or i n : parcours de chaque valeur de la liste.
- f o r r ang e : parcours de chaque indice de la liste.
- f o r enume rate : permet de récupérer à chaque tour l'élément et son
indice.
ma li ste= [ - 2 , 3 , 11 ]
f o r x in ma li s t e
p ri n t (x , e nd= " " ) # - 2 3 11
pri nt () # simpl e sa ut dè lig ne pour l ' af f ic h age
for i , x in e n u me r at e (ma_ l iste ) :
pr i nt ( " Ele me nt ", i , ": " , end =" " ) # Eleme n t O : - 2
El e me nt 1 : 3 Eleme n t 2 11
print ()
for i in ra ng e ( 3 ) : # 3 étan t la t a ill e d e li s t e
p r int (ma_l i s te[i ] , e nd= " " ) # - 2 3 11
p ri nt ()
Opérateur Résultat
X in l Teste si la valeur de x est dans la liste 1.
x not in l Teste si la valeur de x n'est pas dans la liste 1.
11 + 12 ou Concaténation de la liste 11 et 12.
11 . ex tend ( 12 )
l * n Concaténation de n copies de 1.
len (1) Longueur ou taille de la liste 1.
min (1) Plus petit élément de 1.
max(l) Plus grand élément de 1.
l.count(x) Nombre d'occurrences de la valeur de x dans 1.
l.index(x) Premier indice de la position de la valeur de x dans la
liste 1.
l . append(x) Ajout de x à la fin de la liste 1.
l .insert(i , x) Insertion à l'indice de valeur i la valeur de l'élément x
dans la liste 1.
l. clear () 1 devient une liste vide, sans élément.
l . remove(x) Suppression de la valeur de x dans la liste 1.
l. pop (i) Renvoie la valeur de l'élément d'indice i et la
supprime de la liste.
1. reverse () Inversion de la liste 1.
1 . sort () Trie la liste 1 par ordre ascendant.
■ Remarque
Les opérations min et max fonctionnement correctement quel que soit le type
des éléments de la liste cor tout type est transposable en type numérique.
Python peut donc comparer des entiers et des chaînes de caractères par
exemple.
118---------Algorithmique
Techniques fondamentales de progra mmation
5.1.3 Copie
En Python, lorsque nous affectons une liste avec une autre, les deux listes sont
liées : si nous changeons l'une des deux listes, nous changeons automatique-
ment l'autre liste.
ma_ lis t e = [ - 2 , 3 , 1 1 ]
ma_copie = ma_list
ma_ l iste . a ppend ( l )
print (ma_liste , " v s " ma_ copie ) # . [ - 2 , 3 , 11 , l ] VS [ - 2 , 3 , 11 , l]
ma copie . clear ()
1 print (ma_liste, " vs ", ma_ copie ) # [J vs [ J
Pour casser ce lien entre ces deux listes, il existe trois solutions :
- Utiliser la fonction copy .
- Utiliser la fonction list.
- Utiliser la fonction extend de la liste.
ma liste = [ - 2 , 3 , 11 ]
# fonction copy
ma_cop i e _separ ee = ma li ste . copy ()
# f onct i on list
ma _ deuxieme_ copie = list (ma_ li ste )
# Etendre une li ste vide a vec la liste à copier
ma_t r o isieme _ copi e = []
ma_troisi e me _ copie . extend (ma_ lis t e )
ma liste . a ppend ( l )
Les tableaux et structures _ _ _ _ _ _ _ _ _ __ 119
Chapitre 5
■ Remarque
En Python, l'affection d 'une liste ne crée pas un nouveau pointeur, les deux
listes seront en fait le même pointeur. Le chapitre Les fichiers détaillera cette
notion de pointeurs en détail pour mieux la comprendre.
La liste en intention est constituée des valeurs va le u r pour tous les éléments
x de la boucle for qui valident la condition du if .
Imaginons que vous vouliez créer une liste des dix premiers entiers positifs ou
nuls. Vous écririez le code suivant :
1 = [l
1 for i in range ( 1 0)
l . append (i)
:
Et pour finir, la liste des carrés des cinq premiers entiers pairs : \
5.2 Tuple
Un tuple peut être manipulé avec toutes les opérations des listes qui n'en
changent ni la taille, ni la valeur d'un ou de plusieurs de ses éléments .
Les tableaux et structures -----------121
Chapitre 5
5.3 Slicing
Opérateur Résultat
l [il Valeur de l'élément i de la liste 1
l [il = X Remplacement de la valeur de l'élément i de la liste 1
par la valeur de x
l [ i: j l Liste contenant les valeurs des éléments d'indice i
jusqu'à l'indice j exclus de la liste 1
l [i : j l = 12 Remplacement des élément s d'indice i jusqu'à l'indice
j exclus de la liste 1 par ceux de la liste 12
l [ i: j : kl Liste contenant les valeurs des éléments d'indice i
jusqu'à l'indice j exclus au pas de k de la liste 1
del ( 1 [il) Suppression dè l'élément d'indice i de la liste 1
del ( l [ i : j l ) Suppression des éléments d'indice i jusqu'à l'indice j
exclus de la liste 1
Notons que les indices i, j et k peuvent aussi bien être positifs que négatifs en
Python. Un exemple qui peut paraître complexe devient extrêmement
simple : inverser une liste sans l'opération reverse . Le slicing répond à ce défi
en une ligne :
1 ma_ li s t e = ma_li ste [ - 1 : :- 1 ]
1 print (ma_liste [ l : : 2 ])
pr i nt (ma_ liste[ : : 2])
# ( 3 , 2 , 11 ]
# ( - 2 , 11 , 0]
5.4 Dictionnaire
5.4.2 Opérations
Comme pour les listes, Python implémente une multitude d'opérateurs utiles
pour manipuler les dictionnaires dont voici les principales :
Opérateur Résultat
X in dico Teste si la clé x est dans le dictionnaire dico
X not in dico Teste si la clé x n'est pas dans le dictionnaire dico
len (dico ) Longueur ou taille du dictionnaire dico
dico[ x ] Retourne la valeur de la clé x. Si n'est pas une clé, alors
retourne une erreur
de l dico[ x ] Supprime la valeur de la clé x et la clé. Si n'est pas une
clé, alors retourne une erreur
d i co . cl e ar () Vide le dictionnaire dico
dico . keys ( ) Retourne la liste des clés du dictionnaire dico
dico . va l u e s() Retourne la liste des valeurs, san s le lien avec les clés,
du dictionnaire dico
d i co . items() Retourne le couple clé-valeur de chaque élément du
dictionnaire
... '
124---------Algorithmique
Techniques fondamentales de programmation
Afin de ne pas effacer une traduction, nous vérifions avant que le mot en
anglais n'existe pas dé jà en tant que clé.
5.4.3 Parcours
Le parcours d'un dictionnaire se fait avec une boucle for comme pour les
listes, mais nous itérons sur les clés et non les indices.
Pour ce faire, nous pouvons utiliser trois méthodes :
- Parcourir les clés avec for in .
- Parcourir les clés avec la fonction keys () .
- Parcourir les clés et les valeurs avec la fonction items () .
mon dico = {}
mon_dico[ ' computer ' ] = ' ordinateur '
mon_ dico[ ' mouse ' ] = ' souris '
mon_dico[ ' keyboard'] = ' clavie r '
# clé simple
for key in mon_dico :
print ( key , ":", mon_dico[key])
# avec l ' opération keys()
f or key i n mon_dico . keys () :
print ( ke y , ": ", mon_ dico [key ])
#avec l ' opé rat i on items ()
for key , value in mon_dico.it e ms()
print (ke y , ": ", value)
Les tableaux et structures _ _ _ _ _ _ _ _ _ __ 125
Chapitre 5
6. Exercices
6.1 Exercice 1
6.2 Exercice 2
6.3 Exercice 3
6.4 Exercice 4
6.5 Exercice 5
Écrivez un algorithme qui réalise l'inversion des éléments d'un tableau sans
utiliser de tableau intermédiaire. Codez le script Python correspondant.
6.6 Exercice 6
6.7 Exercice 7
6.8 Exercice 8
6. 9 Exercice 9
6.10 Exercice 10
/
------------129
Chapitre 6
Les sous-programmes
1. Procédures et fonctions
Vous êtes encore en train d'apprendre à modéliser votre pensée en informa-
tique avec des problèmes assez simples et dans ce chapitre vous allez aller un
plus loin dans votre réflexion. Imaginez un programme comme un logiciel de
vidéo à la demande ou encore un client de messagerie? Ne pensez-vous pas
que ces programmes contiennent · des millions, voire des milliards
d'instructions ? Comment donc se retrouver facilement dans cette nuée
d'instructions ?
Une première réponse est assez simple: découpez votre logique en petites
parties qui seront appelées à la demande. Cette découpe permet de fortement
réduire la complexité du programme en se focalisant uniquement sur des sous-
problèmes plus simples à résoudre. Ces parties sont les sous-programmes
qui seront appelés dans le programme principal, le point d'accès de l'appli-
cation, comme le représente la figure suivante.
130---------Algorithmique
Techniques fondamentales de programmation
DEBUT
FIN
PROG RAMME principal
VAR
DEBUT
sous_prog_A
F IN
1.1.1 Paramètres
Les paramètres sont des variables dédiées à la procédure . Selon le type de
paramètre, la procédure peut récupérer des valeurs de l'algorithme principal
et/ ou lui en envoyer: ~
Pour qu 'une variable soit utilisable par tous les sous-programmes et le pro-
gramme, il faut qu 'elle soit déclarée comme globale, c'est-à-dire en premier
dans notre algorithme :
VAR ... //déclaration des var i ables globales
SOUS - PROGRAMME so u s_pr og_ A
VAR
// déclaration d es variables locales à sous _ prog_A
DEB UT
FIN
PROGRAMME principal
VAR
// déclaration des variab l es l ocales à principa l
DEBUT
sous_prog_ A
FIN
1.1.2 Déclaration
Une procédure est un algorithme, coml?e ceux que nous,~ ons vus précédem-
ment, identifié par un nom unique. A la différence des algorithmes, nous
définissons également ses paramètres :
PROCEDURE nom (E var l : t ypel , S var2 type2 ,
E/S var3 : typ e3 )
VAR
// variables l ocal es à la procédure
DEBUT
Il instructions de la procédure
FIN
la + 2 * lo
134---------Algorithmique
Techniques fondamentales de programmation
1
n <- n *2
FIN
1 ECRIRE (mot )
F IN
Cette procédure est assez simple, elle prend en paramètre le mo,5,à afficher, qui
est donc une entrée car il est en lecture seule, et l'affiche à l'utilisateur.
Augmentons un peu la complexité des procédures de notre pendu . L'étape
"Traitement du mot masqué et du nombre d'essais" demande à récupérer la
lettre de l'utilisateur et le mot masqué actuel. La lettre est donc une entrée,
comme le mot en clair, et le mot initial et le nombre d'essais restent des
entrées/ sorties car la procédure en récupère les valeurs pour les modifier par la
suite, tout en calculant le nombre d'essais qu'il reste à l'utilisateur. Voici la
procédure correspondante :
PROCEDURE ca l cul_masqu ag e (E/ S : mot : CHAINE , E/S : essai
ENT I ER , E : lettre : CARACTERE , E : mot c l a i r : CHAINE)
VAR i : ENTIER
tmp : CHAI NE
trouve : BOOLEEN
DEBUT
i <- 1
tmp <-
trouve< - FAUX
POU R i ALLANT de 1 à LONGUE UR (mo t c l a i r ) AU PAS DE 1
Les sous-programmes _____________ 135
Chapitre 6
FAIRE
SI EXTRAIRE (mo t , i , 1 ) = lettre
ALORS
CONCATENER(tmp , lettr e )
trouve< - VRAI
SINON
CONCATENER (tmp , EXTRAIRE(mot , i , l))
FINSI
FINPOUR
SI trouve FAUX
ALORS
essai< - essai - 1
FINSI
mot< - tmp
FIN
1.1.3 Appel
Les procédures seules ne servent pas à grand-chose, il faut qu'elles soient utili-
sées pour gagner en intérêt . Une procédure est tout simp_lement appelée avec
une instruction représentant son nom et ses paramèt res entre pàrenthèses
dans l'ordre dans lequel ils sont déclarés, comme la montre la figure ci-dessous.
Les paramètres peuvent être, lors de l'appel, des variables déclarées ou des
valeurs fixes .
'
a< - 5
b <- 9
rectangle (a, b , perimetre, aire ) I l appel avec variables
ECRIRE ( "périmétre : ", perimetre , " aire : ", aire )
FIN
FIN
VAR i : ENTIER
tmp : CHAINE
trouve : BOOLEEN
DEB UT
i <- 1
tmp <- 1111
trouve< - FAUX
POUR i AL LANT de 1 à LONG UEUR (mot c l air ) AU PAS DE 1
FAIRE
SI EXTRAIRE (mo t , i , 1) = lett r e
ALORS
CONCATENER (tmp , lettre )
trouve< - VRA I
SHJON
CONCATENER(tmp , EXTRAIRE(mot , i , l) )
FINSI
FINPOUR
SI trouve FAUX
ALORS
essai< - essai - 1
FINSI
mot< - tmp FIN
PROGRAMME pendu
VAR mot , masque : CHAINE
fin_partie : BOOLEEN
essai : ENTI ER
DEBUT
fin_partie <- FAUX
essai< - 7
Avec ces appels, nous remarquons que les noms des variables et le nom des
paramètres ne sont pas forcément les mêmes. Ici, l'important est la valeur et
le type des données envoyées et non l'identifiant car il est local au programme.
1 3 8 - - - - - - - -- Algorithmique
Techniques fondamentales de programmation
1.2.1 Déclaration
La déclaration d'une fonction est plus simple que celle d'une procédure : les
paramètres étant uniquement en entrée, nous n 'avons pas besoin de spécifier
qu 'ils sont entrés avec E. Une fonction se déclare par son nom, ses paramètres
et son type de retour :
FONCTION ma fonct i on( a , b TYPE , c , d TY PE ) type re tour
VAR
1
Les sous-programmes _ _ _ _ __ _ __ _ __ _ 139
Chapitre 6
DEBUT
1 FIN
RETOURNER ( . . . )
typere tour indique le type de la valeur retournée par la fonction. Cette va-
leur est renvoyée au programme appelant avec 1'instruction RET OURNER () .
Créons notre première fonction simple qui va renvoyer le plus grand de deux
f• entiers passés en paramètres :
FONCTION ma ximum( a , b : ENTIER ) : ENTIER
DEBUT
SI (a > b)
ALORS
RETOURNER(a)
SINON
RETOURNER (b )
FINSI
FIN
Cette fonction compare les valeurs des paramètres de type entier a et b et re- (
tourne la valeur la plus grande.
Continuons notre jeu du pendu en modélisant les trois étapes suivantes par
des fonctions :
- Saisie du mot à deviner : une fonction sans paramètre qui renvoie le mot à
deviner.
- Saisie de la lettre de l'utilisateur : une fonction sans paramètre qui retourne
la lettre saisie par l'utilisateur.
- Tester si le mot a été deviné par l'utilisateur : une fonction qui renvoie un
booléen qui indique si le joueur a trouvé le mot ou non.
■ Remarque
Un sous-programme n'est pas obligé d 'avoir des paramètres. Dons ce cos,
nous utiliserons une poire de parenthèses vide lors de la déclaration et l'appe l
pour no tifier ce cos.
140---------Algorithmique
Techniques fondamenta les de progra mmation
1.2.2 Appel
On appelle une fonction en précisant son nom et, entre parenthèses, les va-
leurs que l'on souhaite attribuer aux paramètres dans l'ordre dans lequel ils
sont déclarés, comme pour les procédures. Lors de son appel, à la différence
d'une procédure, le retour d'une fonction doit être utilisé, en étant stocké dans
une variable par exemple :
,.. FONCTION maximun (a , b ENTIER ) ENTIER
DEB UT
SI (a > b )
ALORS
RETOURNER (a )
SINON
RETOURNER (b)
FINSI
FIN
PROGRAMME calcul_max.imum
VAR a , b , max : ENTIER
DEBUT
ECRIRE ( " Entrez votre premier entier " )
a <- LIRE ()
ECRIRE ( " Entrez votre second entier " )
b <- LIRE ()
max< - max imun(a , b )
ECRIRE ( " Le max imum est " ma x ) 1
FIN \
Complétons notre programme principal du pendu avec l'appel de nos
fonctions :
PROGRAMME pendu
VAR mot , masque : CHAINE
lettre : CARACTERE
fin_partie , mot_de vine BOOLEEN
essai : ENTIER
DEBUT
fin _p artie <- FAUX
es s a i <- 7
mot< - saisie_mot ()
TANT QUE NON fin_partie
FAIRE
afficher_ mot_masque (masque )
lettre< - saisie_ lettre ()
142---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
En pratique, hormis les implémentations du langage SQL, comme par
exemple TransactSQL et quelques langages spécifiques, les langages de
programmation actuels n'utilisent plus de procédures mais uniquement des
fonctions, même si d 'un point de vue d'algorithmie ce sont des procédures.
Nous verrons plus en détail cette remarque dans la mise en pratique a vec
Python plus loin dans la section dédiée.
2. L'élégance de la récursivité
Par définition, un sous-programme récursif est un sous-programme qui
s'appelle lui-même .
L'objectif de la récursivité est de simplifier, en théorie, un traitement complexe
contenant des itérations, en écrivant uniquement des traitements simples.
Cependant, il existe tou jours un fossé entre la théorie et la pratique.
Regardons un peu l'évolution des langages de programmation avec beaucoup
de vulgarisation . Les premiers langages de programmation, et encore certains
exotiques de nos jours, n'implémentaient pas les structures itératives, seule-
ment les conditionnelles. Comment faire alors pour répéter une instruction ?
Les sous-programmes _ _ _ _ _ _ _ __ _ _ _ 143
Chapitre 6
DEBUT
SI condition arrê t
ALORS
// arr ê t des appels récursifs
SINON
144---------Algorithmique 7
Techniques fondamentales de programmation
1 FIN
FINSI
Prenons le cas simple d'une fonction qui calcule la somme des n premiers en-
tiers. Pourquoi partir sur une fonction relative aux mathématiques ? Tout
simplement car l'explication de l'enchaînement des appels est simplifiée avec
les formules commençant notamment par le symbole somme CE).
Commençons par écrire la fonction non récursive:
FONCTION somme_ premi e r s entiers (n : ENTIER ) ENTIER
VAR i , somme : ENTIER
DEBUT
POUR i ALLANT DE 1 à n AU PAS DE 1
FAIRE
somme< - somme+ i
FINPOUR
RETOURNER (somme )
FIN
PROGRAMME calcul somme
VAR s : ETIER
DEBUT
s <- somme_premiers enti e rs ( 4 )
ECRIRE ( " La somme des 4 premiers · e n tiers est s)
FIN
■ Remarq u e
Rappel de la règle de la récursivité : toute instruction itérative incluse dons une
fonction peut se foire en récursif avec une instruction conditionnelle.
L'enchaînement des appels de cette fonction est décrite dans la figure ci-après
pour aider le lecteur à en visualiser l'élégance.
Renvoie 1 + t
+ 3 + 4 = 10
Premier appel - - - - - - . .
Somme(3) ~
----.----- Renvoie 1 + 2
-----
Deuxième appel
Somme(2) ~--"'envoie l
Troisième appel
----....
Somme(l)
1 4 6 - - - - - -- --Algorithmique
Techniques fondamentales de programmation
À la lecture, cette fonction récursive est bien plus naturelle pour les humains
que la première, la difficulté étant son écriture.
Passons aux procédures récursives où la logique est légèrement différente.
Regardons la fonction récursive pour parcourir un tableau :
PROCEDURE parcou rs_rec u rsif (E : taille , compteur : ENTI ER, E :
tab : TABLEAU [ ] : ENTIER ) : ENTIER
DEBUT
SI compteur = taille
ALORS
ECRIRE ( tab [comp te ur])
SINON
ECRIRE (t ab [comp teur ])
parcours_recursif (ta i ll e , compteur+ 1 , tab )
FINSI
FIN
Re,nvoie\ + 2::: 3
ir----...aJa:ppe~ - - - - - - - - ~
Fibo(l)
~~-- ! Fibo(2) ----,Renvoie 1
l
Fibo(l )
Il est bien sûr tout à fait possible de calculer cette suite de manière non
récursive :
FONCTION f ibo(n : ENTIER ) ENTIER
VAR i , pre , sui , resultat ENTIER
DEBUT
SI n = 0
ALORS
resultat <- 0
SINON
SI n = 1
ALORS
res ultat <- 1
SINON
pre <- 0
s ui< - 1
POUR i ALLANT de 2 An AU PAS DE 1
FAIRE
k <- pre + sui
pre <- sui
s u i <- k
Les sous-programmes _ _ _ _ _ _ _ _ _ _ __ 149
Chapitre 6
FINPOUR
FI NSI
FINSI
RETOURNER ( resultat )
FIN
PROGRAMME calcul fibo
VAR f : ENTIER
DEBUT
f < - fibo ( 4 )
ECRIRE ( " La suite de Fibonacci de 4 vau t : ", f )
FIN
Nous remarquons facilement que la fonction récursive est plus simple à lire
que la fonction non récursive.
Elle est également plus simple, ou logique, à écrire car elle demande moins de
réflexion : nous appliquons la définition telle quelle.
Nous pouvons alors nous poser la question : quand devons-nous utiliser des
itérations et quand devons-nous utiliser la récursivité?
r-
Il va de soi que chaque structure itérative ne doit pas être remplacée par un
sous-programme récursif, sinon pourquoi avoir ajouté les itérations aux lan-
gages de programmation ? -
Malgré son élégance, la récursivité peut être dangereuse : si la condition d'arrêt
est mal déterminée, alors le programme bouclera à l'infini et ne se terminera
jamais. De plus, les appels récursifs peuvent également saturer la mémoire de
l'ordinateur dans certains cas, donc planter l'exécution du programme par
débordement de la mémoire.
Nous pouvons toujours transformer un sous-programme récursif en un sous-
programme non récursif mais certains peuvent s'avérer extrêmement
corn pliqués.
l 'exemple classique pour illustrer ce propos est le jeu du démineur. lorsque
l'utilisateur clique sur une case non minée et dont les voisines ne sont pas
minées, la découverte des cases voisines se propagent jusqu'à atteindre une
case voisine d'une mine ou le bord du plateau .
150---------Algorithmique
Techniques fondamentales de programmation
En non récursif, il nous faudrait écrire des structures conditionnelles qui per-
mettent de naviguer dans les huit sens sur la matrice représentant le plateau
de jeu et s'arrêter uniquement lorsque nous atteignons_une case voisine d'une
mine sans dépasser de la matrice et ce, sans oublier toutes les autres cases
voisines à dévoiler. Une imbrication extrêmement complexe de structures
itératives et conditionnelles ...
En récursif, la logique est bien plus naturelle : il nous suffit de définir un sous-
programme "dévoiler" qui s'appellera sur les huit cases voisines lorsqu'il est
appelé sur une case sans mine et non voisine d'une mine . Ainsi la propagation
du dévoilement des cases à dévoiler se fait naturellement sans réfléchir aux
cases que nous traitons sur la matrice. La gestion des bords du plateau se fait
dans ses sous-programmes en faisant partie de la condition d'arrêt.
Nous étudierons ce jeu plus en détail et de manière pratique dans les exercices
de ce chapitre. Nous verrons également au chapitre Les fichiers que la mani-
pulation des structures complexes de données est plus facile en récursif.
En attendant revenons aux tableaux.
Lorsque nous trions un tableau, nous sommes sûrs de devoir échanger des
valeurs assez fréquemment. Nous allons définir une procédure pour effectuer
cette opération afin de la réutiliser dans les algorithmes de tri qui suivent.
PROCE DURE echanger (E/ S : x, y : ENT IE R)
VAR
tmp : ENT I ER
DEBUT
t mp <- X
X<- y
y< - t mp
FIN
Le tri par sélection est le tri ayant la logique la plus simple. Nous commençons
par chercher la plus petite valeur du tableau et nous la plaçons à la première
case en décalant les autres cases, comme le montre la figure ci-après. Il ne nous
reste plus qu'à appliquer les mêmes opérations sur le sous-tableau commen-
çant à la case 2, puis celui commençant à la case 3, etc. jusqu'à arriver à un der-
nier sous-tableau de taille 1, ce qui indique que le tableau est bien trié. \
... .
152 Algorithmique
Techniques fondamentales de programmation
...
3 4 9 10 4 On la permute avec la deuxième valeur
1
Indice< - i
FIN~~~!I
RETOURNER ( indic e )
1 FIN
Nous n 'avons plus qu 'à définir l'échange entre la première case et la plus petite
valeur pour chaque sous-tableau :
PROCEDURE tri - selection (E/ S : tab : TABLEAU[] : ENTIER , E :
taille : ENTIER )
VAR
i : ENTIER
DEBUT
POUR i ALLANT DE 1 à (tail l e - 1 ) AU PAS DE l
FAIRE
echanger (t ab [i] , tab[indice - min i mum (tab ,i, taille ))
FI NPOUR
FIN
154---------Algorithmique
Techniques fondamentales de programmation
3 4 9 4 10
1 1 1 1
3 4 9 4 10
1 1 1 1
3 4 9 4 10
1 1 1 1 ,::,
~
Ill
3 4 4 9 10 !!
1 1 1 1 ~
,:
·~
3 4 4 9 10 Notre tableau est trié !
1 1 1 1 ~
~
Tri à bulles "'C:
._g
:fi
@
Les sous-programmes _ _ _ _ _ _ _ _ _ _ _ _ 155
Chapitre 6
Ayant déjà la procédure pour échanger deux valeurs, donc pour permuter les
deux éléments de la bulle, il ne nous reste qu'à écrire la procédure correspon-
dant au tri à bulles.
PROCEDURE tr i - bulles (E/S : tab : TABLEAU [ ] : ENTIER ,
E : taille : ENTIER )
VAR
fini : BOOLEE N
i : ENTIER
DEBUT
REPETER
fini< - VRAI
POUR i ALLANT DE 1 à (taille - 1) AU PAS DE 1
FAIRE
SI ( tab [ i ] > tab [ i + 1 J )
ALORS
echanger(tab[i ] , t ab [ i+ l])
fini< - FAUX
FINSI
FINPOUR
JUSQUA (fini )
FI
156---------Algorithmique
Techniques fondamentales de programmation
4 9 3 10 4
1 1 On compare les cases 2 et 3
3 est plus petit que 9 : on le décale
4 3 9 10 4
4 3 9 10 4
1 On compare les cases 1 et 2
3 est plus petit que 4 : on le décale
3 4 9 10 4
1 1
3 4 9 4 10
1 1 1
<- t ab [j]
t ab [j + l]
<- j - 1
j
FINTANTQUE
t ab [j + l] <- t mp
FINPOU R
FIN
Le premier sous-tableau étant composé d'une seule case, il est dé jà trié. Nous
commençons notre structure itérative avec un compteur commençant à 2.
Pour chaque sous-tableau à traiter, nous le parcourons du dernier élément au
premier en décalant les plus petites valeurs à la case précédente au besoin.
1 4 10 3 9 4
3 1 4 4 9 1 10
Tri rapide
Il va par la suite répéter le choix du pivot et le placement des éléments pour la
partie avant le premier pivot et la partie après le premier pivot . Il s'arrête
lorsqu'il n'y a plus d'éléments à gauche et à droite du pivot courant.
Avec cette description, nous nous rendons rapidement compte que ce tri uti-
lise la récursivité en se rappelant sur les deux parties du tableau à traiter sépa-
rées par la case pivot.
.
158---------Algorithmique
Techniques fondamentales d e program ma tion
F IN
Le tri par fusion est le tri le plus rapide en informatique . Il scinde le tableau à
trier en deux sous tableaux de même taille, à un élément près si sa t aille est
impaire. Il effectue cette séparation jusqu'à n'avoir que des tableaux d'une
case . Ensuite, il va regrouper les cases des tableaux intermédiaires en
rangeant les valeurs dans l'ordre comme le montre la figu re ci-dessous :
1 9 1 3 10 1 4 1
10
Tri fusion
Nous voyons également avec ce tri qu'il possède un raisonnement récursif
semblable à celui du tri rapide .
160---------Algorithmique
Techniques fondamentales de programmation
FINSI
FIN
PROCEDURE triFusion (E/S : tab TABLEAU[] ENTIER , E taille )
DEBUT
triFusion(tab , 1 , taille)
FIN
■ Remarque
De nos jours, le lecteur n'a plus à apprendre par cœur comment implémenter
les algorithmes de tri cor ils sont implémentés ou sein des langages de pro-
grammation. Cependant, comprendre et être capable de reproduire per-
mettra ou lecteur d'avoir un meilleur niveau en programmation cor vous aurez
acquis un niveau d 'abstraction vous permettant de comprendre le fonction-
nement du langage avec lequel vous codez.
■ Remarque
Lo fonction sort de Python implémente un tri hybride mélangeant le tri par
fusion et le tri par insertion, appelé le Timsort. Nous vous laissons étudier ce tri
par vous-même maintenant que vous avez les bases sur les deux tris utilisés.
Maintenant que nous pouvons trier nos tableaux, nous pouvons optimiser la
recherche d'une valeur dans ces derniers.
Pour ce faire, nous pouvons utiliser une recherche dichotomique, comme
illustrée dans la figure suivante.
On recherche si 30 est dans le tableau
3 1 4 1 4 6 7 1 8 22 30 42 50
3 1 4 1 4 6 1 7 8 22 30 42 50
3 1 4 1 4 6 7 1 8 22 30 42 50
Recherche dichotomique
1 6 2 - - - - -- - - -Algorithmique
Techniques fondamentales de programmation
1
Le principe d'une telle recherche est assez simple. Nous commençons par
regarder la valeur de la case se trouvant au milieu du tableau. Dans le meilleur
des cas, il s'agit de la valeur recherchée. Si ce n'est pas _le cas, si elle est plus
grande que la valeur recherchée, nous regardons alors dans la première moitié
du tableau. Si elle est plus petite, nous regardons dans la seconde moitié du
tableau Nous répétons ces opérations jusqu 'à trouver la valeur. Dans le cas où
la valeur recherchée n'est pas dans le tableau, notre dernière moitié de tableau
sera composée d'une seule case qui ne sera pas la valeur recherchée.
En algorithme, la séparation du tableau en deux parties se base sur la valeur de
plusieurs compteurs : un pour l'indice de départ, un pour l'indice de fin et un
pour l'indice du milieu . Nous allons changer la valeur de ces compteurs pour
indiquer dans quelle moitÎ.é rechercher la valeur demandée.
PROGRAMME Recherche_dichotomique
VAR
tab : TABLEAO[ l ...1 0 ] : ENTIER
debut , milieu fin , valeur : ENTIER
tr ouve< - FAOX : BOOLEEN
DEBUT
Il initialisation et tri du tableau déjà effectués
ECRIRE ( " En t rer la valeur à recherc h er " )
val <- LIRE ()
debut <- 1
1
fin< - 10 Il l a taille du tableau
TANTQOE debut <= fin ET NON trouve
FAIRE
milieu< - (deb ut + f in DIV 2
SI tab[milieu ] = val
ALORS
trouve< - VRAI
SINON
SI tab[milieu ] < v al
Il on recherche donc dans la première moitié
ALORS
fin< - milieu - 1
SINON
Il ou dan s la deux ième moit ié
debut <- milieu+ 1
FINSI
FINSI
FINTANTQOE
Les sous-programmes _ _ _ _ _ _ _ _ _ _ _ _ 163
Chapitre 6
SI trouve
ALORS
ECR I RE( " la val eur est pr é sente dans le tableau)
SINON
ECRIRE ( " le tabl ea u ne contient pas la valeur demandée " )
FINSI
FIN
■ Remarq ue
Vous pouvez remarquer que nous avons juste testé la valeur des variables de
type booléen dans nos conditions. Cela re vient au même que de faire une
comparaison booléenne.
# programme principal
if name == ' main
afficheTableau ( [ 1 , 2 , 3 ])
a = 2
aa = double ( 2 ) .,
print ( " le doub le de ", a , " est ", aa )
print ( " le maximun est ", maximum (2 , 3 ))
Ce code reprend les procédures et fonctions définies dans les sections précé-
dentes. Nous pouvons remarquer plusieurs différences entre l'algorithmie et le
Python:
- Le type de retour n'est pas déclaré car Python est un langage typé dynami-
quement.
- L'instruction RETOURNER est remplacée par l'instruction return.
- Une procédure sans sortie est une fonction sans return.
- Une fonction retournant une valeur peut être directement appelée dans une
instruction print .
- Nul besoin de passer la taille d'un tableau lorsque ce dernier est passé en
paramètre.
Les sous-programmes _ _ _ _ _ _ _ _ _ _ _ __ 165
Cha pitre 6
Retour multiple
■ Remarque
Attention à ne mettre pas les retours multiples entre parenthèses pour une
question d'esthétisme, cela reviendrait à faire un retour simple d 'un tuple et
non de plusieurs valeurs.
Lors de l'appel d'une fonction avec retour multiple, nous récupérons plusieurs
valeurs. Il nous faudra donc énumérer ses valeurs avant l'affectation en les
séparant par des virgules.
# la procédure de calculs sur un r ec tangle
de f calculRectangle (la , lo ) :
aire= la* lo
perimetre =la* 2 + l o * 2
return aire , per i metre
if name ma i n '·
la= 2
lo = 4
aire, perimetre = ca l culRectangle ( la , lo )
print ( " l ' aire d u rectangle est ", aire )
print ( " le périmtère du rectangle est ", perimetre )
■ Remarque
Attention à l'ordre des valeurs du retour qui doit être respecté lors de
l'affectation avec l'appel de la fonction.
...
1 6 6 - - - - - - - - - A l gorithmiq ue Î
Python permet de donner une valeur par défaut aux paramètres en les affec-
tant lors de la déclaration de la fonction.
# maximun entre trois valeurs
def maximum3 (a = 0 , b=l , c=3 ) :
if a> b and a> c :
return a
elif b > c :
.,
return b
else:
return c
if name ma i n
print ( " appel avec les valeurs par défaut ", ma x imum3 ())
print ( " appel sans les valeurs par défaut ", maximum3 (1 , 2 , 3 ))
print ( " appel avec quelques valeurs par défaut ", maximum3 ( 3 , 4 ))
# a vaut 3 , b 4 etc 3
print ( " appel avec quelques valeurs par défaut ", maximum3 ( 4 ))
# a vaut 0 , b 4 etc 3
print ( " appe l avec quelques valeurs par défaut ",
ma xi mum3 (b = 3 , c = 4) ) # a vaut 0 , b 3 etc 4 .
Nous pouvons tout à fait appeler la fonction maximum3 définie précédem-
ment sans paramètre, avec certains paramètres ou avec tous les paramètres.
Lors d'un appel sans paramètre, ce sont uniquement les valeurs par défaut qui
seront affectées à tous les paramètres .
Lorsque nous appelons la fonction avec autant de valeurs que de paramètres,
aucune valeur par défaut n'est utilisée.
Si nous sommes dans l'obligation d'utiliser la valeur par défaut d'un paramètre
autre que le dernier (ou les derniers), nous devons impérativement nommer le
ou les paramètres qui n 'utilisent pas les valeurs par défaut comme le montre
l'extrait de code précédent. Sans cela, Python ne saura pas à quel paramètre
affecter les valeurs .
Les sous-programmes _ _ _ _ _ _ _ _ _ _ _ _ 167
Chapitre 6
La mbda expression
1 doub l e= l ambda a : a* 2
print ( " l e double d e 2 est ", do uble (2 ))
Les fonctions lambda doivent être uniquement utilisées pour des calculs très
simples d'une seule instruction afin de ne pas en surcharger la lecture et donc
la compréhension.
5. Exercices
5.1 Exercice 1
5.2 Exercice 2
168---------Algorithmique
Techniques fondamentales de programmation
5.3 Exercice 3
5.4 Exercice 4
5.5 Exercice 5
5.6 Exercice 6
Écrivez un algorithme qui donne le nombre de chiffres d'un entier entré par
l'utilisateur. Codez le script Python correspondant .
5.7 Exercice 7
5.8 Exercice 8
5.9 Exercice 9
5.10 Exercice 10
5.11 Exercice 11
Chapitre 7
Passons en mode confirmé
Instruction
Instruction
1nstruction
Instruction
Instruction
... .
produit.quantile <- fraises
produit.quantite <- 0
Instruction
1nstruction
Instruction
Instruction
Pile
Pour économiser les cases de la pile et poUvoir retrouver des éléments précis,
nous avons la possibilité de stocker des instructions dans le tas (ou heap en
anglais ), une autre zone mémoire dédiée pour l'exécution d'un programme .
Le tas est utilisé pour les allocations de mémoire dynamique : n'importe quel
bloc de données peut êt re alloué ou désalloué n 'importe quand. Sa gestion est
donc plus complexe mais elle permet de stocker nos struct ures com plexes de
données proprement.
Passons en mode confirmé _ _ _ _ _ __ _ __ 173
Chapitre 7
Pour stocker des valeurs dans le tas, il nous faut utiliser un pointeur, comme
le montre la figure ci-dessous et ainsi n'occuper qu'une case de la pile.
Instruction
Instruction
Instructi on produit
norn<-fraises
Instructi on
quantité<- O
Instructi on
Instruction
POI NTEUR
Instruction
Instruction
Instruction
Instruction
Pile Tas
1
VA R
*mon_p o i nt e u r_e n tier : ENT I ~R
174-- - - - - - - -Algorithmique
Techniques fondamen tales de progra mmatio n
Pour récupérer une valeur simple pointée, nous devons utiliser l'opérateur *.
■ R e marque
La plupart des langages de programmation implémentant ces structures
complexes, le lecteur a tout avantage à en connaître le fonctionnement afin
de mieux comprendre ce qui est codé au sein du langage, donc de mieux
programmer et de programmer de manière plus efficiente.
Les premières listes sont les listes simplement chaînées. Ce type de liste ne
peut être lu qu'à partir du premier maillon jusqu'au dernier.
Contrairement aux tableaux, quel que soit le type de la liste, l'opérateur d'in-
dexation [ J n'existe pas . L'accès à une liste est uniquement séquentiel :
chaque maillon permet d'aller au suivant, toujours en commençant par le pre-
mier.
.. .
1 7 6 - - - - - -- --Algorithmique
Techniques fondamentales de programmation 1
2.1.1 Création
Pour créer une liste simplement chaînée, nous devons d'abord représenter ce
qu 'est un maillon. Pour ce faire, nous allons utiliser une STRUCTURE
contenant deux champs, représentée dans la figure ci-dessous :
- La valeur de la donnée.
- Le pointeur vers le maillon suivant .
Maillon 1 Maillon 2 Maillon 3 Maillon 4
~~I Valeur I ~I
Suivant Valeur I
Suivant ~ NULL
Tout comme les tableaux, les listes ne peuvent contenir que des valeurs de
même type comme le montre la STRUC TURE ma i l l o n . Nous partons du
principe que chaque maillon créé sera le dernier, d'où l'initialisation du
pointeur suivant à NU L L, c'est-à-dire le dernier élément de la liste.
Grâce à la STRUCTURE maill o n, nous pouvons maintenant définir la
STRUCTURE l i ste, représentée sur la figure vue précédemment:
STRUCTURE li s t e
DEBUT
taill e : ENTIER
*p r emie r <- NULL ma illon
"~
~
1 FINSTRUCTURE !:!
~
-<::
-~
PROG RAMM E Declaration liste sic
VAR z:
lu
Ma list e : l i ste V,
c::
DEBUT .,e
1 FIN ~
@
Passons en mode confirmé ----------177
Chapitre 7
En plus de contenir son premier maillon, une liste possède également une
taille, c'est-à-dire le nombre de maillons . Cela nous permettra de la manipuler
plus facilement par la suite.
Toute la difficulté des listes réside dans la bonne gestion des pointeurs repré-
sentant le lien entre leurs maillons.
2.1 .2 Parcours
Pour manipuler une liste, il nous faut définir le type manipulé par les maillons
de cette liste dans la S TRU CT URE maillon. Nous choisissons de travailler
sur des entiers pour illustrer toutes les manipulations des listes simplement
chaînées.
Dans cette section, nous demandons au lecteur de considérer une liste
d'entiers déjà initialisée, car nous ne nous préoccupons que de son parcours.
Le principe du parcours d'une liste est le suivant : tant que le maillon courant
n'est pas à NULL, nous affichons sa valeur et nous allons au maillon suivant.
Nous commençons bien sûr par le premier maillon, le seul accès aux éléments
de la liste.
PROGRAMM E Parcours - li s t e - entier
STRUCTURE ma il lon e n ti e r
DE BUT
valeur : ENT IER
*suivant< - NUL L maillon entier
FINSTRUCTURE
VAR
ma lis t e : l iste ent i er
*mail lon cou ra nt< - NULL : maillon entier
DEBUT
mai l lon_courant <- ma_li ste . premier
// Le derni e r ma ill on point e sur NULL
TANTQUE ma il lon courant # NULL
4.
178---------Algorithmique
Techniques fondamentales de programmation
FAIRE
ECRIRE ( " Va l e ur . " maillon courant - >valeur )
maillon courant< - ma ill on cou r ant - >suivant
1 FIN
FINTANTQUE
Valeur Suivant
Maillon 1 Maillon 2 Maillon 3
Maillon ajouié
Valeur Suivant
Maillon 1 Maillon 2 Maillon 3 Maillon 4
r
Maillen à ajouter
r
Ma.i!lon ajouté
Pour ajouter au début, nous créons un nouveau pointeur de maillon qui prend
comme suivant les éléments de la liste avec une affectation au premier
élément de la liste . Il nous suffit ensuite de remplacer le premier maillon de la
liste par ce nouveau maillon.
Pour ajouter à la fin, nous devons parcourir la liste jusqu'au dernier élément et
le faire pointer sur le nouveau maillon et non plus NULL. Par défaut, le
pointeur suivant du maillon inséré a comme valeur NULL, il est donc le dernier
élément de la liste.
Dans tous les cas, nous devons augmenter la taille de la liste de 1.
Pour insérer des valeurs dans la liste, il nous suffit simplement d'appeler l'une
ou l'autre des procédures d'a jout selon nos besoins.
Liste.premier
Valeur
lI ~I I ~I
Suivant
Maillon 2
Valeur Suivant
Maillon 3
Valeur I
Suivant r--►I
Maillon 4
Valeur I
Suivant ~ NULL
Liste.premier
Liste.premier
1 I ~I I
Valeur Suivant Valeur Suivant ~ Valeur Suivant 1 Valeur I Suivant ~ NULL
NULL
NULL
VAR
ma liste : liste entier
nouvelle_valeur , i : ENTIER
*maillon courant< - NULL : maillon entier
ok : BOOLEEN
DEBUT
Il Création de la liste
POUR i ALLANT DE 1 A 5 AU PAS DE 1
FAIRE
ECRIRE ( " Entrez la valeur ", i )
valeur< - LIRE ()
ajout debut (ma liste , valeur )
FI NPOUR
POUR i ALLANT DE 1 A 5 AU PAS DE 1
FAIRE
ECRIRE ( " Ent r e z la valeur " , i )
valeur< - LIR E ()
ajout fin (ma liste , valeur)
FINPOUR
Il Affichons notre liste en supposant q u e l ' utilisat e ur a entré
les e ntiers de 1 à 10 dans l ' ordre croissant
maillon courant< - ma_ liste . premier
TANTQUE maillon courant j NULL
FAIRE
ECR I RE ( "Valeur : ", maillon courant - >valeur )
maillon cou r ant< - maillon courant - >suivant
FINTANTQUE
Il v a leur de la liste 5 4 3 2 1 6 7 8 9 10
Il Suppression de trois éléme nts de la l i ste
retirer debut (ma liste , nouvelle valeur , ok)
SI ok
ECRIRE ( " La valeur retirée est : " nouvelle valeur)
ALORS
SINON
186 - - - - -- - - -Algorithmique
Techniques fonda mentales de programma tion
ECRIRE ( " Nous ne pouvons retirer une valeur d ' une list e vide " )
FINSI
retire r_ fin (ma _ liste , nouvelle_va leur , ok )
SI ok
ECRIRE ( " La valeu r r etirée est : " nouvelle val e ur )
ALORS
SINON
ECRIRE ( " Nous ne pouvons retirer une valeur d ' une list e vide " )
FINSI
retirer (ma_ liste , l, ok )
SI ok
ECRIRE ( " La valeur ret i rée est " nouvelle _ valeur )
ALORS
SINON
ECR I RE ( " Nous ne p o u vons reti rer une valeur d ' une liste vide
ou la valeur n ' est pas d a ns la li s te " )
FINSI
I l valeur d e la liste : 4 3 2 5 6 7 8 9
FIN
Dans les procédures retirant des éléments, nous avons ajouté un booléen en
paramètre de sortie pour indiquer que nous avons effectivement retire r un
maillon de la chaîne. Cela nous permet de gérer facilement le cas des listes
vides ainsi que le fait que la valeur n'existe pas dans la liste.
Pour chaque type de suppression de maillon, il est primordial de désallouer
la mémoire du maillon à retirer en l'affectant à la valeur NULL. Dans le cas
contraire, nous créons une fuite de mémoire, donc un problème majeur pour
la gestion de la mémoire du programme par l'ordinateur.
Pour retirer le premier maillon, nous affectons le premier maillon de la liste à
son suivant tout en le désallouant par la suite.
Pour retirer le dernier maillon, nous parcourons la liste jusqu'à l'avant-dernier
maillon. Nous désallouons le pointeur s uivan t de maillon pour effacer le
dernier élément de la liste.
Pour retirer un maillon au milieu de la liste, nous recherchons la valeur du
maillon dans un parcours de la liste. Une fois cette valeur trouvée, nous
faisons "sauter" un maillon au maillon précédent tout en désallouant le mail-
lon à retirer.
Passons en mode confirmé 187
Chapitre 7
Valeur Suivant
Maillon à insérer
Valeur Suivant
0
Maillon 1 Maillon 2 Maillon 3 Maillon 4
Maillon inséré
Valeur Suivanr
0
Maillon 1
Valeur Suivant
Maillon 3
1Valeur I Suivant ri
Maillon 4
188---------Algorithmique
Techniques fondamenta les de progra mma tion
// Création de la liste
POUR i ALLANT DE 1 A 5 AU PAS DE 1
FAIRE
ECRIRE ( " Entrez la valeur ", i )
valeur< - LIRE()
ajout_debut (ma liste , valeur )
FINPOUR
POUR i ALLANT DE 1 A 5 AU PAS DE 1
FAIRE
ECRIRE ( " Entrez la valeur ", i )
valeur< - LIRE ()
ajout_fin (ma_liste , valeur )
FINPOUR
// Affichons no tre liste en supposant q u e l ' utilisateur a e ntr é
les entiers de 1 à 10 dans l ' ordre croissant
ma i llon_courant <- ma_ liste . premier
TANTQUE maillon_ courant t NULL
FAIRE
ECRIRE ( " Val eur : ", mai ll on_cou rant - >valeu r )
FINTANTQUE
// va l e ur de la liste : 5 4 3 2 1 6 7 8 9 1 0
// Insertion de l a valeur 42 à l ' indice 3
inserer (ma_ liste , 42 , 3 , ok )
SI ok
ECRIRE ( " Insertion r é ussi~ " )
SINON
ECRIRE ( " Indice trop grand ou trop petit ou liste vide " )
// valeur de la list e : 4 3 42 2 1 6 7 8 9 1 0
FIN
La logique d'insertion d'une valeur dans une liste est la suivante : après avoir
vérifié que l'insertion est possible (indice positif et inclus dans la taille de la
liste qui est non vide), nous parcourons la liste jusqu'au maillon d'indice voulu
que nous appelons mail l on_a vant. Une fois ce maillon récupéré, nous
créons le nouveau maillon avec son champ su i vant qui pointera sur le
su i vant du maillon_avant, puis le suivant de ma i llon_avant sur ce
nouveau maillon.
1 9 0 - - - - - - - - -Algorithmique
Techniques fondamentales de programmation
Une liste chaînée circulaire est une liste simplement chaînée dont le champ
suivant du dernier maillon pointe sur le premier maillon de la liste, comme
illustré dans la figure ci-dessous .
Maillon 1 Maillon 2 Maillon3 Maillon4
~~I Valeur I
Suivant ~ Valeur Suivant
l
V,
Maillon 1 ~
V,
:;:,
·~
Valeur Suivant ~
Commençons par créer une liste d'un maillon que nous allons parcourir par la
suite :
STRUCTURE maillon entier
DEBUT
valeur ENTIER
*suivant< - NULL : maillon
Valeur Suivant
Maillon à ajouter
Valeur Suivant
Maillon ajouté
Valeur Suivant
Maillon à ajouter
Valeur Suivant
Maillon à ajouter
Valeur Suivant
~~I Valeur I 1-
Suivant Valeur Suivant
Maillon ajouté
Valeur Suivant
1 I 1 - ~ I I 1-
Valeur Suivant Valeur Suivant Valeur Suivant
Pour ajouter, il nous faut toujours parcourir la liste afin de récupérer le dernier
maillon et de changer son pointeur s u ivant sur le bon maillon.
Passons en mode confirmé _ _ _ _ _ _ _ _ _ __ 195
Chapitre 7
~ I l r---
Valeu r Suivarn Valeur Suivant
1 FIN
FINS I
Une liste doublement chaînée est une liste où chaque maillon possède un
pointeur vers le maillon précédent, en plùs du pointeur sur son successeur.
Comme le montre la figure ci-de ssous, le pointeur précédent du premier
maillon a comme valeur NULL comme le pointeur suivant du dernier
maillon de la liste.
Maillon 1 Maillon 2 Madon 3 Maillon 4
1
..i Précédem Valeur Suivam ........, Précédent Valeur Suivant Précédent i Valeur Suivant Précédent Valeur Suivant
i
NUl.L NVLL
Nous allons maintenant écrire un algorithme qui crée une liste doublement
chaînée d'un élément et qui la parcourt :.
PROGRAMME Parcours creation liste doublement chainee
STRUCTURE ma i llon double e ntier
DEBUT
valeu r : ENTIER
*sui v ant< - NULL maillon double entier
*precedent <- NULL maillon doubl e entier
FINSTRUCTURE
VAR
*maillon< - NULL : maillon ent i er
*maillon_parcours <- NULL : maillon_entier
li ste : liste doub lement chainee
i : ENT IER
DEBUT
maillon<- NOUVEAU ma il lon e nti er
ECRIRE( " Entrez l a valeur du premier ma i llon de la liste
200---------Algorithmique
Techniques fondamentales de programmation
circulaire " )
maillon - >valeur < - LI RE( )
l is te . premier< - mai ll on
l is te . taill e< - lis te. taill e + 1
Il Parcours de l a l iste doublement chaînée
mail l on_ courant <- ma_liste . premier
POUR i ALLANT DE 1 A l iste . taill e AU PAS DE 1
FAIRE
ECR I RE ( " Valeur : ", maillon courant - >va leu r )
mai ll on courant< - mail l on courant - >su i vant
FINPOUR
FIN
DEBUT
SI liste . premier= NULL
ALORS
mai llo n< - NOUVEAU maillon entier
maillon -> v aleur <- valeur
liste.premier< - maillon
SINON
maillon< - NOUVEAU maillon entier
maillon - >valeur <- valeur
maillon - >suivant <- liste . premier
liste . premier - >precedent <- maillon
liste . premier< - maillon
liste.taille< - liste . taille+ 1
FINSI
FIN
DEBUT
insere <- FAUX
SI indice> 0 ET liste . t a ille< indice - 1 ET liste . premi e r i NULL
ALORS
maillon< - liste.premier
POUR i ALLANT DE 2 à indice - 1 AU PAS DE 1
FAIRE
maillon avant< - maillon .s uivant
FINPOUR
mail l on nouveau< - NOUVEAU maillon entier
- -
mai l lon nouveau - > valeur< - valeur
maillon_nouveau->precedent <- maillon_avant
maillon - nouveau - >su i vant <- maillon - avant - >suivant
maillon avant - >suivant <- maillon nouveau
insere <- VRAI
FINSI
liste . taille< - liste . taille 1 1
FIN
DEBUT
retire< - FAUX
SI l i ste . premier# NULL
ALORS
maillon courant< - ma l iste . premier
TANTQUE ma il lon courant - >valeur # valeur ET maillon courant
# NUL L
FAIRE
maillon avant< - maillon courant
maillon courant< - mail l on courant - >suivant
FINTANTQUE
SI maillon courant# NULL
ALORS
maillon avant - >suivant <- maillon courant - >suivant
maillon avant - >precedent <- maillon courant - >precedent
mail l on courant< - NULL
liste . t aille< - li s t e.taille - 1
retire< - VRA I
FINSI
l iste . taille< - liste . taille - 1
valeur< - maillon courant - >valeur
maillon courant< - NULL
dernier maillon . suivant< - NULL
retire< - VRAI
FINSI
FIN
■ Re marqu e
Nous n 'avons parlé que de la liste simplement chaînée circulaire. Il existe éga-
lement la liste doublement chaînée circulaire, une liste hybride entre notre liste
circulaire et la liste doublement chaînée vue précédemment. La représenta-
tion d 'un tel typ e de liste est illustré dons la figure ci-après :
i
Maillon 1 ! Ma!ilon 2 Maillon 3 Ua1!1on 4
' l:écendent Valeur Su1vanl - --- ► Précendenl Va!eur Su ivant -·-- - • Précendent Valeur Suivant
' ♦
t
Suivant Suivant Suivant Suivant
t
Suivant Suivant Suivant
Suivant
Valeurl
Deux exemples d'utilisations de piles par l'ordinateur sont la gestion des re-
gistres des processeurs en bas niveau, et en haut niveau la mémorisation de
l'historique d'un navigateur Internet par exemple.
Pour définir une liste, nous pouvons donc utiliser notre STRUCTURE maillon,
ou ma illon_ e ntier pour une pile d'entiers. La STRUC TURE de la pile est
également semblable à celle de la liste simplement chaînée.
STRUCTURE pile_en ti e r
DEBUT
*premi e r< - NULL : maillon entier
ta i lle< - 0 : ENTI ER
1 FINSTRUCTURE
La procédure empiler est une procédure qui prend en paramètres une pile et
une valeur, et qui ajoute cette valeur au sommet de la pile.
La procédure de p iler est une procédure qui prend en paramètre une pile et
une variable du même type que celui des données de la pile pour retourner la
dernière valeur insérée.
PROCEDURE empiler(E/S : pil e : pile entier , E valeur ENTIER )
VAR
ma illon< - NULL : maillon en ti er
maillon courant< - NULL : maillonLentier
DEBUT
ma il l o n <- NOUVEAU ma il lon ent ier
maillon - >val e ur <- valeur
SI pile.taille = 0
ALORS
pile.premier< - maillon
SINON
maillon courant< - p il e . p r emier
TANTQUE mai ll on courant - >suivant? NULL
FAIRE
maillon courant< - mail l on courant - >su i vant
FINTANTQUE
maillon courant - >suivant <- ma illon
FINSI
pile . taille< - pile . taille+ 1
FI
Cela correspond à l'acronyme FIFO pour First In Finst Out : nous ne pouvons
retirer que le premier élément ajouté, comme représenté sur la figure ci-
dessous.
.
Suivant Suivant Suivant Suivant
Suivant
Valeurl
210---------Algorithmique
Techniques fondamentales de programmation
3. Les arbres
3.1 Principe
e
Arbre quelconque
Passons en mode confirmé _ _ _ _ _ _ __ _ __ 211
Chapitre 7
Nous utilisons, nous aussi, des arbres dans notre vie. L'exemple le plus flagrant
pour illustrer cette structure complexe est l'arbre généalogique.
3.2 Création
L'arbre est créé grâce à une structure complexe de données qui, comme la liste,
va se construire sur une autre STRUCTURE : les nœuds. Un nœud d'un arbre
peut être la racine, une branche ou une feuille. Chaque nœud va donc posséder
une liste d'autres nœuds, sauf les feuilles par lesquelles cette liste sera une liste
vide.
Un arbre vide est donc une STRUCTURE contenant un pointeur sur un nœud
initialisé à NULL.
Chaque arbre possède également une caractéristique décrivant son nombre de
niveaux: la profondeur. Nous pouvons vulgariser la profondeur par le
nombre de fois où nous pouvons descendre dans l'arbre. Par exemple, l'arbre
de la figure précédente a une profondeur de trois. Un arbre ne contenant
qu'une racine aura une profondeur de zéro.
Dans cette section, nous nous focalisons uniquement sur les principes des
arbres et leurs manipulations du fait èe la possibilité qu'un nœud puisse avoir
un nombre maximum illimité de nœuds sous lui . La partie algorithmique sera
vue dans la section suivante sur un type d'arbre précis, les arbres binaires, pour
des raisons pédagogiques.
Étudions maintenant les différents parcours des arbres.
212---------Algorithmique
Techniques fondamentales de programmation
Pour le parcours en infixe, nous ne commençons pas par la racine mais par le
sous-arbre le plus à gauche, puis la racine, puis le sous-arbre suivant et ainsi de
suite.
Le parcours en infixe de l'arbre représenté sur la figure précédente sera le
suivant : B C DA E F CH I J M N Z Let K pour finir.
Pour ajouter une feuille , la logique est assez simple. Nous effectuons un
parcours sur la branche considérée et" nous ajoutons à sa feuille un nouveau
nœud . L'ancienne feuille devient une branche, et le nouveau nœud la nouvelle
feuille de cette branche.
Pour insérer un nouveau nœud branche, donc non feuille et non racine, les
choses se compliquent un peu. Imaginons que nous voulions ajouter un nœud
Y entre le nœud Let Z de l'arbre. Pour ce faire, il nous faut parcourir la banche
contenant L jusqu'à L, stocker temporairement le nœud Z, indiquer que le
nouveau nœud sera le suivant de Let le précédent de Z.
3.10.1 Création
Travailler sur un arbre quelconque est très complexe en informatique du fait
de la liste dynamique de nœuds pour représenter les branches de l'arbre.
Nous travaillons principalement sur des arbres binaires. Ils nous permettent
de garder notre structure d'arbre mais en imposant une contrainte : une
branche ne peut avoir au maximum que deux nœuds, comme le montre la
figure ci-dessous.
0
Exemple d'arbre binaire
Passons e n mode confirmé _ _ _ __ _ _ _ _ _ 21 5
Chapitre 7
Avec ces deux structures, un arbre vide sera un arbre dont la racine vaut NULL
et un arbre non vide sera un nœud ayant ou non un sous-arbre à gauche suivi
ou non d'un sous-arbre à droite.
■ Remarque
Un arbre binaire équilibré est un arbre dont toutes les bronches ont la même
profondeur.
FIN
FIN
Nous parcourons notre arbre en commençant par la racine puis ses branches.
L'astuce dans ce parcours est l'utilisation d'une file . Avec l'exemple de la figure
précédente, nous enfilons A. Nous dépilons ensuite A pour l'afficher et
enfilons B et E. Puis nous dépilons B pour l'afficher et enfilons C et D. Après
nous dépilons E et enfilons G et J... ce qui nous donne bien un parcours en
largeur.
Passons en mode confirmé _ __ _ _ _ _ ___ 217
Chapitre 7
DEBUT
SI arbre . racine j NULL
ALORS
arbre temporaire . racine <- arbre . r a cine
parcours postfixe arbre_ binaire (a rbre_ temporaire .
racine - >noeud_ga uche )
parcours postfixe arbre_ binaire(arbre_ temporaire .
racine - >noeud_g auche)
ECRIRE (arbre_temporaire . racine - >valeur )
FINSI
FIN
3.11.1 Principe
Un arbre binaire de recherche est un arbre binaire facilitant la recherche d'une
valeur comme son nom le suggère. Pour simplifier cette opération, l'arbre
binaire possède une contrainte sur les nœuds de l'arbre : les valeurs à gauche
du nœud courant doivent être plus petites que la valeur du nœud et celles à
droite plus grandes que la valeur du nœud, comme le montre la figure ci-
après.
La récursivité de cette fonction est une fois de plus élégante : si la racine n 'est
pas la valeur recherchée, nous appelons cette fonction sur le sous-arbre gauche
si la valeur est plus petite que la valeur de la racine, sinon nous appelons cette
fonction sur le sous-arbre de droite. Si nous avons parcouru tous les sous-
arbres sans trouver la valeur recherchée, nous retournons NULL pour dire
qu'elle n 'existe pas dans l'arbre passé en paramètre.
10
0
On veut ajouter
c?
00
0
On veut ajouter
6
1•
Nous n'abordons pas l'a jout d'une valeur en tant que branche dans unarbre
binaire de recherche pour laisser le lecteur motivé le réaliser par lui-même.
r5
V,
C:
.g
~
@
Passons en mode confirmé _ _ _ _ _ __ _ _ __ 225
Chapitre 7
1
4. Et avec Python?
1
1
En ce qui concerne les listes, Python n'implémente pas les tableaux à taille
~ fixe, il implémente directement ces structures complexes grâce au type de
données lis t qui possède une allocation dynamique de la mémoire. La
gestion des pointeurs est entièrement effectuée par le langage, ce qui simplifie
largement les programmes .
Cependant, Python ne possède pas de type de données correspondant aux
arbres par défaut.
Nous vous proposons d'implémenter ces ty pes de données complexes dans le
dernier chapitre de cet ouvrage grâce à la notion d'objet car Python ne possède
pas le type STRUCTURE, ce langage utilise l'objet pour nous permettre de créer
nos propres types de données complexes .
5. Exercices
5.1 Exercice 1
5.2 Exercice 2
5.3 Exercice 3
Chapitre 8
Les fichiers
1. Le système de fichiers
1.1 Préambule
N'en avez-vous pas assez de devoir toujours entrer vos valeurs à la main ? Est-
ce vraiment de cette manière que fonctionnent les programmes ?
Pour donner une solution à la première question, nous allons voir dans ce
ch apitre la persistance des données dans un fichier. La persistance indique
juste que nous allons stocker physiquement sur l'ordinateur les données que
le programme va utiliser mais aussi celles que le programme peut compiler.
Avant de voir comment stocker des informations dans des fichiers , il nous
faut voir ce que sont justement ces fichiers.
Les droits d'accès indiquent qui a le droit de faire quoi sur le fichier :
- Droit de lecture : pouvoir accéder aux données pour les lire .
- Droit d'écriture : pouvoir écrire dans le fichier.
- Droit d'exécution : pouvoir exécuter un fichier qui représente un
programme.
La grande question est de savoir comment un programme peut retrouver un
fichier sur un disque.
< PremierRépertoire
Nom
fichier
v Sous-Répertoire1
fichier
> Sous-sous-répertoire
Sous-répertoire2
fichier
fichier 2
fichier 3
Sous-repertoire3
hchier
fichier 2
fichier 3
fic hier 4
Arborescence de {t'chiers
230---------Algorithmique
Techniques fondamentales de progra mmation
Cette racine est le point de montage du disque dur que vous parcourez :
- C: sur Window (système DOS)
- / sur Linux et macOS (système Unix)
C'est à partir de ce point de montage que vous pouvez récupérer un fichier.
Prenons un exemple : vous travaillez sur le fichier exemple qui se trouve sur
votre bureau . Pour y accéder, vous utilisez le chemin :
- / users/ moi/ Desktop/ exemple sur Linux et macOS
- C: \ Utilisateurs\ moi\ Bureau\ exemple sur Windows
Nous pouvons déjà remarquer une différence notable entre les systèmes Unix
et le système DOS : Unix utilise le / pour entrer dans un répertoire et DOS
le \. Faites bien attention à ce point dans vos prochains programmes.
Si vous êtes dans le répertoire sous-rep qui est sur le bureau, pour accéder à
votre fichier, vous devez aller dans le répertoire qui contient le répertoire sous-
rep. Pour remonter d'un répertoire, vous pouvez utiliser le raccourci ".. " repré-
sentant le répertoire précédent :
- / .. / exemple sur Linux et macOS
- \ .. \ exemple sur Windows
2.2.1 csv
Le format CSV, ou Coma -Separated Values , permet de séparer les champs
d'une ST RUCT URE par des virgules et les ST RUCTURES par des sauts de
ligne .
Comme le montre la figure ci-dessous, les fichiers .csv sont manipulables avec
un tableur pour un être humain.
Accueil Insertion Dessin Mise en page Formutes Données Révision Affichage Q Dites•le-nou
0 Perte de dormêe,s potentielle Vous risquez de perdre certair.e'i fonctionnalités sl vous enregistrez ce classeur au formai .csv (
0 M1se à jour d'Otfice Les mises à jour d-e s.é.curité. les correctlls, !es amé!ioraOO,s -. Rien ne vous échappera si vous sé1ectionn
PlB fx
A S - -- -- - G "
::! .ld."tut·,-utrgQfY kt'
2 !o.·Thl!tt.cofS~ÏhAtr1cafe;,turn7colo,:,,rs .·,9
3 [l. " H.l!f~Ufe by V.ilwusH the Gold:Src1.im1 e-ne:lrw, whichli a hi9hlymodlfiedve-t11œofwhat-e~lneP,9
il / Tht-~atll! t11 ~ ll-act<St.:JrWars : E :,9
J." LeoNtdo sM«W1Us.idoe1nothilw~bmw s. •,9
6 4,"Whid! s11n of thoe lodla< is l'i!PfH&med by the ô11br _,9
5,"What was t !)e tit!e ol tN flrst Bond movill!, 1e-leu~ ln 19621".9
6, "lrhh mllSJ Tlllat ~ to _ ,9 4rrlntY'3&QIJt: , asiemblrd ln?" ,9
9 '. 8,"AII of tht fol!owlrg aœ Î~r&/.-1!111rs ln the Pacifie W..nd nation of kl riba tl EXCEPT:" ,9
1D '9: comp1ete the-followlr« 1naloev: Audi îs to Volkswagcn as tnfiniti is to r ,9
ll 10, "ln web OHl111\ wh:,t doH CS$ S.Und forr ,9
12 11,"Wnlch modem (by country ls lht 1q;Jon tha r w.1.s known ;u fltlrya: !1 ln aACW!nt ti n,.~?• ..9
13 11,~ Wlvt Wl pet m.onlœyFn t't'lds& Q00 ?",9
4 ; 13/ Whid'l of Ù'll.!St' ror>'lpilM! dœs NOl m1nuf.ictt;fl! motortveles r ,9
S · 14,"What 11 the oam e oft~ machine tha t lails andt>nimti1Hydoorfls mankiodin tt'lebeg lnni"!J of t he flnt Half- Ufe gaml•'",9
(, : 1s,"Whidl oft~ foilow'ir,g is NOT a iu 1el t>n,e.nt?~,9
1' l6,"WhkhontofthesePh'tltFloydalbùm1werealu,a m<Mt>r,'J
!
1.8 17, "WNt 1s t~ n1ht way to si:,eH the a pltal of Huntary7",9
l!i 1s: 1n u noer funV.i, lue&q ~et to56-S7Wronc Num l.",9
19,"The&q,..O.y al Dl!Ju .se rluofg1mH t:a~ plaœmrlnc whkh war r ,S
1 ' 20,"Whlt lngrt:dit'nU are. ~ rt"d tomaic,e a catœ in Minecnittr ,9
21," ln thegar.il! B:.ltti~bloc.-k Theatff, whilt wu W n.1mt' of tht W!Kt' actorwho YOiud tl>t: N1rr1tor7",9
22/ !iwittt'rlaod N t four Ntlonal langu:igtt, English belns one of the-m." ,9
' 23,"Wtwdl ofthe-J.erpecifl lsnote.,.t.inct?".9
S ;24, "Whk:h hm~ _New 't'M Ya r.k«, outfle!~, dld Marl lyo Moorœ mar,.,1",9
25, "Nidœ!OÔf:oo re j&ted th!! pllol: t:o AM-ntUfe Titne. • ,9
7 ;26,"Wh.n 11 the Nflle of the proteu that mm one qublt of lrlOl'matlon usinig two bit!. of c!;mical lnformatlon?",9
-S · 27,"Wl'IM dld the CO bt-jln to ap~ilf on the: COOSiJmr.r m.trlœt?",9
l8,"ThelSle.~ine l1 howm.;mycubi< inc-he.s?*,9
29,"What ~ tM lr:terr.ationaJ Syst~ of Qulnlltles rcl'tt 102.4 t,vl:H as7",9
l :30,"lnwhlt•8ob Ross&Q:\ die?",9
l l1, "Wh.1t does the tNm MIME st.ir,d Pa, !nr('flfds l0cunp..1ln,1" ,9
l 32. "WhohtAltadcOnlll r ,9
3-' 33, "from wt On Mel1nchc. ftoaturrd ln?",9
2.2.2 XML
Les fichiers XML, pour eXtensib!e M arkup Language , donnent une structure
sous forme de balises aux données.
Un fichier XML est toujours une balise contenant d'autres balises. Une balise
est définie par un identifiant unique au sein du fichier, entre chevrons. Les
valeurs des données peuvent être valorisées soit en attribut de la balise, soit à
l'intérieur de la balise.
<myfirsteleme nt>
<mysecondelement>
valu e
</mysecondelement>
<myth irde l ement itsattribute=« value»/>
</my f iste l ement>
■ Re m arque
Le format est sensible à la casse dans la définition des balises et des attrib uts.
<?xml version = " l . 0 " encoding= " UTF- 8 " ?>
<gens>
<pers onne année de naissanc e= " l988 " ><prénom>Adélaïde
</prénom><nom>Adev~rdit</nom></pe rsonne >
<per s onne année_de_naissance= " l989 " ><prénom>Béranger
</prénom><nom>Sachambr ess </nom></ pers onne>
<per s onne année _ de_ naissanc e= " 2010 " ><prénom>Cédric
</ prénom><nom>Azaraile</nom></pe rs onne>
<per s onne année _ de_ naissanc e= " 20 0 7 " ><prénom>Dési rée<
/ prénom><nom>Mifasolac i do< / nom>< / personne>
</ g e ns>
2.2.3 JSON
Le XML étant très verbeux avec les identifiants des balises, donc lourd pour
envoyer des informations d'un programme à un autre, un format de fichier
texte le remplace de nos jours : le JSON pour]ava Script Object Nota tion.
■ Re marque
Même si le JSON a pour objectif de remplacer le XML, le format XML reste un
standard dans l'informatique et ne pourra pas être obsolète avant de
nombres années.
Le principe du JSON est de garder les informations d'un fichier XML en enle-
vant au maximum les identifiants. Ainsi une liste sera définie par une paire de
crochets, ses éléments étant séparés par des virgules. Cette liste remplace la
première balise du fichier XML et chaque balise contenant des sous-balises.
Chaque autre type d'information est donné avec le format clé: valeur, comme
dans un dictionnaire. Les données de type chaîne de caractères sont également
entre double quotes comme en algorithmie.
Transformons notre fichier XML en JSON :
personne : {
annee de naissance 1988
prenom : "Adélaïde "
nom : "Adeverdit "
},
personne : {
annee de naissa nce 1989 ,
prenom : " Béranger "
nom : " Sachambress ",
},
personne : {
annee de na i ssa nce 201 0 ,
prenorn : "Cédric " ,
n om : "Azaraile "
} '
personne : {
annee de naissance 2 007 ,
prenom : " Désirée "
nom : " Mi fas olacido "
236---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
Pour aller plus loin avec la persistance des données dans un programme en
informatique, nous pouvons conseiller au lecteur de s'intéresser aux bases de
données et au langage SOL avec un ouvrage tel que SOL, Les fondamentaux
du langage écrit par Anne-Christine Bisson et publié aux Éditions ENI. Les bases
de données sont une technologie qui permet de formater simplement les
données tout en les enregistrant sur le disque et qui, pour finir, est facilement
intégrable dans vos programmes.
3. Manipulation de fichiers
Pour des raisons de simplicité, nous ne manipulerons que des fichiers texte
non formaté s dans le reste de ce chapitre. Nous laissons le lecteur étudier la
manipulation des autres types de formats de fichiers par lui-même. En effet,
nous lui apportons les bases nécessaires à la manipulation de tout ty pe de
fichier texte.
De plus, nous partons également du principe que le fichier manipulé existe sur
le disque et se trouve dans le même répertoire que le fichier de l'algorithme.
1 mon_ fichier <- OUVRIR- FI CHI ER (" nom du fichier ", " mode d ' ouverture " )
238--- ------Algorithmique
Techniques fondamentales de programmation
Une fois le fichier ouvert, vous pouvez commencer à le lire. Sa lecture se fait
de manière séquentielle : l'algorithme lit les lignes les unes après les autres.
Pour lire une ligne d'un fichier, nous allons utiliser la procédure LIRE qui
prend en paramètre d'entrée le fichier de type FI CHIER et en sortie la ligne
lue de type CHA I NE.
1 LIRE (mon_fichier , ligne ) .,
Pour pouvoir parcourir un fichier, il faut savoir quand le fichier est fini . C'est
le rôle de la fonction EO F (mon - f ich ier) (pour End Of File): cette fonction
retourne un booléen VRAI si nous sommes à la fin du fichier (le curseur sur le
fichier ne pointe plus de texte) ou FAUX quand il reste des lignes dans le
fichier.
Mettons en place l'algorithme pour lire un fichier choisi par l'utilisateur :
PROGRAMME Lecture fi chier
VAR
mon fichier : FICHIER
nom du f ichi er : CHAINE
l ig ne : CHAINE
DEBUT
ECRIRE ( " Entr e z le nom du fichi e r " )
nom du fic h ier< - LIRE ()
mon fic hi e r< - OUVRIR- FI CHIER(nom du f ichie r , " l ecture " )
TANTQU E NON EO F (mon_fichier )
FAIRE
LIRE(mon_ fichie r , ligne )
ECR IRE (ligne )
FINTANTQUE
FERMER - FICHIER (mon fich ier )
FI N
■ Remarq u e
À la différence de l'algorithmie, si le fichier n'existe pas, Python va le créer lors
de l'instruction open, en écriture ou en ajout. L'ouverture d 'un fichier inexistant
en mode Lecture provoque une erreur terminant le script.
En Python, la lecture d'un fichier peut se faire grâce. à trois fonctions qur
retournent toutes une chaîne :
- lire tout le fichier d'un seul coup : re a d () .
- lire une ligne du fichier: re adline ().
- lire toutes les lignes du fichier (retourne une liste de chaînes) :
re adl in es () .
Voyons maint enant un exemple d'utilisation de chacune de ces fonctions .
4.2.1 read()
Avec la fonction rea d, vous lisez tout le texte du fichier, saut de ligne inclus,
en une instruction.
name = input ( " Entrer le nom de votre f ichier " )
fichier = open (name , ' r ', encodi ng = " UTF- 8 " )
te x te = fichier.read ()
1 print (texte )
fich i er . close ()
l u to • l l l -1 '-• ~)
• -·~h,_l,.._ b H<)
c 'r1 !• J> ,.,._.. dcl> l :Lc o,:·•,1
•ic•i- ~, , , u,•. ~i >
4.2.2 readline()
La fonction readl ine vous permet de lire votre fichier ligne par ligne.
name = input ( " Ent re r le nom de votre fichier " )
f ichier = open (name , ' r ', e ncoding ="UT F- 8 " )
p remiere_ ligne = fichi e r . readline ()
1 fichier. close ()
Notons que parcourir de manière sûre notre fichier est délicat avec cette
fonction.
4.2.3 readlines()
La fonction readlines lit toutes les lignes du fichier et les stocke dans une
liste de chaîne de caractères.
name = inp u t ( " Entrer l e nom de vo t re fic h ier " )
f ichi e r = op e n (name , ' r', encoding= " UTF- 8 " )
ligne s= fich ier .readl ines ()
f o r ligne in ligne s
print (li gne )
f ichier . clos e ()
.. .
244---------Algorithmique
Techniques fondamentales de programmation
print (t exte )
print (l igne )
print ()
fichier.close()
4.2.4 for in
Vous pouvez également utiliser l'instruction fo r in qui parcourt chaque
ligne du fichier. Cette méthode reste la plus simple en Python.
name = input ( " Entrer le nom de votre fi ch ier " )
f o r ligne in fichi er
print (l igne [ : - 1 ])
1 f ichier . clos e ()
Entrt r h nos'dt wotn tith:itr cht pitrtl.p'J
, , . . IHth Ulpon fs-. pi
tr<W 01 :..port •die
f gr li gne in lignu,
pri...rl lignt)
f o rllgneinfiehitr ,
~ri ntlligne[: - 1 ]1
torhgnt in tiel>itr,
pr1nt\hgnt, end• 0 )
pnnt E)
Notons que 1 lors de notre parcours de ligne 1 la ligne lue dans le fichier se
termine par un saut de ligne : nous n'affichons donc pas son dernier caractère.
Une alternative est d'enlever le saut de ligne de la fonction p ri nt
name = input ( " Entrer le nom de vot re f i chier " )
fichi e r open (name , ' r ', encoding= " UT F- 8 " )
fichier . close ()
...
246---------Algorithmique
Techniques fondamentales de programmation
4.3.2 print()
Vous pouvez changer la sortie par défaut du print pour écrire dans un fichier
et non sur la console avec l'option file: ·
fichier = open(name , ' w', encoding= " UTF - 8 " )
nombre_ligne = int (input ( " Ent re r l e nombre de lignes de votre fichier " ))
for i in range (nombre_ligne) :
te x te = input( " Entrer votre lign e " + s tr( i ))
■ Remarque
Toutes nos écritures de fichiers se positionnent sur la première du ligne au
risque d 'effacer ce qui existe déjà dans le fichier. Si vous voulez converser le
texte du fichier, vous devez utiliser le mode a pour append.
Les fichiers _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 247
Chapitre 8
4.4.1 Module
Un module en Python permet d'importer et d'utiliser des fonctions définies
dans ce module. Pour utiliser ses fonctions , vous devez importer le module .
1 import nomModul e
Le premier import importe toutes les fonctions définies dans le module. Pour
les utiliser, il faudra les préfixer du nom du module suivi d'un point. Le second
n'importe que les fonctions listées dans l'instruction. Vous pouvez les utiliser
sans les préfixer.
Les imports sont toujours les premières instructions de votre script.
Illustrons les modules avec le module math qui contient la fonction fsum
calculant la somme d'une liste et la constante pi.
impor t math
ma_liste = [l , 2 , 3 , 4 , 5]
somme= math.fsum (ma_liste )
■ Remorque
Un module en Python peut contenir énormément d 'instructions. Lors de son im -
port, l'interpréteur Python lit tout le module. 11 est donc conseillé de préférer le
deuxième import pour ne pas surcharger la mémoire.
248---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
Cette méthode peut également provoquer un conflit de nom mage avec vos
propres instructions. Par exemple, vous avez défini une fonction sum et vous
utilisez également la fonction sum de Math . Deux solutions s'offrent à vous:
renommer votre fonction ou préfixer la fonction du module par le nom du
module.
,
4.4.2 Utilisation de walk l
Pour manipuler l'arborescence de fichiers , Python propose le module os qui
implémente toutes les fonctions nécessaires pour gérer les fichiers et les
répertoires d'un disque.
Parmi ces fonctions , il existe la fonction walk. En l'applïquant sur un
répertoire, elle va récupérer tous les répertoires, les sous-répertoires et tous les
fichiers contenus dans le répertoire passé en paramètre. .-,
from os import walk
monRepertoire = input ( " Entrer le répertoire à parcour ir " )
liste fichiers= [ ]
liste_ sous_ repertoires = []
for repertoire_courant , sous r epertoires ,
fichiers in walk(monReperto ir e ) :
for fichier in fichiers :
li ste_ fichiers . append ( fichi er )
for sous _ repertoir e in sous_rep e rto i res
liste so us repertoires . append (sous repertoire )
print ( " Voici les fic hi ers " )
f or fi chie r in li ste fichiers :
print (fic hi e r)
print ( " Vo ici les sous - répertoires " ) ...
for sous_repertoire in liste sous repertoires ...
print (s ous repertoire )
"t:,
~
Q.l
V,
~
.':'.l
..c:
·ê>
~
z:'
Lu
V,
C:
.g
~
@
Les fichiers _ _ _ _ __ __ __ _ _ __ _ 249
Chapitre 8
5. Exercices
5.1 Exercice 1
5.2 Exercice 2
Écrivez l'algorithme qui recopie un fichier texte dont le nom est donné par
l'utilisateur dans un autre ficher texte nommé "copie .txt". Codez le script
Python correspondant.
5.3 Exercice 3
Écrivez l'algorithme qui compare deux fichiers texte et qui affiche la première
différence. Codez le script Python correspondant.
5.4 Exercice 4
5.5 Exercice 5
Codez le script Python qui remplace tous les espaces d'un fichier texte par un
triple espace. Par exemple, "le chat" deviendra "le chat".
..
250---------Algorithmique
Techniques fondamentales de programmation
5.6 Exercice 6
5.7.1 Exercice 7
Codez le script Python qui liste tous les fichiers d'un répertoire dont le nom
est donné par l'utilisateur.
5.7.2 Exercice 8
Codez le script Python qui demande à l'utilisateur de donner le nom d'un •
1
répertoire à parcourir afin de savoir si ce répertoire contient un fichier ou un 1
répertoire dont le nom est également entré par l'utilisateur. 1
l
l
1
- - - - - - -- - - --251
Chapitre 9
Commencer avec l'objet
1. Préambule
L'objectif de ce livre est d'apprendre la logique de programmation afin de pou-
voir programmer vos premiers scripts en Python. Tout apprentissage du
développement informatique commence par ce que nous avons vu jusqu'à
présent : la programmation impérative, ou procédurale si vous préférez.
Ce style de programmation est à la base de toutes les autres, que ce soit la pro-
grammation fonc t ionnelle ou la Programmation Orientée Objet (POO ou
Object-Oriented Programming en anglais), les deux grands courants actuels du
développement informatique.
À l'heure de l'écriture de ce livre, nous pouvons voir un style de programma-
tion revenir sur le devant de la scène : la programmation fonctionnelle. Il s'agit
d'un style utilisé quasiment à la naissance de la machine et commençant à être
implémenté dans la plupart des langages. La programmation fonctionnelle
moderne en est encore à ses débuts et elle est le plus souvent utilisée pour
traiter des masses de données comme en Big Data par exemple, c'est pourquoi
nous ne l'introduisons pas dans cet ouvrage.
La programmation orientée objet détient facilement aujourd'hui plus de 80 %
des parts du marché du développement informatique. Elle est apparue au
début des années 1990, apportant une vraie révolution sur la modélisation des
données dans les programmes.
252 - --------Algorithmique
Techniques fondamentales de programmation
Afin que vous puissiez continuer votre apprentissage avec de solides bases,
nous vous proposons dans ce chapitre une introduction à la programmation
orientée objet et ses principes de base .
Le lecteur intéressé par ce type de programmation pourra approfondir ses
connaissances et compétences avec des ouvrages tels que UML 2.5 et Design
Patterns ou encore Apprendre la Programmation Orientée Objet avec le
langage Python dans la collection Ressources informatiques aux Éditions ENI.
2. Le naturel de l'objet
2.1 Introduction
L'accès aux attributs d'un obj et se fait comme pour les structures avec
l'opérateur"." pour notre exemple qui est incomplet.
254---------Algorithmique
Techniques fondamentales de programmation
■ Remarque
Pour la programmation orientée objet, nous utilisons la convention de nom- 1
mage Came/Case : les classes commencent toujours par une majuscule et la
séparation des mots d 'un identifiants est également représenté par une
majuscule.
■ Remarque
Attention à ne pas confondre classe et objet : classe = type et objet =
variable .
1 quantité : ENTIE R
FINSTRUCTURE
Devient :
CLASSE Produi t
ATT RIBUT
DEBUT
FIN
q uant ite : ENTIER
nom : CHAINE ,
Nous remarquons qu 'il n'y a pas de différence notable entre une STRUC T URE
et une classe sur la modélisation des attributs . Cependant, les classes ajoutent
les traitements sur ses attributs dans son bloc de méthodes .
2.3 Méthodes
PROCEDURE produit_achete ()
DEBUT
quantite < - 0
FIN
FIN
CLASSE Produit
ATTRIBUT PUBLIC
DEBUT
quan ti t e : ENTIER
FIN
ATTRIBUT PRIVE
DEBUT
nom : CHAINE
FIN
METHODE PUBLIC
DEBUT
PROCEDURE diminuer_quant i te (E : combien ETIER )
DEBUT
qu a nt i te <- quantite - comb ie n
F IN
FIN
METHODE PRIVEE
DEBUT
PROCEDURE p r oduit_ achete ()
DEBUT
quantite <- 0
F N
FIN
Notre classe Pro duit illustre le fait que la déclaration algorithmique d'une
classe n'est pas lisible rapidement.
Afin de donner un aperçu d'une classe, un langage a été créé: l'UML pour
Unified Modeling Language. Ce langage fournit plusieurs schémas, appelés
diagrammes, pour représenter tous les aspects d'un programme orientée
objet.
Commencer avec l'objet _ __ _ _ _ _ _ _ _ 257
Chapitre 9
Classe
+ attributel:type
+ attribute2:type
- attribute3:type
+ sous-programmel(params):type
de retour
- sous-prog ramme(params)
- sous-programme()
Dans la classe représentée dans la figure ci-dessus, les deux premiers attributs
sont donc publics, le troisième privé. Cette classe ne possède qu'une méthode
publique, la première, les deux dernières étant privées.
Pour analyser un algorithme ou programme existant, avec cette représenta-
tion schématique, les classes sont plus rapidement lisibles, leur structure
algorithmique sert uniquement pour lire l'implémentation des méthodes de la
classe.
...
258---------Algorithmique
Techniques fondamentales de programmation
Modélisons notre classe Produit avec l'UML dans la figure ci-dessous pour
conclure cette section :
Produit
+ quantile : ENTIER
- nom : CHAINE
3.1 Introduction
Les premières sections de ce chapitre ont présenté les principes des classes et
des objets. Cette section est dédiée à la manipulation des ob jets, de leur
création jusqu'à leur destruction en mémoire.
Comme le lecteur peut s'en douter, une classe étant une structure de données
plus que complexe, un objet sera donc forcément un pointeur.
Pour instancier un objet, nous utiliserons le même opérateur que pour les
pointeurs : NOUVEAU . Cependant, ce qui suit cet opérateur va être différent,
cela ne sera pas le nom de la classe, mais le constructeur de la classe.
Commencer avec l'objet _________ __ 259
Chapitre 9
3.2.1 Constructeur
Le constructeur d'une classe est une méthode obligatoire dans la classe . Il
permet d'allouer la mémoire de l'objet qui instancie la classe .
Le constructeur a toujours le même nom que la classe et ne retourne rien. Il
peut prendre des paramètres ou non, selon nos besoins.
Par convention, le constructeur prend en paramètres les valeurs à affecter aux
attributs de l'objet. Dans le cas d'un constructeur sans paramètre, que nous
appelons constructeur par défaut, il initialise les attributs à des valeurs par
défaut comme son nom l'indique.
Le constructeur se définit par le mot-clé CONS TRUC TEUR en premier dans le
bloc des méthodes publiques et ce, en étant la première méthode de ce bloc.
Implémentons donc un constructeur dans notre classe Produit pour
illustrer cette méthode spécifique.
CLASSE Produit
ATTRIBUT PUBLIC
DEBUT
quantite : ENTIER
FIN
ATTRIBUT PRIVE
DEBUT
nom : CHAIN E
FIN
METHODE PUBLIC
DEBU T
CONSTRUCTEUR Produit (name CHAINE , combien ENTIER )
DEBUT
nom< - name
quantite <- combien
FIN
PROCEDURE diminuer_ quantite(E : combien ENTIER)
DE BUT
quantite <- quant ite - combien
FIN
FIN
METHODE PRIVEE
DEBUT
PROCEDURE produit_achete ()
DEBUT
260---------Algorithmique
Techniques fondamentales de programmation
quantite <- 0
FIN
FIN
PROGRAMME Constructeur e xemple
VAR
mon_produit : PRODUIT
nom : CHAINE
quantite : ENTI ER
DEBUT
ECRIRE ( " Entrer l e nom de votr e p r oduit)
nom <- LIRE
ECR IRE ( " Entrer l a q u antité de votr e p r oduit)
quantite <- LIRE
mon_ produit <- NOUVEAU Produit(nom , quantite )
FIN
3.2.2 Destructeur
Oui dit allocation de mémoire, dit forcément désallocation de mémoire. Pour
désallouer la mémoire d'un objet, notamment si la classe déclare des attributs
de ty pe pointeur, nous pouvons définir à nouveau une méthode spécifique : le
destructeur.
Le dest ructeur est automatiquement appelé lorsque l'objet prend comme
valeur NULL pour l'effacer de la mémoire du programme.
Le destructeur se définit grâce au mot-clé DESTRUCTEUR suivi par
~ NomDeLaClas se dans le bloc public des méth odes de la classe, juste après
le constructeur. Contrairement au constructeur, il est facultatif.
Nous n'avons besoin de définir cette méthode que si notre classe possède des
attributs de ty pe pointeur. En effet, pour les attributs non pointeurs, la
mém oir sera désallouée automatiquement .
Ajouton s donc un pointeur à n otre classe Produit pour l'attribut nom.
Commencer avec l'objet ___________ 261
Chapitre 9
CLASSE Produit
1 ATTRIBUT PU BLIC
1 DEBUT
t
!
quanti t e : ENTIER
FIN
AT TRIB UT PRIVE
DEBUT
*n om< - NULL CHAIN E
FIN
METHODE PUBL IC
DEB UT
CONSTRUCTEUR Produit (n a me CHAINE , combi en ENTIER )
DEBUT
nom< - NOUVEAU CHAINE
*nom< - name
qua n tite <- comb ie n
FIN
DESTRUCTE UR ~Produ it ()
DEB UT
nom< - NULL
FIN
262---------Algorithmique
Techniques fondamentales de programmation
1 FIN
mon_produit <- NULL
Nos objets étant implicitement des pointeurs, nous devons donc utiliser
l'opérateur -> pour accéder aux méthodes et attributs publics.
CLASSE Produ it
ATTRIBUT PUBLIC
DEB UT
quantite : ENTIER
FIN
ATTRIBUT PRIVE
DEB UT
*nom <- NULL CHAINE
FIN
METHO DE PUBLIC
DEBUT
CONSTRUCTEUR Produit (name CHAINE , combien ENTIER )
DEB UT
nom< - NOUVEAU CHAINE
*nom< - name
quantite <- combien
FIN
DESTRUCTEUR ~Produit ()
DEB UT
nom< - NULL
FIN
METHODE PRIVEE
DEBUT
PROCEDURE produ it_achete ()
DEBUT
quantite <- 0
FIN
FIN
PROGRAMME Appel_méthode_exemple
VAR
mon_ produit : PRODUIT
nom : CHAINE
quantite : ENTIER
DEBUT
ECRIRE ( " Entrer le nom de votre produit )
nom< - LIRE
ECRIRE ( " Entrer l a quantité de votre produi t )
quantite <- LIRE
mon_produit <- NOUV EAU Produit (n om , quantite )
// Nous appelons la méthodre diminuer_quantite
mon_ produit - >diminuer_quantite ( l )
mon_ produit <- NU LL
FIN
STRUCTURE li ste
DEBUT
taille <- 0 ENTIER
*premier< - NULL : maillon
FI NSTRUCTURE
264---------Algorithmique
Techniques fondamentales de programmation
Classe Liste
ATTRIB UT PUBLIC
DEBUT
p r emier : Maillon
FIN
ATTRIBUT PRIVE
DEBUT
taill e : ENTIER
FIN
Maillon Liste
+ valeur : type
<> ◊
- taille : ENTIER
l
Première représentation des listes simplement chaînées en UML
Nous pouvons manipuler nos listes simplement chaînées en ajoutant,
insérant ou supprimant un maillon de ces dernières . Les fonctions et procé-
dures correspondantes vont maintenant devenir les méthodes de la classe
Liste. Nous pouvons remarquer que la classe Noeud ne possède pas de
méthode, hors son constructeur et son destructeur, et cela est tout à fait
permis en programmation orientée objet.
Notre diagramme de classes représentant les listes simplement chaînées
devient celui de la figure ci-dessous :
liste
+ valeur : type
266---------Algorithmique
Techniq ues fondamen tales d e programmation
Classe Maillon
ATTRIBUT PUBLIC
DEBUT
valeur : type
suivant : Maillon
FIN
METHODE PUBLIC
DEBUT
CONSTRUCTEUR Maillon (v type )
DEBUT
valeur<- v
suivant< - NULL
FIN
DESTRUCTEUR ~Maillon ()
DEBUT
suivant< - NULL
FIN
FIN
Classe Liste
ATTRIBUT PUBLIC
DEBUT
premier : Maillon
FIN
ATTRIBUT PRIVE
DEBUT
taille : ENTIER
FIN
METHODE PUBLIC
DEBUT
CONSTRUCTEUR Liste ()
DEBUT
premier< - NULL
taille <- 0
FIN
DESTRUCTEUR ~List e ()
VAR
maillon courant , maillon MAILLON
SI premier? NULL
ALORS
maillon courant< - premier
TANTQUE maill o n courant? NULL
FAIRE
maillon<- maillon courant - >suivant
maillon< - NULL
Commencer avec l'objet ___________ 267
Chapitre 9
FIN
PROCEDURE ajouter fin (E valeur type )
DEBUT
l
FIN
PROCEDURE retirer debut (S valeur type , S retire BOOLEEN )
DEBUT
'l FI N
PROCEDURE retirer fin (S valeur type , S retire BOOL EEN )
DEBUT
FIN
PROCEDURE retirer (E /S valeur type, E indice ENTIER,
S : retire BOOLEEN)
DEBUT
FIN
FONCTION inserer(valeur : type✓ indice ENTIER ) BOOLEEN
DEBUT
VAR
insere <- FAUX : BOOLEEN
*maillon avant : Maillon
*maillon nouveau : Maillon
i : ENTIER
DEBUT
SI indice> 0 ET taille<= indice ET premier? NULL
ALORS
maillon< - premier
POUR i ALLANT DE 2 à i nd i ce AU PAS DE 1
FA IRE
maillon avant< - maillon.suivant
FINPOUR
maillon nouveau< - NOUVEAU Maillon
maillon nouveau - > valeur< - valeur
maillon nouveau - >suivant <- maillon avant - >suivant
maillon avant->suivant < - maillon nouveau
inse re < - VRAI
268---------Algorithmique
Techniques fondamentales de programmation
FI NSI
F IN
FIN
liste .tai l l e< - liste . taille - 1
RE TOURNER (insere )
F IN
FIN
Les attributs sont maintenant initialisés dans les constructeurs et non plus
lors de leur déclaration, ce qui est la convention en programmation orientée
objet.
Le destructeur de la class~ Liste va parcourir la liste en désallouant chaque
maillon, ce qui devait être fait à la main dans chaque algorithme utilisant la
structure liste avant que l'algorithme ne s'arrê te . Nous voyons donc avec cette
méthode un premier avantage de la modélisation en classe.
Les méthodes de la classe Lis te permettent quant à elles d'alléger la liste des
paramètres car elles ont un accès direct à la liste, son premier maillon et sa
taille. Cela nous permet de transformer la procédure d'insertion en fonction
retournant un booléen indiquant si l'insertion a pu être effectuée. Cette
méthode est donc plus légère à gérer que l'ancienne procédure.
Arbre
Noeud
Ces deux structures peuvent être traduites avec les classes suivantes :
Classe NoeudEnti er
A TRIBUT PUBLIC
DEBUT
noeud gauche : NoeudEntier
noeud droit : NoeudEntier
valeur : ENTIER
FIN
METHODE PUBLIC
DEBUT
CONSTRUCTEUR No e udEntier (v : · va le ur )
DEBUT
valeur< - v
no e ud_ gauche <- NULL
noeud droit< - NULL
FIN
DESTRUCTEUR ~NoeudEntier ( )
DEBUT
noeud_gauche <- NULL
noeud droit <- NULL
FIN
FIN
270---------Algorithmique
Techniques fondamen tales de programmation
DEBUT
CONSTRUCTEUR ArbreBinaireEntier ()
DEB UT
racine <- NULL
FIN
DESTRUCTEUR ~ArbreBinaireEntier ()
VAR
arbre temporai r e : ArbreBinaireEntier
DEBU
SI arbre . racine ? NULL
ALORS
arbre_temporaire . racine <- racine
parcours_profondeur_ arbre_ binaire (arbre temp o raire .
racine - >noeud_ gauche )
parcours _ profondeur arbr e_bina ir e (arbr e temporaire .
racine - >noeud_gauche )
racine< - NULL
FINSI
FIN
PROCEDURE parcou r s _ profondeur ()
DEBUT
FIN
PROCEDURE parcours infixe ()
DEBUT
FIN
PROCEDURE parcou rs_p ostfi xe ()
DEBUT
FIN
PROCEDURE parcours largeu r ()
DEB UT
FIN
FONCTION cherche r noeud (valeur ENTIER ) NœudEntier
DEBUT
FIN
PROCEDURE a jouter noeud (E valeur ENTIER )
DEBUT
FIN
FIN
Commencer avec l'objet _ _ _ _ _ __ __ _ 271
Chapitre 9
La logique reste la même que celle des listes simplement chaînées. Les
méthodes allègent les paramètres et donc leur code et le destructeur nettoie
proprement la mémoire.
■ Remorque
Nous appelons aussi la classe mère la super classe et la fille la sous-classe. Les
deux appellations sont utilisées par les développeurs et ont la même significa-
tion : le lien d 'héritage entre les classes.
1
Carnivore
•1
Herbivore
1
Omnivore
Comme illustré dans la figure précédente, le lien d'héritage entre deux classes
est une flèche pointant vers la classe mère.
Le diagramme de classes de la figure précédente peut être traduit par l'algo-
rithme suivant où nous utilisons les mots-clés HERITE DE pour indiquer le
lien d'héritage lors de la déclaration de la classe fille :
Classe Animal
ATTRIBUT PUBLIC
DEBUT
FIN
METHODE PUBLIC
DEBUT
F IN
Classe Carnivore HERITE DE Animal
ATTRIBUT PUBLIC
DEBUT
FI N
METHODE PUBLI C
DEBUT
FIN
Cl asse Herbivore HERITE DE Animal
ATTRIB UT PUBLIC
DEBUT
FIN
METHODE PUBLIC
DEBUT
FIN
Classe Omn i vore HERITE DE Animal
ATTRIBUT PUBLIC
DEBUT
FIN
METHODE PUBLIC
DEBUT
FIN
Commencer avec l'objet ___________ 273
Chapitre 9
+ valeur : type
r<> ◊
+PROCEDUR E ajouter_debut(E : vale,ir : type)
+PROCEDURE ajourer_fin(E : valeur : type)
+PROCEDURE retirer_debut(S : valeur : type, S : retire : BOOLEEN)
+PROCEDURE retirer_fin(S : valeur : type , S : retire : BOOLEEN)
+PROCEDURE retirer_debut(E/S : valeur : type. S : retire : BOOLEEN)
1 ' + FONCTION inserer(v aleur : type, indice : ENTIER) : BOOLEEN
MaillonDouble
Î
Liste Double
27 4 - - - - - - - -- Algorithmique
Techniques fon d amentales de programmation
FIN
FIN
Cl asse Maill on Doub le HER ITE DE Ma i ll on
ATTRIBUT PUBLI C 1
DE BUT
p r ece d e nt : Mail l onDoubl e
1
FIN
METHODE PUBLIC
DEBUT
CON STRUC TEUR Ma i ll on Doubl e (v t ype )
DEBUT
Ma i llon (v )
prece d e nt < - NULL
F IN ~
4.1 Polymorphisme
4.1.1 Objet
Grâce au polymorphisme, un objet de type de la classe mère peut appeler le
constructeur d'une de ses classes fille. Pour vous en souvenir, vous pouvez uti-
liser la technique mnémonique suivante : une mère peut être enceinte d'une
fille, donc la contenir, mais une fille ne peut pas être enceinte de sa mère.
Ainsi nous pouvons rendre notre classe MaillonDouble adéquate :
Cl asse Maillon
ATTRIBUT PUBLIC
DEBUT
val e ur : type
suivant : Ma ill on
FIN
METHODE PUBLIC
DEBUT
CONSTRUCTEUR Mai llon (v type )
DEBUT
valeur< - v
su ivant< - NULL
FIN
DESTRUCTEUR ~Maillon ()
DEB UT
suivant< - NULL
FIN
FIN
Classe Mai ll onDoubl e HERIT E DE Maillon
ATTRIBUT PUBLIC
DEBUT
pre cedent : Ma il lonDouble
FIN
... '
..,
276---------Algorithmique
Techniques fondamentales de programmation
METHODE PUBLIC
DEBUT
CONSTRUCTEUR Maill onDouble(v type )
DEBUT
Ma illon (v)
precedent <- NULL
FIN
DESTRUCTEUR ~MaillonDoubl e ()
DEBUT
~Maillon ()
precedent <- NULL
FIN
PROCEDURE in stancier suivant ()
DEBUT
suivant< - NOUV EAU Maillon Double(l)
F IN
FIN
de paramètres. ~
~
Seul le destructeur d'une classe ne peut pas être surchargé, toutes les autres "'~
V,
.l'.l
méthodes, y compris le constructeur, peuvent l'être. En effet, le destructeu r ne ""-~
possède qu'une seule signature possible car il lui est interdit de prendre des ~
paramètres .
~
V,
Class e Maillon
ATTRIBUT PUBLIC
DEBUT
val eur : typ e
suivant : Maillon
FIN
METHODE PUBLIC
DEBUT
CONSTRUCTEUR Maillon (v type )
DEBUT
valeur< - v
suivant< - NULL
FIN
DESTRUCTEUR ~Maillon ()
DEBUT
suivant< - NULL
FIN
FIN
Classe MaillonDouble HERITE DE Maillon
ATTRIBUT PUBLIC
DEBUT
prec ede nt : MaillonDouble
FIN
ME THODE PUBLIC
DEBUT
CONSTRUCTEUR Mail l onDoubl e (v type )
DEBUT
Mai llon (v )
preceden t <- NULL
FIN
CONSTRUCTEUR MaillonDoubl e ()
DEBUT
suivant< - NULL
precedent <- NULL
FIN
DESTRUCTEUR ~MaillonDouble ()
DEBUT
~Maillon ()
prece dent <- NULL
FIN
PROCEDURE instancier suivant ()
DEB UT
suivant<- NOUVEAU MaillonDoub l e ()
FIN
FIN
4.
2 7 8 - - - - - - - - -Algorithmique
Techniques fondamentales de programmation
FI
PROCEDURE ajouter fin (E valeur type )
DEBU T
Commencer avec l'objet ___________ 279
Chapitre 9
FIN
PROCEDURE retirer_debut (S valeur type, s retire BOOLEEN )
DEBUT
FIN
PROCEDURE retirer fin (S valeur type , s retire BOOLEEN )
DEBUT
FIN
PROCEDURE retirer_debut (E/ S valeur type, S retire BOOLEEN)
DEBUT
FIN
FONCTION inserer (valeur: type , indice ENTIER ) BOOLEEN
DEBUT
VAR
insere < - FAUX : BOOLEEN
*maillon avant : Maillon
*maillon nouveau : Maillon
i : ENTIER
DEBUT
SI indice> 0 ET taille< = indice ET premier? NULL
ALORS
maillon< - premier
POUR i ALLANT DE 2 à indice AU PAS DE l
FAIRE
maillon avant< - maiÏlon . suivant
FIN POUR
maillon no uv eau< - NOUVEAU Maillon
maillon_ nouveau - > val eur< - valeur
maillon nouveau ->s uivant <- maillon avant ->s uiva nt
maillon avant - >suivant <- maillon nou vea u
insere <- VRAI
FINSI
FIN
FIN
liste.taille<- liste.taille - 1
DEBUT
Liste ()
FIN
DESTRUCTEUR ~ListeDo u ble ()
~ListeDouble 1
FIN
PROCEDURE aJouter debut (E : valeur type ) ....
VAR
*maillon : MaillonDouble
DEBUT
SI premier = NUL L
ALORS
maillon<- NOUVEAU MaillonDouble (valeur )
premier< - maillon
SINON
ma i llon< - NOUVEAU MaillonDouble(valeur)
maillon - >suivant <- premier
premier - >precedent <- mai llon
premier< - maillon
FINSI
FIN
PROCEDURE ajouter_fin (E valeur type )
DEBUT
,
FIN
PROCEDURE retirer debut (S valeur type, S retire BOOLEEN )
DE BUT
.,
FIN
PROCE DURE retirer fin (S valeur type , s retire BOOLEEN )
DEBUT
-,
FIN
PROCEDURE retirer debut(E/S val e u r type , S retire BOOLEE N)
DEBUT
FIN
FONCTION inserer (valeur : type, ind ice ENTIER ) BOOLEEN
DEB UT
FIN
FIN
Commencer avec l'objet _ _ _ _ __ _ _ _ _ 281
Chapitre 9
+ manger0
♦
1
Carnivore Herbivore
+ manger() + ma11ger0 1
1
t t 1
1
1
Omnivore 1
,l
.
1
5. L'objet en Python
Nous créons donc une classe Po i nt dans un fichier point.py que nous impor-
tons dans le fichier contenant le ma i n, le fichier main.py.
Pour faciliter l'import de nos classes, les fichiers des scripts doivent tous être
dans le même répertoire.
284- - - - -- - --Alg orithmique
Techniques fondamentales de programmation
Les attributs d'une classe en Python ne peuvent être déclarés sans être initia-
lisés du fait du typage dynamique du langage. Du fait de la syntaxe de ce lan-
gage, les attributs ne peuvent être uniquement déclarés dans les méthodes de
la classe. Allons donc étudier comment déclarer les méthodes d'une classe pour
en déclarer notamment ses attributs ..
En Python, pour différencier une fonction d'une méthode, il nous faut placer
le mot -clé se l f en premier paramètre de la méthode, qui est toujours définie
par le mot-clé de f . Ce mot-clé indique que la méthode est attachée à la classe,
self pouvant être traduit comme "soi-même" .
Pour appeler une méthode, nous utilisons l'opérateur"." de l'objet instancié.
Lors de l'appel d'une méthode, ce mot-clé se lf disparait de la liste des para-
mètres, il n 'est obligatoire que lors de sa défin ition.
Le constructeur est une méthode spéciale qui s'appelle obligatoirement
i ni t (self, pa r am l, para m2 ... ) où les paramètres, or le s e lf,
sont optionnels.
Pour appeler le constructeur et donc instàncier un objet, il suffit d'appeler le
nom de la classe suivi de la liste des paramètres du constructeur (une paire de
parenthèses vide si le constructeur n 'est défini qu'avec se l f ).
Nous déclarons et initialisons les attributs de la classe dans son constructeur.
Pour différencier une variable d'un attribut, un attribut est toujours de la
fo rme s e l f . i den tifia nt . Hormis cette contrainte, un attribut se
manipule normalement comme une variable ou un objet.
# fichier point . py
class Point :
def init (se lf , x , y ) :
# Ini ti a l isation et déclaration des attributs
self. x = x
self. y = y
def afficher (self )
print ( " Point :", se lf . x , "-" self . y)
d ef changerCoo rdonnees (self , nouveau x , nouveauy )
Commencer avec l'objet ___________ 285
Chapitre 9
# f ichie r main . py
fr om point import Point
point= Point ( 4 , 3 )
point . afficher () # a ff iche en console Point : 4 - 3
point . changerCoordonnees ( l , 2 )
point . afficher () # a f fiche en conso l e Point : 1 - 2
# fichier main . py
from point i mpor t Point
point= Point ( 4 , 3 )
c l ass Fi gure :
def init (sel f, x, y )
1 sel f. point = Point (x , y )
class Figure :
d ef ini t (s elf, point ) :
se l f . p o i n t = point
Avec cette instanciation de la classe Point, notre objet point ne meurt pas
en même temps que notre objet instanciant la classe Figu r e. Il est alloué en
dehors de la classe, il peut donc continuer à vivre sans aucun objet instanciant
la classe Figure.
Commencer avec l'objet _ _ _ _ _ _ _ _ _ __ 287
Chapitre 9
Pour présenter l'héritage simple en Python, nous allons utiliser une classe
Rectangle et une classe Carre.
Un rectangle possède une largeur et une longueur. Il peut s'afficher, calculer
son aire et son périmètre. Un carré est un rectangle particulier ayant la même
valeur pour sa largeur et sa longueur. Le carré hérite donc du rectangle comme
le montre le diagramme de classes de la figure qui suit.
En Python, l'héritage se déclare lors de la déclaration de la classe fille grâce à
une paire de parenthèses :
1 class Fi ll e (Mere )
Rectangle
+ largeur . ENTIER
+ longueur : ENTIER
+ aireQ : REEL
+ perimetre() REEL
Carre
# fichier carre.py
from rectangle import Rectangle
class Carre (Rectangle ) :
def init (self , largeur )
Rec tangle . init ( self , largeur, largeur)
def str ( self )
return " Carrée de c6té " + str ( self. l argeur ) + " et d ' aire"+
str ( self.aire ())
# fichier main.p y
fro m rectangle import Rectangle
from carre impor t Carre
if name -- ' main
mon Rec ta ngle = Rectangle (2 , 8)
print (monRectangle )
print ( " Aire du rectangle :", monRecta ngle . aire ()) # 16
print ( " Périmètre du rectangle :", monRectangle . perimetre ()) # 20
monCarre = Carre (3 )
pri nt(mon Carre )
print ( " Aire du carré . " , monC arre . aire ()) # 9
print( " Périmètre du carré :", monCarre .perimetre ()) # 12
Nous utilisons dans ce script une subtilitt de Python pour afficher un objet
avec la fonction native de Python : nous reecrivons la méthode
_ str_ (self) . Cette méthode est appelée automatiquement par l'inter-
préteur lorsqu'une instruction p r in t prend un objet en paramètre.
Cette méthode illustre également le polymorphisme en Python en changeant
l'affichage pour la classe Ca rre.
Notons que pour qu'une classe fille puisse appeler une méthode définie dans
sa classe mère, il faut préfixer la méthode par self., comme ici pour l'affi-
chage d'un carré qui affiche en plus son aire. j
a.,
V)
l',
~
-<::
·~
sic
Commencer avec l'objet ___________ 289
Chapitre 9
# fichier carrepri v e . py
from rectangleprive i mport RectanglePrive
class CarrePrive (RectanglePrive ) :
def init (se l f , largeur )
Rectangle. ini t (self , largeur , largeur )
def str (self )
return " Carrée de côté " + str (getLargeur (self ))
..
290-- - - - - -- - Algorithmique
Techniques fondamentales de programmation
La classe Ornn i vor e hérite bien des classes Ca rni vo re et Herb i vo re. De
ce fait, elle doit respecter deux contraintes pour que le script puisse s'exécuter
sans erreur :
- Appeler le constructeur de chacune de ses mères dans son constructeur pour
réaliser une allocation mémoire correcte.
- Réécrire la méthode mange r () car l'interpréteur Python ne peut pas savoir
quelle méthode appeler sinon.
Notre script est d'un seul coup plus lisible pour un autre développeur qui
connaît forcément l'opérateur d'égalité .
Commencer avec l'objet _ _ _ _ _ _ _ _ _ _ 293
Chapitre 9
6. Exercices
6.1 Exercice 1
Modélisez en UML puis avec un algorithme une classe Duree possédant trois
attributs privés :
- le nombre d'heures de la durée ;
- le nombre de minutes de la durée ;
- le nombre de secondes de la durée.
Et les méthodes publiques suivantes :
- Un constructeur par défaut (tous les attributs auront zéro comme valeur)
et un constructeur initialisant toutes les valeurs. On vérifiera que les
nombres d'heures, minutes, secondes sont bien positifs, dans le cas
contraire on considèrera leurs opposés. On fera également les conversions
nécessaires pour que les nombres de minutes et de secondes soient stricte-
ment inférieurs à 60.
- Une méthode réalisant l'affichage de la durée (sous la forme 3h10m00s).
- Une méthode convertissant la durée en un nombre de secondes .
- Une méthode rajoutant à la durée un nombre de secondes.
Codez par la suite les scripts Python correspondants.
6.2 Exercice 2
294---------Algorithmique
Techniques fondamentales de programmation
Animal
1
+ nom : CHAINE
+ coul eur : CH AINE
+ cri : CHAINE i
+ PROCEDURE afficheQ
41
Î
1 1 l
Mammifere Omnivore
6.3 Exercice 3
6.4 Exercice 4
B Bloc, 31, 71
Booléen, 58, 64
Boucle, 80
imbriquée, 93
infinie, 82, 89
Boucle-else, 95
Branche, 210, 214
Break, 94
break, 95
.. .
298---------Algorithmique
Techniques fondamentales de programmation
C Chemin
absolu, 230
relatif, 230
Classe, 252, 253, 265, 283
fille, 271
mère, 271
Clé/ valeur, 122
Colonne, 100, 102
Commentaire, 49
Composition, 263, 264, 286
Compteur, 85
Concaténation, 39
Conflit de nommage, 248
Constante, 33
Constructeur, 258, 259, 274
Continue, 94
Curseur, 236
Droit
d'écriture, 229
d'exécution, 229
de lecture, 229
E empiler, 205
Encodage, 241
enfiler, 208
Enregistrement, 110
EOF, 238
ET logique, 65
Extension, 231
Extraction, 40
1 IDE, 47
Identifiant, 26
import, 247
Indentation, 33, 71
Indexation, 101, 115
Indice, 101 , 105, 115
Instanciation, 258
Instruction, 19, 20, 80, 130, 132
conditionnelle, 74
Intention, 125
Itération, 80
lndex _ _ _ _ __ _ _ _ _ _ _ __ 3Ql
M Matrice, 102
Mémoire
cache, 18
implémentation, 171
morte ou ROM, 18
vive ou RAM, 18
Mère, 274
Méthode, 253, 254, 262
réécriture, 278, 282
Module, 247
os, 248
302---------Algorithmique
Techniques fondamentales de programmation
NON logique, 67
NULL, 173, 176, 186, 198
0 Obfuscation, 289
Objet, 252, 253, 283
Opérateur, 2~, 43, 50
arithmétique, 52
de comparaison, 36, 53
logique, 37, 54
mathématique, 34
opérations sur les chaînes, 39
sur les caractères, 38
ternaire, 76
OU logique, 66
R Racine, 213
range, 91
read, 242
readline, 243
readlines, 243
Recherche, 105
dichotomique, 161
Récursivité, 142, 144, 149, 159, 240
imple, 143
Réduction, 107
Référence, 171
Répertoire, 227, 228
courant, 230
racine, 229
Répéter ... Jusqu 'à, 84
Répéter jusqu'à, 93
Retour multiple, 165
304---------Algorithmique
Techniques fondamentales de programmation
s Séquentielle, 238
Signature, 257, 276
Slicing, 121
Sous-arbre, 210
Sous-classe, 271
Sous-programme, 129
Structure, 110, 113
conditionnelle, 58
de données, 100
imbriquée, 112
itérative, 79
itérative imbriquée, 87
Super classe, 271
Surcharge
de méthodes, 276
opérateur, 291
Système de fichiers, 227
Tri
à bulles, 154
fusion, 159
par insertion, 155
par sélection, 151
rapide, 157
Tuple, 120
w walk, 248
while, 92, 93, 94, 95
write(chaîne), 246
;z:
UJ
Ressources informatiques
Algorithmique
Techniques fondamentales de programmation (exemples en Python)
Ce livre sur l'algorithmique s'adresse à toute personne désireuse de Ludivine CREPIN
maîtriser les bases essentielles de la programmation. Pour ap- Docteur en Intelligence Artificielle depuis
prendre à programmer, il faut d'abord comprendre ce qu'est vrai- 2009, Ludivine CREPIN est depuis consul-
ment un ordinateur, comment il fonctionne et surtout comment il tante indépendante pour des entreprises au
peut faire fonctionner des programmes, comment il manipule et niveau européen, de la start-up à la multi-
stocke les données et les instructions, quelle est sa logique. Alors, au nationale. Forte de son expertise, elle pro-
fur et à mesure, le reste devient évidence : variables, tests, condi- pose à ses clients ses services de conseil,
tions, boucles, tableaux, fonctions, fichiers, jusqu'aux notions de développement et de recherche appli-
quée pour tous les types de projets infor-
avancées comme les compréhensions de listes et les objets.
matiques. Également formatrice, elle fait
Le langage algorithmique (ou la syntaxe du pseudo-code des algo- profiter le lecteur de toute sa pédagogie
rithmes) reprend celui couramment utilisé dans les écoles d'infor- pour l'apprentissage de l'algorithmique
matique et dans les formations comme les BTS, OUT, première basée sur le langage Python.
année d'ingénierie à qui ce livre est principalement destiné et
conseillé. Une fois les notions de base acquises, le lecteur trouvera
dans ce livre de quoi évoluer vers des notions plus avancées : un
chapitre sur les objets ouvre les portes de la programmation dans
des langages évolués et puissants comme le C, le C++, le Java, le
C# et surtout Python.
À la fin de chaque chapitre, l'auteur propose de nombreux exercices
corrigés permettant de consolider ses acquis.
Tous les algorithmes de ce livre sont réécrits en Python et les
sources, directement utilisables, sont disponibles en téléchargement
sur le site www.editions-eni.fr.
sur www.editions-eni.fr :
➔ Le code source en Python de la plupart
des exemples du livre.
Pour plus
d'informations :
cri
■
0
~
ro
I'--
cri
www.ed~ions-eni.fr