Polycopié Algorithmique L1 PDF

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Centre Universitaire Belahdj Bouchaib - Ain Témouchent Initiation à l’Algorithmique Cours et exercices corrigés 1ère année tronc commun MI, ST et SM Dr MEDEDJEL Mansour Maître de conférences en Informatique Département de Mathématiques et Informatique Centre Universitaire Belhadj Bouchaib - Ain Temouchent Préambule Ce polycopié est destiné essentiellement aux étudiants de la 1ère année du tronc commun Mathématiques et Informatique (MI), ainsi qu’aux étudiants des autres domaines (ST et SM) désirant acquérir des bases solides en programmation sans connaissances préalables. Il s’agit d’un support pédagogique qui couvre une partie fondamentale et essentielle de l’algorithmique constituant ainsi un prérequis indispensable pour la programmation. L'objectif de ce support est d’initier le lecteur à la résolution des problèmes par la programmation, commençant par l’analyse du problème, la recherche de la solution ou la méthode pour résoudre ce problème, l’écriture de cette solution sous forme d’un algorithme, et enfin la traduction de l’algorithme en programme exécutable par la machine en utilisant un langage de programmation tel que le langage C. Il convient de noter que ce support de cours est un manuel d’accompagnement de l’étudiant et sa lecture ne constitue en aucun cas une dispense de la présence attentive aux séances de cours et de travaux dirigés ou pratiques. Table des matières Introduction générale......................................................................................................................1 Partie I - Cours................................................................................................................................3 Chapitre 1 - Introduction aux algorithmes....................................................................................4 1. Contexte....................................................................................................................................4 2. Notions élémentaires.................................................................................................................4 3. L'algorithmique.........................................................................................................................5 3.1. Définition..........................................................................................................................5 3.2. Principe général.................................................................................................................6 4. Caractéristiques des algorithmes...............................................................................................6 4.1. Structure générale..............................................................................................................6 4.2. Les variables et les constantes...........................................................................................7 4.2.1. Les variables..............................................................................................................8 4.2.2. Les constantes............................................................................................................8 4.3. Les types de base...............................................................................................................8 4.3.1. Type entier.................................................................................................................9 4.3.2. Type réel....................................................................................................................9 4.3.3. Type caractère...........................................................................................................9 4.3.4. Type booléen.............................................................................................................9 Chapitre 2 - Les instructions simples........................................................................................... 11 1. Introduction............................................................................................................................. 11 2. L’instruction d’affectation....................................................................................................... 11 3. L’instruction de lecture........................................................................................................... 12 4. L’instruction d’écriture............................................................................................................ 13 Chapitre 3 - Les instructions conditionnelles (les alternatives)................................................. 15 1. Introduction............................................................................................................................. 15 2. Structure d’un test................................................................................................................... 15 2.1. Forme simple................................................................................................................... 15 2.2. Forme complète............................................................................................................... 16 3. Tests imbriqués....................................................................................................................... 16 4. Les choix multiples................................................................................................................. 19 5. Conclusion.............................................................................................................................. 20 i Chapitre 4 - Les instructions itératives (les boucles).................................................................. 21 1. Introduction............................................................................................................................. 21 2. Définition................................................................................................................................ 21 3. L’instruction « Pour ».............................................................................................................. 21 4. L’instruction « Tant que… faire »........................................................................................... 23 6. L’instruction « Répéter… jusqu’à »........................................................................................ 23 7. La notion du compteur............................................................................................................ 24 8. La notion d’accumulation........................................................................................................ 25 9. Les boucles imbriquées........................................................................................................... 25 10. Conclusion.............................................................................................................................. 26 Chapitre 5 - Les tableaux.............................................................................................................. 27 1. Introduction............................................................................................................................. 27 2. Tableaux à une seule dimension.............................................................................................. 27 2.1. Déclaration...................................................................................................................... 27 2.2. Manipulation................................................................................................................... 28 2.2.1. L’affectation............................................................................................................28 2.2.2. La lecture.................................................................................................................29 2.2.3. L’écriture.................................................................................................................29 3. Tableaux à deux dimensions................................................................................................... 30 3.1. Déclaration d’un tableau à deux dimensions................................................................... 31 3.2. Manipulation d’un tableau à deux dimensions................................................................. 31 4. Tableaux à n dimensions......................................................................................................... 32 5. La recherche dans un tableau................................................................................................... 32 5.1. La notion du drapeau....................................................................................................... 32 6. Le tri d’un tableau................................................................................................................... 35 6.1. Tri par sélection............................................................................................................... 35 6.2. Tri par insertion............................................................................................................... 37 6.3. Comparaison.................................................................................................................... 39 7. Conclusion.............................................................................................................................. 39 Chapitre 6 - Les enregistrements (structures)............................................................................. 40 1. Introduction............................................................................................................................. 40 2. Définition................................................................................................................................ 40 3. Déclaration et manipulation.................................................................................................... 40 4. Tableau de structures............................................................................................................... 41 5. Structure membre d’une autre structure................................................................................... 42 6. Conclusion.............................................................................................................................. 42 ii Chapitre 7 - Les fonctions et les procédures................................................................................ 43 1. Introduction............................................................................................................................. 43 2. La notion de sous-programme................................................................................................. 44 2.1. La portée d’une variable.................................................................................................. 44 2.2. Les paramètres................................................................................................................. 46 2.3. Le passage de paramètres................................................................................................ 46 3. Les fonctions........................................................................................................................... 46 3.1. Définition d’une fonction................................................................................................ 47 3.2. Appel d’une fonction....................................................................................................... 47 4. Les procédures........................................................................................................................ 48 4.1. Définition d’une procédure.............................................................................................. 48 4.2. Appel d’une procédure.................................................................................................... 48 5. Fonctions et procédures récursives.......................................................................................... 50 5.1. Exemple illustratif........................................................................................................... 50 5.2. Interprétation................................................................................................................... 50 5.3. Mécanisme de fonctionnement........................................................................................ 51 6. Conclusion.............................................................................................................................. 52 Chapitre 8 - Les pointeurs............................................................................................................ 53 1. Introduction............................................................................................................................. 53 2. Notion de pointeur................................................................................................................... 54 2.1. Définition................................................................................................................................ 54 3. Allocation dynamique............................................................................................................. 56 4. Application des pointeurs........................................................................................................ 57 5. Conclusion.............................................................................................................................. 59 Partie II - Exercices corrigés........................................................................................................ 60 Série 1 : Initiation aux algorithmes.................................................................................................. 61 Série 2 : Instructions algorithmiques de base.................................................................................. 64 Série 3 : Les instructions conditionnelles........................................................................................ 65 Série 4 : Les instructions itératives.................................................................................................. 66 Série 5 : Les tableaux et les structures............................................................................................. 69 Série 6 : Les fonctions et les procédures......................................................................................... 70 Corrigé série 1................................................................................................................................. 74 Corrigé série 2................................................................................................................................. 77 Corrigé série 3................................................................................................................................. 79 Corrigé série 4................................................................................................................................. 82 Corrigé série 5................................................................................................................................. 86 iii Corrigé série 6................................................................................................................................. 92 Partie III – Travaux pratiques en C............................................................................................ 96 TP 1................................................................................................................................................ 97 TP 2.............................................................................................................................................. 100 TP 3.............................................................................................................................................. 101 TP 4.............................................................................................................................................. 102 TP 5.............................................................................................................................................. 104 TP 6.............................................................................................................................................. 107 TP 7.............................................................................................................................................. 110 Conclusion générale.................................................................................................................... 112 Références bibliographiques...................................................................................................... 113 iv Table des figures Figure 1. Etapes de développement..................................................................................................5 Figure 2. Principe du traitement automatisé.....................................................................................6 Figure 3. Organisation de la mémoire..............................................................................................7 Figure 4. Opération de lecture........................................................................................................ 13 Figure 5. Opération d’écriture........................................................................................................ 14 Figure 6. Organigramme « Etat de l’eau »...................................................................................... 18 Figure 7. Calcul de la factorielle par récursivité............................................................................. 51 Figure 8. Représentation d’une variable en mémoire..................................................................... 53 Figure 9. Le pointeur et la variable pointée en mémoire ………………………………………….54 v Introduction générale Introduction générale Dans ce support, le lecteur est initié à la notion d’algorithmique, ses concepts et ses fondements de base. L’accent est mis également sur les structures de données nécessaires au développement algorithmique tout en insistant sur le côté pratique à travers des exemples et des exercices corrigés à la fin du polycopié. Le côté programmation est aussi fort présent dans ce support à travers des exemples typiques de travaux pratiques. Le langage C est utilisé à cette fin pour ses caractéristiques plus proches aux algorithmes ce qui le rend un langage de programmation pédagogique convenable aux étudiants en phase d’initiation à la programmation. Ce manuscrit est constitué également de trois parties :  Partie I – Cours Cette partie couvre le côté théorique nécessaire à la compréhension du concept d’algorithmique et de programmation. Cette partie est composée également de huit chapitres. - Chapitre 1 : est une initiation à la discipline d’algorithmique. - Chapitre 2 : présente les instructions de base et fondamentales pour l’écriture des algorithmes. - Chapitres 3 et 4 : traitent les instructions qui permettent de contrôler le flux d’instructions de base, il s’agit notamment des instructions conditionnelles (les alternatives) et des instructions d’itération (les boucles). - Chapitres 5 et 6 : sont consacrés aux structures de données indispensables à la manipulation et au stockage des données dans la phase de traitement, à savoir les tableaux et les enregistrements (ou les structures). - Chapitre 7 : présente une initiation à la modularité algorithmique à travers la notion des sous-programmes (fonctions et procédures). Les modes de passage de paramètres par valeur et par adresse sont également mis en évidence ainsi qu’un aperçu sur la notion de la récursivité. - Chapitre 8 : introduit le lecteur à la notion des pointeurs avec des exemples d’application, ainsi qu’au mécanisme de gestion dynamique de la mémoire. -1- Introduction générale  Partie II – Exercices corrigés Cette partie est consacrée à la mise en œuvre des connaissances acquises dans les cours à travers un ensemble de travaux dirigés qui couvrent globalement tous les chapitres de la partie I.  Partie III – Travaux pratiques en C Cette partie présente une initiation à la programmation à travers des exemples de travaux pratiques à réaliser en langage C avec quelques exemples de code source. -2- Partie I - Cours -3- Chapitre 1 - Introduction aux algorithmes Chapitre 1 - Introduction aux algorithmes 1. Contexte Le terme Informatique est un néologisme proposé en 1962 par Philippe Dreyfu 1 s pour caractériser le traitement automatique de l’information, c’est une contraction de l’expression « information automatique ». Ce terme a été accepté par l’Académie française en avril 1966, et l’informatique devint alors officiellement la science du traitement automatique de l’information, où l’information est considérée comme le support des connaissances humaines et des communications dans les domaines techniques, économiques et sociaux. 2. Notions élémentaires  Informatique L’informatique est la science du traitement automatique de l’information. Elle traite de deux aspects complémentaires : - les programmes ou logiciels (software) qui décrivent un traitement à réaliser, - les machines ou le matériel (hardware) qui exécute ce traitement.  Hardware C’est l’ensemble des éléments physiques (microprocesseur, mémoire, disques durs,...) utilisés pour traiter les informations.  Software C’est un programme (ou ensemble de programmes) décrivant un traitement d’informations à réaliser par un matériel informatique.  Algorithme La notion d'algorithme est à la base de toute la programmation informatique. La définition la plus simple que l’on peut associer à cette notion est qu’un algorithme est une suite ordonnée d’instructions qui indique la démarche à suivre pour résoudre un problème ou effectuer une tâche. Le mot algorithme vient du nom latinisé du mathématicien perse Al- Khawarizmi, surnommé « le père de l'algèbre ». 1 Informaticien Français -4- Chapitre 1 - Introduction aux algorithmes Exemple : Appel téléphonique a. Ouvrir son téléphone, b. Chercher/Composer le numéro du destinataire, c. Appuyer sur le bouton « Appel ». Ce mode d’emploi précise comment faire un appel téléphonique. Il est composé d’une suite ordonnée d’instructions (ouvrir, chercher/composez, appuyer) qui manipulent des données (téléphone, numéro, bouton) pour réaliser la tâche d’appel. 3. L'algorithmique 3.1. Définition L’algorithmique est la science des algorithmes. Elle s’intéresse à l’art de construire des algorithmes ainsi qu’à déterminer leur validité, leur robustesse, leur réutilisabilité, leur complexité ou leur efficacité. L’algorithmique permet ainsi de passer d’un problème à résoudre à un algorithme qui décrit la démarche de résolution du problème. Par conséquent, la programmation consiste à traduire un algorithme dans un langage « compréhensible » par l’ordinateur afin qu’il puisse être exécuté automatiquement. Figure 1. Etapes de développement. La figure 1 ci-dessus illustre les deux phases nécessaires pour obtenir un code source :  Phase d’algorithmique qui implique la recherche et l’écriture d’un algorithme ;  Phase de programmation qui consiste à traduire l’algorithme obtenu en un programme à l’aide d’un langage de programmation (C, Java, Python,…). Dans la première phase, on doit définir les données qu’on dispose et les objectifs qu’on souhaite atteindre, ainsi que prévoir des réponses à tous les cas possibles. -5- Chapitre 1 - Introduction aux algorithmes Exemple : résolution d’une équation de second degré ax2+bx+c =0 → Les données sont a, b et c → Les sorties sont x1 et x2 → Les cas : a=0 et b≠0, a = 0 et b = 0, a ≠0 , …… 3.2. Principe général Le traitement automatique de l’information consiste à exécuter des instructions (opérations élémentaires et complexes) sur des données d’entrée afin de générer d’autres informations appelées résultats ou données de sortie. Données Traitement Résultat Entrée (Input) Sortie (Output) Figure 2. Principe du traitement automatisé. Exemple : Calcul de la moyenne d’un étudiant Supposons qu’on doit calculer la moyenne d’un étudiant pour un ensemble de matières. Donc, on doit : i. Définir le nombre des matières concernées ainsi que les notes et les coefficients ; ii. Réaliser les opérations suivantes : - Multiplier chaque note d’une matière par son coefficient, - Calculer la somme des résultats des multiplications, - Diviser la somme obtenue par le total des coefficients, iii. Afficher le la moyenne de l’étudiant (résultat final). Remarque : Lorsqu’on écrit un algorithme, les questions suivantes doivent être considérées :  Quel est le résultat attendu ?  Quelles sont les données nécessaires (informations requises) ?  Comment faire (le traitement à réaliser) ? 4. Caractéristiques des algorithmes 4.1. Structure générale Un algorithme se compose généralement de deux parties : Partie déclarative : appelée aussi entête de l’algorithme, elle contient généralement les déclarations (des constantes, des variables, etc.). -6- Chapitre 1 - Introduction aux algorithmes Partie corps de l’algorithme : constituée d’une ou plusieurs séquences d’instructions faisant appel à des opérations de base à exécuter par l’ordinateur. Syntaxe : Algorithme nom_de_l’algorithme ; Partie déclarative (Entête) < Liste de variables/constantes > ; Début < Séquence d’instructions > ; Partie corps de l’algorithme Fin 4.2. Les variables et les constantes L’élément unitaire de stockage de l’information est appelé bit. Un bit ne peut avoir que deux états distincts : 0 ou 1 (vrai ou faux dans la logique). Dans la mémoire de l’ordinateur, les données sont manipulées par groupes de 8 bits (octets), ou plus (mots de 16, 32, 64 bits,…). Une case mémoire est donc appelée mot et pour que l’unité centrale puisse stocker une information et la retrouver dans la mémoire, chaque mot est repéré par une adresse. Dans la programmation, les adresses mémoire sont représentées par des noms. Le programmeur ne connait pas donc l’adresse d’une case mais plutôt son nom. Il y a donc deux façons de voir la mémoire centrale de l’ordinateur : côté programmeur et côté ordinateur tel qu’il est illustré, à titre d’exemple, dans le schéma suivant (figure 3). Mémoire Adresses Mots 10000000 6 x 10000001 8 y Variables 10000010 7 moyenne 10000011 … Côté ordinateur Côté programmeur Figure 3. Organisation de la mémoire. -7- Chapitre 1 - Introduction aux algorithmes 4.2.1. Les variables Une variable est une case mémoire destiné à contenir des valeurs de type défini au préalable (nombres, caractères, chaînes de caractères,…). Elle possède un nom, un type, et un contenu qui peut être modifié au cours de l’exécution de l’algorithme. Le mot clé est: Var. 4.2.2. Les constantes La définition d’une constante est la même que celle d’une variable à la différence que sa valeur reste inchangée tout au long du déroulement (exécution) de l’algorithme. Le mot clé est: Const. Les variables et les constantes sont déclarées selon la syntaxe suivante : Syntaxe : Var nom_variable : type ; Const nom_constante = valeur ; Remarque : Dans la partie déclarative, les variables et les constantes sont caractérisées essentiellement par :  Un identificateur : est un nom attribué à la variable ou à la constante, qui peut être composé de lettres et de chiffres mais sans espaces.  Un type : qui définit la nature et la taille de la variable. Exemple : Var x, y : entier; Const alpha = 0,5 ; Dans cet exemple, nous avons déclaré : - Deux variables (x et y) de type entier, ce type est décrit dans la sous-section suivante. - Une constante (alpha) égale à la valeur 0,5 à titre d’exemple. 4.3. Les types de base Le type d’une variable définit l’ensemble des valeurs que peut prendre la variable, ainsi que l’ensemble des opérations que l’on peut appliquer sur cette variable. Il existe des types simples prédéfinis tels que : entier, réel, caractère et booléen. -8- Chapitre 1 - Introduction aux algorithmes 4.3.1. Type entier C’est un type numérique représentant l’ensemble des entiers relatifs, tels que: -9, 0, 31, …. Les opérations permises sur ce type sont : +, - , *, div (division entière) et mod (modulo ou reste de la division entière). Le mot clé est : entier. Exemple : Var x : entier ; 4.3.2. Type réel C’est un type numérique aussi représentant l’ensemble des nombres réels, tels que : 0.25, - 1.33, 2.5 e+10,…. Les opérations permises sur ce type sont : +, -, * et /. Le mot clé est : réel. Exemple : Var y : réel ; 4.3.3. Type caractère Ce type représente tous les caractères alphanumériques tels que : ′a′, ′A′, ′3′, ′%′, ′ ′, … Les opérations supportées par ce type sont : =, ≠, =. Le mot clé est : caractère. Exemple : Var a : caractère ; 4.3.4. Type booléen Ce type est utilisé dans la logique pour représenter les deux valeurs : vrai et faux. Les opérations prises en charge sont : NON, ET, OU. Le mot clé est : booléen. Exemple : Var b : booléen ; 4.3.5. Chaîne de caractères Ce type représente les mots et les phrases tels que "Algorithmique", "Cours", etc. Le mot clé utilisé est : chaîne Exemple : Var c : chaîne ; Globalement, la partie déclarative d’un algorithme peut être représentée comme suit. -9- Chapitre 1 - Introduction aux algorithmes Exemple : Var x, y : entier ; z, w : réel ; lettre : caractère ; nom : chaîne ; Etat : booléen ; Const n = 100 ; arobase = ′@′ ; mot = "bonjour" ; 5. Conclusion Ce chapitre constitue une initiation aux notions basiques de l’écriture des algorithmes. La syntaxe d’un algorithme, la notion de variable et de constante, ainsi que leurs types sont définis et expliqués à travers des exemples simples. Ceci constitue pour le lecteur un prérequis de base qui lui permettra de comprendre la notion d’instructions algorithmiques dans les prochains chapitres. - 10 - Chapitre 2 - Les instructions simples Chapitre 2 - Les instructions simples 1. Introduction Un algorithme, par définition, est un ensemble d’instructions qui peuvent être simples ou complexes. Dans ce chapitre, on s’intéressera aux instructions simples notamment : les instructions d’affectation, de lecture et d’écriture. 2. L’instruction d’affectation Cette instruction est élémentaire en algorithmique, elle permet d’assigner une valeur à une variable selon la syntaxe suivante : variable ← expression ; Une instruction d’affectation est exécutée comme suit : - évaluation de l’expression située à droite de l’instruction, et - affectation du résultat à la variable située à gauche de l’instruction. L’expression peut être : une constante ( c ← 10 ) une variable ( v ← x ) une expression arithmétique ( e ← x + y ) une expression logique ( d ← a ou b ) Remarque :  Une constante ne figure jamais à gauche d’une instruction d’affectation. Exemple d’instruction fausse : Const z = 1 ; z ← 2 ; « Faux »  Après une affectation, l’ancien contenu d’une variable est substitué (écrasé) par le nouveau contenu. Exemple : Var a : entier ; a←1; a←2; Après la deuxième affectation, la valeur de a est devenue 2 (la valeur 1 est écrasée).  Une instruction d’affectation doit se faire entre deux types compatibles. Exemple : Var x, y : entier ; z : réel ; a, b : caractère ; - 11 - Chapitre 2 - Les instructions simples Instructions correctes Instructions incorrectes x←y; x←z; y←x; x←a; z←x; b←y; a←b; a←z; b←a; Les expressions arithmétiques ou logiques sont composées d’au moins deux termes reliés par un ou plusieurs opérateurs dont on peut distinguer : a) Les opérateurs arithmétiques (par ordre de priorité) : ^ ou ** : Puissance * , / , mod : Multiplication, Division et Modulo + , - : Addition et Soustraction b) Les opérateurs logiques ou booléens : NON : Non logique (négation) ET : Et logique (conjonction) OU : Ou logique (disjonction) NON ET : négation de conjonction NON OU : négation de disjonction c) Les opérateurs de comparaison ou relationnels : > , >= : supérieur et supérieur ou égal < , ) : égal et différent Remarque : Les expressions logiques peuvent être composées des opérateurs logiques et/ou relationnels. Par exemple, (A=10) est Vrai si A est inférieur à 20 et B est égal ou supérieur à 10, et faux sinon. 3. L’instruction de lecture Cette instruction est très primordiale dans un algorithme. Elle permet de lire des valeurs en entrée (input) et les affecter aux variables stockées dans la mémoire. Les valeurs affectées sont souvent des données introduites à partir d’un périphérique d’entrée tel que le clavier. Syntaxe : Lire (var1, var2,…) ; - 12 - Chapitre 2 - Les instructions simples Exemple : Lire(x) : lit et stocke une valeur donnée dans la case mémoire associée à x. Lire(x, y) : lit et stocke deux valeurs, la première dans x et la deuxième dans y. Illustration : Figure 4. Opération de lecture. 4. L’instruction d’écriture Cette instruction est aussi d’une grande importance dans les algorithmes. Elle permet d’écrire en sortie (output) les données résultant d’un traitement effectué par l’algorithme (valeur, texte, …) en les affichant par exemple sur un périphérique de sortie tel que l’écran. Syntaxe : Ecrire (var1, var2, expr1, expr2, …) ; Remarque : Dans le cas d’écriture d’une expression, c'est le résultat d’évaluation de cette expression qui est affiché et non pas l’expression elle-même. Par exemple : Soient deux variables x et y tel que x=5 et y=7, l’instruction : Ecrire (x+y) ; Affiche en sortie le résultat d’addition de x et y (soit 12). - 13 - Chapitre 2 - Les instructions simples Illustration : Figure 5. Opération d’écriture. Exemple d’algorithme contenant les trois instructions précédentes : Algorithme Moyenne_deux_réels Var x, y, z : réel ; Début Ecrire (″Donner la première valeur :″) ; Lire (x) ; Ecrire (″Donner la deuxième valeur :″) ; Lire (y) ; z ← (x + y)/2 ; Ecrire (″La moyenne est : ″, z) ; // On peut remplacer les deux dernières instructions par une seule : Ecrire (″La moyenne est : ″, (x + y)/2 ) ; // dans ce cas on a pas besoin de z Fin Dans cet algorithme, si l’utilisateur introduit 10 pour x et 20 pour y alors l’affichage sera : La moyenne est : 15 5. Conclusion Dans ce chapitre, nous avons présenté les instructions algorithmiques fondamentales à savoir l’affectation, la lecture et l’écriture. Ces trois simples instructions sont incontournables dans l’écriture d’un algorithme et constituent l’un des moyens les plus simples qui permettent au programmeur d’interagir avec son ordinateur à travers à travers des actions d’entrées/sorties. - 14 - Chapitre 3 - Les instructions conditionnelles (les alternatives) Chapitre 3 - Les instructions conditionnelles (les alternatives) 1. Introduction Les algorithmes comportent généralement deux types d’instructions : - Les instructions simples : qui permettent la manipulation des variables telles que l’affectation, la lecture et l’écriture. - Les instructions de contrôle : qui précisent l’enchainement chronologique des instructions simples. C’est en particulier le cas des instructions conditionnelles ou les tests. 2. Structure d’un test Il existe deux formes de test : forme simple (ou réduite) et forme complète. 2.1. Forme simple Dans cette forme, une action qui correspond à une ou plusieurs instructions, est exécuté si une condition est vérifiée. Sinon l’algorithme passe directement au bloc d’instruction qui suit immédiatement le bloc conditionnel. Syntaxe : Si (condition) Alors instruction(s) ; // action Finsi Remarque : La condition évaluée après l’instruction « Si » est une variable ou une expression booléenne qui, à un moment donné, est Vraie ou Fausse. par exemple : x=y ; x = 0 et x < 1 qui doivent être vérifiées en même temps. Pour combiner ces deux conditions, on utilise les opérateurs logiques. Ainsi, la condition x ∈ [0, 1[ pourra s’écrire sous la forme : (x >= 0) ET (x < 1). Cette dernière est appelée une condition composée ou complexe. Exemple (sur la forme complète d’un test) : x←5;y←9; Si (x = y) Alors Ecrire (″x est égale à y ″) ; Sinon Ecrire (″x est différente de y ″) ; Avec cette forme, on peut traiter les deux cas possibles. Si la condition (x=y) est vérifiée, le premier message est affiché, si elle n’est pas vérifiée, le deuxième message est affiché. 3. Tests imbriqués La forme « Si … Alors…Sinon » permet deux choix correspondants à deux traitements différents. Dans d’autres situations, on pourra avoir plus de deux cas ce qui rend cette alternative insuffisante pour traiter tous les cas possibles (voir exemple ci-dessous). La forme complète permet de choisir entre plusieurs actions en imbriquant des formes simples selon la syntaxe ci-dessous. Syntaxe : Si (condition1) Alors instruction(s) 1 ; Sinon Si (condition2) Alors instruction(s) 2 ; Sinon Si (condition3) Alors instruction(s) 3 ; - 16 - Chapitre 3 - Les instructions conditionnelles (les alternatives) … Sinon instruction(s) N ; FinSi FinSi FinSi Exemple : Etat de l’eau Dans les conditions normales de température et de pression, l’eau est sous forme de glace si la température est inférieure ou égale à 0° C, sous forme de liquide si la température est comprise entre 0° C et 100° C et sous forme de vapeur au-delà de 100° C. Ecrivons l’algorithme qui permet de vérifier l’état de l’eau selon sa température. La solution pourrait être comme suit : Algorithme Etat_Eau ; Var t : réel ; Début Ecrire ("Donner la température de l’eau :") ; Lire (t) ; Si (t 0 ET t < 100) Alors Ecrire ("Etat liquide") ; Finsi Si (t >= 100) Alors Ecrire ("Etat gazeux") ; Finsi Fin Cet algorithme est correct mais il évalue les trois conditions qui portent sur la même variable et qui sont exclusives. En effet, si (t = 0 et t < 100) ni (t > 100). Il est donc inutile d’évaluer les deux dernières conditions si la première est vérifiée, ou d’évaluer la dernière condition si la deuxième est vérifiée. Pour éviter ce cas de figure, il sera préférable d’utiliser des tests imbriqués comme suit : … Début Ecrire ("Donner la température de l’eau:") ; Lire (t) ; Si (t 2), peuvent être utilisés pour diverses raisons telles que la création et le traitement des objets 3D par exemple qui nécessitent des tableaux de 3 dimensions au minimum. La déclaration de ce type de tableaux est comme suit : Syntaxe : Tableau nom_tableau [taille1][taille2] … [tailleN] : type ; Exemple : Tableau T : réel ; // un tableau T à 3 dimensions La manipulation d’un tableau à plusieurs dimensions suit le même principe que celle des tableaux à deux dimensions. Ceci s’appuie sur l’utilisation des boucles imbriquées pour parcourir le tableau, de sorte qu’il y aura autant de boucles qu’il y a de dimensions. 5. La recherche dans un tableau 5.1. La notion du drapeau Le drapeau (ou flag en Anglais) est une variable booléenne initialisée à Faux (drapeau baissé). Dès qu’un évènement attendu se produit, la variable change de valeur à Vrai (drapeau levé). Donc, la valeur finale du drapeau permet de savoir si un évènement a eu lieu ou pas. Cela devrait s’éclairer à l’aide d’un exemple extrêmement fréquent : la recherche de l’occurrence d’une valeur dans un tableau. Exemple : En supposant l’existence d’un tableau comportant N valeurs entières. On doit écrire un algorithme qui lit un nombre donné et informe l’utilisateur de la présence ou de l’absence de - 32 - Chapitre 5 - Les tableaux ce nombre dans le tableau. La première étape consiste à écrire les instructions de lecture du nombre N et de parcours du tableau : Tableau Tab[N] : Entier ; Var val, i : Entier ; Début Ecrire ("Entrer la valeur à rechercher :") ; Lire (val) ; Pour i de 0 à N-1 … Finpour Fin Illustration : On suppose que N=6 et les valeurs saisies sont celles figurant dans le schéma suivant : indices : i=0 i=1 i=2 i=3 i=4 i=5 Tab valeurs : 10 22 31 46 5 7 Revenons à l’algorithme, maintenant, il faut combler les points de la boucle (le bloc qui devra contenir les instructions de la recherche). Évidemment, il va falloir comparer « val » à chaque élément du tableau, s’il y a une égalité quelque part, alors « val » fait partie du tableau. Cela va se traduire, bien entendu, par l’instruction conditionnelle « Si … Alors … Sinon ». … Début Ecrire ("Entrez la valeur à rechercher ") ; Lire (val) ; Pour i de 0 à N-1 Si (val = Tab[i]) Alors Ecrire (val, "figure") ; Sinon ? Ecrire (val, "ne figure pas") ; Finsi Finpour Fin - 33 - Chapitre 5 - Les tableaux Illustration : On suppose que la valeur à rechercher (val) est égale à 31 : On peut constater qu’on a deux possibilités : - ou bien la valeur « val » figure dans le tableau, - ou bien elle n'y figure pas. Mais dans tous les cas, l'algorithme ne doit produire qu'une seule réponse, quel que soit le nombre d'éléments du tableau. Or, l'algorithme ci-dessus affiche autant de messages qu'il y a de valeurs dans le tableau. Il y a donc une erreur quelque part. En fait, on ne peut savoir si la valeur recherchée existe dans le tableau ou non que lorsque le parcours du tableau est entièrement accompli. Pour pallier à cette erreur, on doit réécrire l’algorithme en plaçant le test après la boucle et en utilisant cette fois-ci une variable booléenne (drapeau) que l’on appelle « Existe ». Cette variable doit être gérée comme suit : - La valeur de départ de « Existe » doit être évidemment Faux (drapeau baissé). - La valeur de la variable « Existe » doit devenir Vrai (drapeau levé), si un test dans la boucle est vérifié (lorsque la valeur de « val » est rencontrée dans le tableau). mais le test doit être asymétrique, c.à.d. qu’il ne comporte pas de "sinon". Donc l’algorithme correct devrait être comme suit : Tableau Tab[N] : entier ; Var val, i : entier ; existe : booléen ; Début Ecrire ("Entrez la valeur à rechercher ") ; Lire (val) ; existe ← faux ; Pour i de 0 à N-1 Si (val = Tab[i]) Alors existe ← vrai; Finsi Finpour - 34 - Chapitre 5 - Les tableaux Si (existe) Alors Ecrire (val, "fait partie du tableau") ; Sinon Ecrire (val, "ne fait pas partie du tableau") ; Finsi Fin Illustration : En utilisant un drapeau (la variable « Existe ») :  Question ? Réécrire le même algorithme mais cette fois-ci, la boucle de recherche doit être arrêtée dès que la valeur du drapeau change. 6. Le tri d’un tableau Qu’est-ce qu’un tri ? Le tri est une opération consistant à ordonner un ensemble d’éléments suivant une relation d’ordre prédéfinie. Le problème du tri est un grand classique en algorithmique. Trier un tableau numérique c’est donc ranger ses éléments en ordre croissant ou décroissant. Il existe plusieurs algorithmes de tri, parmi lesquels le tri par sélection, tri par insertion, tri à bulles, tri par fusion, etc. Nous illustrons dans ce qui suit deux types de tri, à savoir le tri par sélection et le tri par insertion. 6.1. Tri par sélection Cette technique est parmi les plus simples, elle consiste à sélectionner, pour une place donnée, l’élément qui doit y être positionné. Par exemple pour trier un tableau en ordre croissant, on met en première position le plus petit élément du tableau et on passe à la position suivante pour mettre le plus petit élément parmi les éléments restants et ainsi de suite jusqu’au dernier. - 35 - Chapitre 5 - Les tableaux Exemple : Soit à trier, en ordre croissant, le tableau suivant : 25 10 13 31 22 4 2 18 Nous commençons par la recherche de la plus petite valeur et sa position. Une fois identifiée (dans ce cas, c’est le nombre 2 en 7ème position), nous l’échangeons avec le 1er élément (le nombre 25). Le tableau devient ainsi : 2 10 13 31 22 4 25 18 Nous recommençons la recherche, mais cette fois, à partir du 2ème élément (puisque le 1er est à sa position correcte). Le plus petit élément se trouve en 6ème position (le nombre 4). Nous échangeons donc le 2ème élément avec le 6ème élément : 2 4 13 31 22 10 25 18 Nous recommençons la recherche à partir du 3ème élément (puisque les deux premiers sont maintenant bien placés), Le plus petit élément se trouve aussi en 6ème position (10), en l’échangeant avec le 3ème, ça donnera: 2 4 10 31 22 13 25 18 Nous recommençons maintenant à partir du 4ème élément et de la même façon nous procédons jusqu’à l’avant dernier : 2 4 10 13 22 31 25 18 2 4 10 13 18 31 25 22 2 4 10 13 18 22 25 31 2 4 10 13 18 22 25 31 Algorithmiquement, nous pouvons décrire ce processus de la manière suivante :  Boucle principale : prenant comme point de départ le premier élément, puis le second, etc, jusqu’à l’avant dernier.  Boucle secondaire : à partir de ce point de départ mouvant, nous recherchons jusqu’à la fin du tableau le plus petit élément. Une fois trouvé, nous l’échangeons avec le point de départ. - 36 - Chapitre 5 - Les tableaux Donc, cela s’écrit : Pour i de 0 à 6 posmin ← i ; // posmin est la position du minimum initialisée par i Pour j de (i + 1) à 7 Si (T(j) < T(posmin)) Alors posmin ← j ; Finsi Finpour temp ← T(posmin) ; T(posmin) ← T(i) ; T(i) ← temp ; FinPour 6.2. Tri par insertion Soit à trier un tableau d’éléments en ordre croissant. Le principe de ce type de tri repose à chaque itération sur trois phases : a) On prend le premier élément dans la partie non encore triée du tableau (la clé). b) On cherche la place de la clé dans la partie déjà triée du tableau, en commençant par la droite de cette partie. c) Une fois cette place trouvée, on y insère la clé après qu’on ait décalé vers la droite tous les éléments de la partie triée dont la valeur est plus grande ou égale à la valeur de la clé. Il faut noter qu’initialement, la partie triée est constituée seulement du premier élément du tableau, autrement dit, le processus du tri commence à partir du deuxième élément. Exemple : Soit à trier, en ordre croissant, le même tableau précédent en appliquant le tri par insertion : i=1 25 10 13 31 22 4 2 18 Clé Partie non encore triée - 37 - Chapitre 5 - Les tableaux On décale le 1er élément de la partie triée vers la droite puisque sa valeur est supérieure à la clé. Cette dernière est déplacée à la 1ère position : i=2 10 25 13 31 22 4 2 18 On recommence le processus avec une nouvelle clé. Le 1er élément à droite de la partie triée (25) est décalé vers la droite puisque sa valeur est supérieure à la clé. Le 2 ème élément ne sera pas décalé puisqu’il est inférieur à la clé. Par conséquent, la clé est insérée dans la 2ème position du tableau : i=3 10 13 25 31 22 4 2 18 On ne déplace pas cette clé (31) puisque sa valeur est supérieure à celles des éléments qui la précèdent. i=4 10 13 25 31 22 4 2 18 On décale les deux premiers éléments (31 et 25) vers la droite et la clé est insérée à la 3 ème position : i=5 10 13 22 25 31 4 2 18 On décale tous les éléments de la partie triée vers la droite puisque leurs valeurs sont supérieures à celle de la clé. Cette dernière est déplacée à la 1 ère position : i=6 4 10 13 22 25 31 2 18 La même opération est répétée pour cette clé (2) : i=7 2 4 10 13 22 25 31 18 Les trois éléments (22,25 et 31) sont décalés vers la droite et la clé est déplacée vers la 5ème position : 2 4 10 13 18 22 25 31 Nous obtenons donc un tableau qui est trié en ordre croissant. L’algorithme correspondant à ce type de tri est présenté dans ce qui suit : - 38 - Chapitre 5 - Les tableaux Algorithme Tri_Insertion ; Var i, j, n, clé : Entier; // n est la taille du tableauT T : Tableau d’entiers ; Début Pour i de 1 à n-1 // on commence par le 2ème élément (début de la partie non triée) clé  T[i] ; j  i - 1 ; // indice du 1er élément à droite de la partie triée Tant que ((j >= 0) ET (clé < T[j])) Faire T[j +1]  T[j]; // Décalage j  j - 1; FinTant que T[j +1]  clé; // Insertion de la clé FinPour Fin 6.3. Comparaison Dans l’algorithme de tri par sélection, nous avons dans tous les cas, la boucle interne est exécuté pour i=1, 2, 3 jusqu’à i=(n-1) par conséquent, nous avons (n-1) + (n-2) + (n-3) + … + 1 étant n (n-1) / 2 exécutions. Par exemple, pour un tableau de 100 éléments, la boucle est exécutée 4950 fois dans tous les cas. Dans l’algorithme de tri par insertion, nous avons dans le pire des cas un tableau trié à l’envers (en ordre décroissant dans ce cas), et la boucle interne est exécuté (n-1) + (n-2) + (n-3) + … + 1 fois, étant n (n-1) / 2 exécutions au maximum. Au meilleur des cas, le tableau est trié en ordre voulu (croissant dans ce cas) et la boucle interne ne s’exécutera jamais. En moyenne, le nombre d’exécutions est n (n-1) / 4. Par exemple, pour un tableau de 100 éléments, la boucle est exécutée 4950 fois au maximum et 2475 en moyenne. 7. Conclusion Dans ce chapitre, nous avons vu comment mémoriser et manipuler un ensemble de valeurs représentées par le même nom et identifiées par des numéros à travers la notion du tableau. En fait, un tableau n’est pas un type de données mais plutôt une liste d’éléments d’un type donné. Le problème du tri qui est un grand classique de l’algorithmique, a été abordé par la suite à travers deux algorithmes parmi les plus simples, à savoir le tri par sélection et le tri par insertion. Une comparaison entre les deux algorithmes a été donnée à la fin de ce chapitre. - 39 - Chapitre 6 - Les enregistrements (structures) Chapitre 6 - Les enregistrements (structures) 1. Introduction Nous avons vu dans le chapitre précédent, que les tableaux nous permettent de stocker plusieurs éléments de même type, tel que stocker les notes des étudiants dans un tableau de type réel. Supposons maintenant qu’en plus des notes des étudiants, nous voulons stocker aussi leurs informations (nom, prénom, matricule, …). Il nous faut dans ce cas de figure, une autre structure qui permet de stocker des données de différents types. Donc, une nouvelle structure appelée enregistrement est plus adaptée dans ce cas. 2. Définition Un enregistrement (ou structure) permet de regrouper un ensemble de données de différents types sous le même nom (un seul objet). Il est défini par un ensemble d’éléments appelés champs. Ces derniers sont des données élémentaires ou composées qui peuvent être de types différents. 3. Déclaration et manipulation La syntaxe de déclaration d’une structure est la suivante : Structure nom_structure champ1 : type1 ; champ2 : type2 ;... champN : typeN ; FinStructure ; Tel que « nom_structure » est le nom d’enregistrement défini par l’utilisateur. « champ1, champ2, …, champN » sont les variables membres de la structure déclarée. Exemple : Structure Etudiant num : entier ; nom : chaîne ; moyenne : réel; FinStructure ; Par la suite, des variables de type Etudiant peuvent être déclarées comme suit : Var x,y : Structure Etudiant ; - 40 - Chapitre 6 - Les enregistrements (structures) La manipulation d’une variable structure se fait par champ (membre) et l’accès à une information contenue dans un champ se fait en précisant le nom de la variable structure suivie du champ concerné. Les deux séparés par un point. Exemple : x.num ←123 ; // affecte le nombre 123 au champ num Lire (x.nom) ; // lire le champ nom x.moyenne ←13.5 ; // affecte le nombre 13.5 au champ moyenne 4. Tableau de structures Il est possible de déclarer un tableau dont les éléments sont des structures avec la syntaxe suivante : Tableau nom_tableau [taille] : Structure nom_structure ; Exemple : Tableau T : Structure Etudiant ; Donc, T est un tableau de 10 éléments de type structure (« Etudiant » dans ce cas). L'accès à un champ d’élément i d’un tableau de structure se fait comme suit : nom_tableau [i].champ Par exemple, les instructions : T.nom ← "Mohamed" ; T.num ← 1 ; et T.moyenne ← 12.5 ; affectent respectivement la valeur entière « 1 », la chaîne de caractères « Mohamed » et la valeur réelle « 12.5 » aux champs « num », « nom » et « moyenne » du 1er élément du tableau T. Illustration : indices : i=0 i=1 … i=9 T num : 1 num : num : Eléments : nom : Mohamed nom : … nom : moyenne : 12.5 moyenne : moyenne : De même, les instructions : Ecrire (T.num) ; Ecrire (T.nom) ; Ecrire (T. moyenne) ; Affichent les contenues des trois champs du 1er élément du tableau T. - 41 - Chapitre 6 - Les enregistrements (structures) 5. Structure membre d’une autre structure Une structure peut figurer parmi les champs d'une autre structure. Dans ce cas, elle doit être déclarée avant la structure qui la contient. Exemple : Structure Date jour, mois, annee : entier ; Finstructure ; Structure Compte Ncpt: entier; nom: chaine ; DtOuverture : Date ; Finstructure ; Où « DtOuverture » est une variable structure de type « Date », champ de la structure « Compte ». Donc, la structure « Date » est déclarée obligatoirement avant la structure « Compte ». Lorsqu'un champ d'une structure est lui-même une structure, l’accès à ce champ se fait comme suit : variable_structure.variable_sous_structure.champ Par exemple : c.DtOuverture.annee ← 2019 ; affecte la valeur 2019 au champ année de l’enregistrement « DtOuverture » qui est lui-même un champ de l’enregistrement « c ». Tel que « c » est une variable de type « Compte ». Dans le cas d'un tableau, l'accès se fait comme suit : nom_tableau[indice].variable_sous_structure.champ Par exemple : T[i].DtOuverture.annee ← 2019 ; Où T[i] fait référence au ième élément du tableau T de type « Compte ». 6. Conclusion Nous avons vu dans le cinquième chapitre que les tableaux sont très pratiques, cependant ils ne permettent pas de répondre à tous les besoins de stockage tels que le regroupement de plusieurs données de types différents en un seul objet. A cet effet, la notion de structure (ou d’enregistrement) abordée dans le présent chapitre permet de pallier ce problème en créant un nouveau type permettant le stockage des données de types différents ou non. Un enregistrement qui est composé de plusieurs champs où chaque champ correspond à une donnée, constitue la brique de base pour les structures de données telles que les listes, les piles et les files qui ne font pas l’objet d’étude dans ce polycopié. - 42 - Chapitre 7 - Les fonctions et les procédures Chapitre 7 - Les fonctions et les procédures 1. Introduction La fiabilité, la lisibilité et la réutilisabilité des programmes, reposent sur l’utilisation des sous-programmes. Ces derniers permettent : - La réduction de la taille des programmes : il est possible de déterminer les blocs analogues, les substituer par un sous-programme, ensuite l’appeler dans des points déterminés au niveau du programme principal. - L’organisation du code : le problème initial peut être découpé en sous-problèmes (modules) où chacun sera résolu par un sous-programme. Exemple : Codage en base b Un entier positif en base b est représenté par une suite de chiffres (c n cn−1... c1c0)b où les ci sont des chiffres de la base b (0 ≤ ci < b). L’équivalent décimal de ce nombre est : cnbn + cn-1bn-1 + … + c1b1 + c0b0 = ∑𝑛𝑖=0 𝑐𝑖 𝑏𝑖 On suppose que le nombre x est représenté par un tableau de chiffres (code) en base b ; par exemple si b = 2 et code = [1,0,1], alors en base 10 le nombre entier x correspondant vaudra 1×22 + 0×21 + 1×20 = 4+0+1 = 5. Etant donné code et b, l’algorithme qui permet de calculer x en base 10 est le suivant : x←0; Pour i de 0 à L-1 // L est la longueur du code x ← x + code[i]*b^(L-1-i); Supposons que l’on veut calculer successivement la valeur décimale x des nombres (123)5 et (123)8, on devra donc recopier deux fois l’algorithme ci-dessus. b←5; b←8; code ← [1,2,3] ; code ← [1,2,3] ; x←0; x←0; Pour i de 0 à L-1 Pour i de 0 à L-1 x ← x + code[i]*b^(l-1-i); x ← x + code[i]*b^(l-1-i); - 43 - Chapitre 7 - Les fonctions et les procédures Dans la pratique, il n’est pas souhaitable d’écrire deux fois le même programme, d’autant plus, si celui-ci nécessite de très nombreuses lignes de code source. Pour améliorer la réutilisabilité de l’algorithme la solution est d’encapsuler le code à répéter au sein d’un sous- programme. 2. La notion de sous-programme Un sous-programme est une portion de code analogue à un programme, destiné à réaliser une certaine tâche à l’intérieur d’un autre programme. Il est identifié par un nom unique et un bloc d’instructions qui peut être exécuté plusieurs fois par des appels. Un appel est une instruction qui fait partie d’un autre programme ou sous-programme appelé le (sous-) programme appelant. Pour résumer, un sous-programme est utilisé pour deux raisons essentielles : - Lorsqu’une tâche est répétée plusieurs fois : on écrit un sous-programme pour cette tâche et l’on appelle à chaque endroit où l’on en a besoin c.à.d. on évite de réécrire le même code à plusieurs endroits dans le même programme. - Pour réaliser la structuration d’un problème en sous-problèmes : on divise le problème en sous-problèmes pour mieux le contrôler (diviser pour régner). Il existe deux types de sous-programmes : les fonctions et les procédures. Cependant, avant de détailler ces deux concepts, il sera utile de définir quelques notions utiles. 2.1. La portée d’une variable Dans cette sous-section, nous illustrons une notion appelée portée d’une variable. L'idée principale est qu'il est possible d'avoir deux variables différentes avec le même nom toutefois qu'elles ont des portées différentes. Le cas le plus connus que l'on peut citer, est qu'une variable définie au niveau du programme principal (celui qui résout le problème initial) est appelée variable globale et sa portée est totale, par conséquent, tout sous-programme du programme principal peut utiliser cette variable. Alors qu'une variable définie au sein d'un sous-programme est appelée variable locale dont la portée est limitée au sous-programme dans lequel elle est déclarée. Remarque : Si l’identificateur (le nom) d'une variable locale est identique à celui d’une variable globale, cette dernière est localement masquée. Autrement dit, la variable globale devient inaccessible dans le sous-programme contenant la variable locale de même nom. - 44 - Chapitre 7 - Les fonctions et les procédures Exemple : Supposons qu’une partie de notre programme sera le sous-programme suivant : Algorithme Secondaire ; Var x : entier ; // variable locale Début x←3; Ecrire (x, y) ; Fin Supposons maintenant que nous appelons ce sous-programme « Secondaire » depuis une autre partie du programme « Principal » qui utilise également deux variables globales : Algorithme Principal ; Var x, y : entier ; // variables globales Début x←5;y←8; … ; // Appel au sous-programme Secondaire Ecrire (x, y) ; Fin L’exécution de ce programme peut être illustrée comme suit : Programme Espace mémoire Résultat d’affichage -Principal Début Appel au sous- … programme 5,8 x=5 … Fin y=8 -Secondaire x=3 Début 3,8 … Fin Dans cet exemple, la variable « x », ayant la valeur 5 dans le programme principal, est une variable globale. Une autre variable qui porte le même nom « x » est utilisée au niveau du programme secondaire ayant comme valeur 3. Cet variable locale a masqué la variable globale « x » au niveau du programme secondaire, par conséquent, l’affichage de « x » au niveau de ce sous-programme correspond à la valeur 3. Par contre, la variable globale y est quant à elle accessible, ce qui justifie l’affichage de la valeur 8 au niveau du sous- programme. - 45 - Chapitre 7 - Les fonctions et les procédures 2.2. Les paramètres Les paramètres d'un sous-programme sont un ensemble de variables locales (paramètres formels) associées à un ensemble de variables ou constantes du (sous-) programme appelant (paramètres effectifs). Remarque : - Un paramètre est une variable locale, donc il admet un type. - L’appel d’un sous-programme possédant un ou plusieurs paramètres, implique une association entre ces paramètres et les paramètres effectifs du programme (ou sous- programme) appelant, respectivement de même type. Par exemple, si le sous-programme Racine permet de calculer la racine carrée d'un réel : - Ce sous-programme admet un seul paramètre de type réel positif. - Le programme appelant Racine doit fournir le réel positif dont il veut calculer la racine carrée, cela peut être une variable (Racine (y)) ou une constante (Racine (9)). 2.3. Le passage de paramètres L'association entre les paramètres effectifs et les paramètres formels est appelé passage de paramètres. Il existe deux types de passage de paramètres : - Le passage par valeur. - Le passage par référence (ou adresse). Dans le premier type, la valeur du paramètre effectif est affectée (copiée) au paramètre formel correspondant. Sachant que les paramètres formels ne sont que des variables locales de la fonction. Ce type de passage sera illustré dans la section qui suit. Dans le second type, c’est l’adresse du paramètre effectif qui est affectée au paramètre formel correspondant. Ceci rend possible au sous-programme d’accéder directement à l’adresse de la variable concernée (le paramètre effectif) et par conséquent la modifier si nécessaire. Ce type de passage nécessite d’utiliser la notion des pointeurs. Remarque : Une illustration du passage de paramètre par valeur est donnée dans l’exemple 3 de la section 4. Le passage de paramètre par adresse sera illustré dans le chapitre suivant. 3. Les fonctions Une fonction est un sous-programme qui admet un nom, un type et des paramètres. Une fonction admet un type et retourne toujours un résultat. - 46 - Chapitre 7 - Les fonctions et les procédures 3.1. Définition d’une fonction On définit une fonction comme suit : Fonction nom_fonction (paramètres : types) : type de la valeur retournée Var var1, var2,…: types; // variables_locales Début instructions de la fonction ; Retourner (résultat) ; // (au moins une fois) Fin Où :  Les paramètres sont en nombre fixe (n≥0)  Le type de la valeur retournée est le type de la fonction.  La valeur de retour (ou le résultat) est spécifiée par l'instruction Retourner. 3.2. Appel d’une fonction On fait appel à une fonction comme suit : var ← nom_fonction (paramètres) ; Où les paramètres d’appel peuvent être des variables, des constantes ou même des résultats d’une autre fonction. Remarque : A la définition ou à l’appel d’une fonction, les parenthèses sont toujours présentes même lorsqu'il n'y a pas de paramètres. Exemple 1 : Soit l’algorithme A qui calcule la valeur absolue d’un entier en utilisant une fonction : Algorithme A ; Var a, b : entier ; Fonction Abs (n : entier) : entier Var valabs : entier Début Si (n >= 0) alors valabs ← n ; Sinon valabs ← -n ; FinSi Retourner valabs ; Fin Passage de paramètre par valeur : la valeur de la variable a est copiée dans la variable n. Début Ecrire (" Donner une valeur ") ; Lire (a) ; b ← Abs(a) ; Ecrire (b) ; Fin - 47 - Chapitre 7 - Les fonctions et les procédures Lors de l’exécution de la fonction Abs(), il y a une association entre le paramètre effectif a et le paramètre formel n d’où la valeur de a est copiée dans n. Ce type d’association s’appelle passage de paramètre par valeur. 4. Les procédures Une procédure est un sous-programme qui admet également un nom et des paramètres mais ne retournant aucun résultat. 4.1. Définition d’une procédure On définit une procédure comme suit : Procédure nom_procédure (paramètres : types) Var var1, var2,…: types; // variables_locales Début instructions de la procédure ; Fin 4.2. Appel d’une procédure L’appel d’une procédure se fait comme suit : nom_procédure (paramètres) ; Exemple 2 : Soit l’algorithme B calculant la valeur absolue d’un entier mais cette fois-ci en utilisant une procédure : Algorithme B ; Var a : entier ; Procédure Abs (n : entier) Début Si (n >= 0) alors Ecrire n ; Sinon Ecrire -n ; FinSi Fin Début Ecrire (" Donner une valeur ") ; Lire (a) ; Abs(a) ; Fin - 48 - Chapitre 7 - Les fonctions et les procédures Exemple 3 : Soit un algorithme utilisant une procédure comme suit : Algorithme C ; Var x : entier ; Procédure Modif (x : entier) Début x ← x + 1 ; Fin Début x←1; Ecrire ("Valeur de x avant l’appel :", x) ; Modif (x) ; Ecrire ("Valeur de x après l’appel :", x) ; Fin L’exécution de l’algorithme C peut être illustrée comme suit : Programme Espace mémoire Résultat d’affichage Algorithme C x 1 Début Valeur de x avant l’appel : 1 x←1; Ecrire (…) ; Valeur de x après l’appel : 1 Modif (x) ; Ecrire (…) ; Fin Appel avec passage de paramètre par valeur Procédure Modif() x 12 Début x←x+1; Fin Lorsqu’on passe un paramètre à une fonction (ou à une procédure), cette dernière ne peut pas modifier la variable. La variable est automatiquement recopiée et la fonction travaille sur une copie de la variable. La modification de la copie n’entraîne pas une modification de la variable originale. C’est ce qu’on appelle le passage de paramètre par valeur. - 49 - Chapitre 7 - Les fonctions et les procédures 5. Fonctions et procédures récursives La récursivité est une méthode de description d’algorithmes qui permet à une fonction (ou procédure) de s’appeler elle-même directement ou indirectement. 5.1. Exemple illustratif On peut définir la factorielle d’un nombre N non négatif de deux manières : Définition non récursive : N ! = N * N-1 * …* 2 * 1 Définition récursive : N ! = N * (N – 1) ! et 0 ! = 1 Par conséquent, deux solutions sont possibles pour le calcul de la factorielle. a) Solution itérative : Fonction FACT ( n : entier ) : entier Var i, F: entier ; Début Si (n = 0) alors F ← 1 ; Sinon F←1; Pour i de 2 à n F ← F * i; Finpour Retourner F; Finsi Fin b) Solution récursive : Fonction FACT ( n : entier ) : entier Début Si (n=0) alors Retourner 1 ; Sinon Retourner n * fact (n-1) ; // Appel récursif de la fonction FACT Finsi Fin 5.2. Interprétation Une procédure ou une fonction récursive doit comporter une condition d’arrêt (n=0 dans l’exemple étudié ci-dessus). Cette condition empêche des appels récursifs sans arrêt. Généralement, la condition d’arrêt se présente sous la forme d’une instruction « Si… - 50 - Chapitre 7 - Les fonctions et les procédures Alors…Sinon » qui permet de stopper la récurrence si la condition d’arrêt est satisfaite. Dans le cas contraire, la fonction ou la procédure continue à exécuter les appels récursifs. D’autre part, le paramètre de l’appel récursif doit converger toujours vers la condition d’arrêt. Un processus récursif remplace en quelque sorte une boucle, ainsi tout processus récursif peut être également formulé en tant qu’un processus itératif. 5.3. Mécanisme de fonctionnement Considérons, à titre d’exemple, le calcul de la factorielle de 4 en appliquant la fonction récursive FACT(). Pour calculer FACT(4), il faut calculer FACT(3). Pour calculer FACT(3), il faut calculer FACT(2). Pour calculer FACT(2), il faut calculer FACT(1). Pour calculer FACT(1), il faut connaître FACT(0), ce dernier vaut 1. Ensuite, on revient à rebours pour terminer le calcul pour 1, 2, 3 puis 4. Il y a donc autant d’occurrences de paramètre n et d’appel récursif que de niveaux de récursivité. A chaque niveau, un nouvel environnement, comprenant les paramètres et les variables locales de la fonction, est créé. Cette gestion des variables est invisible à l’utilisateur et effectuée automatiquement par le système si le langage admet la récursivité. Une illustration de ce mécanisme est donnée dans la figure 6. FACT(4) = 24 Si (4=0) alors … Sinon Retourner 4 * FACT (3) ; 6 Si (3=0) alors … Sinon Retourner 3 * FACT (2) ; 2 Si (2=0) alors … Sinon Retourner 2 * FACT (1) ; 1 Si (1=0) alors … Sinon Retourner 1 * FACT (0) ; 1 Si (0=0) alors Retourner 1 ; 6. Conclusion Figure 7. Calcul de la factorielle par récursivité. - 51 - Chapitre 7 - Les fonctions et les procédures 6. Conclusion La notion du sous-programme est très importante en programmation. Elle résulte de la décomposition du programme initial en de plus petites unités ou parties réutilisables qui sont ensuite appelées le moment opportun par le programme principal. Un sous-programme évite la répétition inutile de code et permet de clarifier le programme. En algorithmique, un sous- programme correspond à une fonction ou à une procédure dont la description et le mécanisme de fonctionnement sont présentés plus haut dans ce chapitre. Aussi, une initiation à la notion de récursivité, une des outils puissants de la programmation, a été donnée à la fin de ce chapitre. Le prochain chapitre traite l’un des concepts utiles et indispensables au passage de paramètres par adresse (ou référence), c’est le concept de pointeur. - 52 - Chapitre 8 - Les pointeurs Chapitre 8 - Les pointeurs 1. Introduction Lorsqu’une variable est déclarée et ce, quel que soit le langage de programmation, le compilateur réserve, à une adresse donnée en mémoire, l’espace nécessaire au contenu de cette variable. Donc, toute variable possède : - Un identificateur (nom), - Une valeur (donnée), - Une adresse en mémoire. Une donnée peut s’étaler sur plusieurs octets, donc occuper une plage d’adresses (par exemple 2 octets pour un entier, 4 ou 8 octets pour un réel, plus encore pour une chaîne). Exemple : Var n : entier ; // déclaration d’un entier (sur 2 octets) n ← 5 ; // affectation de la valeur 5 à n Dans cet exemple, le nom de la variable c’est n, la valeur c’est 5 et l’adresse c’est son emplacement dans la mémoire. Espace réservée à l’entier n pour stocker sa valeur 5 Variable n Figure 8. Représentation d’une variable en mémoire. On peut donc accéder à une variable de deux façons :  par son identificateur,  par l'adresse mémoire à partir de laquelle elle est stockée (pointeur). - 53 - Chapitre 8 - Les pointeurs 2. Notion de pointeur 2.1. Définition Un pointeur est une variable qui contient l’adresse d’une autre variable. Le pointeur pointe sur une autre variable dont il contient l’adresse mémoire, cette dernière étant dite variable pointée. Si l’on affiche le contenu d’un pointeur, on obtient une adresse qui est celle de la variable pointée, tandis que si l’on affiche le contenu de la variable pointée, on obtient la valeur associée à cette dernière. Un pointeur est une variable. De ce fait, elle doit être déclarée, dispose elle-même de sa propre adresse en mémoire, et se voit définir un type. Le type d’un pointeur ne décrit pas ce qu’il contient (c’est une adresse, donc en principe d’une longueur de 32 ou 64 bits selon les architectures) mais le type de la variable qu’il pointe. Un pointeur sur une variable de type réel devrait donc être déclaré avec un type réel. Pointeur p 5 Variable n Figure 9. Le pointeur et la variable pointée en mémoire. Dans ce qui suit, nous décrivons comment déclarer et manipuler un pointeur avec quelques cas d’applications par la suite. 2.2. Opérations sur les pointeurs 2.2.1. Déclaration En algorithmique, un pointeur est déclaré comme suit : nom_pointeur : pointeur sur type ; ou nom_pointeur : *type ; // où type est le type de l’élément pointé. Dans ce qui suit, nous utilisons la deuxième syntaxe qui est plus proche du langage C. - 54 - Chapitre 8 - Les pointeurs Par exemple : p : *entier ; // p est un pointeur vers un entier (il contient l’adresse d’un entier) 2.2.2. Initialisation Lorsqu’un pointeur ne pointe aucune variable, il faut l’initialiser avec la constante symbolique NIL. Un pointeur non initialisé pointe n’importe quoi dans la mémoire. Par exemple : p : *entier ; p ← NIL ; // p est un pointeur qui ne pointe rien 2.2.3. Accès aux données L’accès aux données se fait en utilisant les deux opérateurs suivants : * : opérateur unaire qui permet de déréférencer un pointeur (accéder directement à la valeur de l’objet pointé). & : opérateur unaire permettant d’obtenir l’adresse d’une variable. Il convient de noter que ces opérateurs sont les mêmes utilisés en langage C, d’autres opérateurs peuvent être rencontrés par le lecteur tels que ^ et @ en Pascal à titre d’exemple. Exemple : Algorithme Exemple_pointeur ; Var x : entier ; p1, p2 : *entier ; Début x←3; p1 ← &x ; // p1 contient l’adresse de x p2 ← NIL ; // p2 ne contient aucune adresse Ecrire ("Le contenu de la variable pointé par p1 est :", *p1) ; *p1 ← 5 ; // modification de x à travers p1 Ecrire ("x=", x, "*p1=", *p1) ; p2 ← p1 ; // affectation de l’adresse contenue dans p1 à p2 Ecrire ("Le contenu de la variable pointé par p2 est :", *p2) ; Fin L’exécution de cet algorithme donne : Le contenu de la variable pointé par p1 est : 3 x=5 , *p1=5 Le contenu de la variable pointé par p2 est : 5 - 55 - Chapitre 8 - Les pointeurs Remarque : Avant toute utilisation, un pointeur doit être initialisé :  par la valeur générique NIL, par exemple p ← NIL ;  par l'affectation de l'adresse d'une autre variable, par exemple p ← &v;  par allocation dynamique d'un nouvel espace-mémoire. 3. Allocation dynamique Nous avons vu dans la section précédente qu’un pointeur reçoit l’adresse d’une variable qui existe déjà par affectation. Il est aussi possible de réserver un emplacement mémoire pour une donnée pointée directement. Dans ce cas, on peut créer un pointeur sur un entier par exemple, et réserver un espace mémoire (qui contiendra cet entier) sur lequel la variable pointeur pointera. C’est le principe de l’allocation dynamique de mémoire. On peut employer la syntaxe suivante : pointeur ← nouveau type ; Le type doit bien entendu être celui de la valeur qui sera contenue à l’emplacement mémoire alloué. Après cette instruction, le pointeur reçoit l’adresse mémoire de la zone réservée. En cas d’échec (plus de mémoire disponible par exemple) il reçoit la valeur NIL. Exemple : Dans l’algorithme qui suit, un pointeur « p » sur un entier est déclaré. Pour placer une valeur entière dans la zone mémoire pointée, il faut d’abord réserver l’emplacement nécessaire. Puis on accède à l’élément pointé et on y place un entier. Algorithme allouer ; Var p : *entier Début p ← nouveau Entier ; // allocation d’un espace mémoire dont l’adresse est affectée à p *p ← 12345 ; // affectation d’un entier Ecrire ("Le contenu de p est :", *p) ; Fin Quand une zone mémoire est allouée dynamiquement, elle reste occupée tout le temps de l’existence du pointeur. Sans rien d’autre, la mémoire est récupérée uniquement à la sortie du programme. Il est aussi facile de libérer un espace alloué de la mémoire dès que le ou les pointeurs ne sont plus utiles. Pour ceci on applique la syntaxe suivante : Libérer pointeur ; - 56 - Chapitre 8 - Les pointeurs Exemple : Dans l’algorithme qui suit, un pointeur « p » sur un entier est déclaré. Pour placer une valeur entière dans la zone mémoire pointée, il faut d’abord réserver l’emplacement nécessaire. Puis on accède à l’élément pointé et on y place un entier. Algorithme libérer ; Var p : *entier Début p ← nouveau Entier ; *p ← 12345 ; Ecrire ("Le contenu de p est :", *p) ; Libérer p ; // libérer l’espace mémoire pointé par p p ← NIL ; // réinitialiser p Fin Quand on libère un pointeur, on libère la zone mémoire sur laquelle il pointait, cette zone redevient disponible pour toute autre utilisation. Après chaque libération, il est préférable de réinitialiser le pointeur par la valeur NIL, et de penser à tester le pointeur avant de l’utiliser. Dans le cas où l’adresse de la zone mémoire libérée est conservée dans un autre pointeur, il faut faire attention au fait que ce pointeur pointe sur une zone éventuellement réaffectée à autre chose. Y accéder risque de fournir une valeur arbitraire, y écrire risque d’occasionner des problèmes, voire des plantages. 4. Application des pointeurs Les applications des pointeurs sont nombreuses, à titre d’exemple en langage C : - Une fonction ne peut pas retourner plus d’une valeur, un tableau ou un enregistrement. En utilisant un pointeur, ceci est possible en retournant l’adresse de l’ensemble ou de la structure des données à travers un pointeur. - Les tableaux se manipulent très facilement via des pointeurs, puisqu’il est possible de faire des calculs sur les adresses : +1 va au contenu de l’adresse suivante, et ainsi de suite. - Les pointeurs offrent la possibilité d’utiliser des structures de données plus complexes telles que listes chainées, les arbres, etc. - Le passage de paramètres par adresse n’est possible aussi que par l’utilisation des pointeurs où un sous-programme peut modifier le contenu d’une case mémoire à l’adresse passée via un pointeur (voir l’exemple suivant). - 57 - Chapitre 8 - Les pointeurs Exemple : Nous reprenons dans ce qui suit le même exemple vu dans le chapitre précédent concernant le passage de paramètres en utilisant le deuxième mode : passage par adresse. Algorithme D ; Var x : entier ; Procédure Modif (px : *entier) // Procédure utilisant un pointeur comme paramètre local Début *px ← *px + 1 ; // le contenu pointé par px est modifié Fin Passage de paramètre par adresse : l’adresse de la variable x est affectée au pointeur px. Début x←1; Ecrire ("Valeur de x avant l’appel :", x) ; Modif (&x) ; Ecrire ("Valeur de x après l’appel :", x) ; Fin L’exécution de l’algorithme D peut être illustrée comme suit : Programme Espace mémoire Résultat d’affichage Algorithme D Début x 12 x←1; Valeur de x avant l’appel : 1 Ecrire (…) ; Modif (&x) ; Valeur de x après l’appel : 2 Ecrire (…) ; Fin Appel avec passage de paramètre par adresse Procédure Modif() Début px (&x) *px ←*px + 1 ; Fin Lorsqu’on passe l’adresse d’une variable à une fonction (ou à une procédure), cette dernière peut modifier directement cette variable à travers le pointeur contenant son adresse. Donc l’accès au contenu pointé (*px) est équivalent à l’accès à la variable (x) dans ce cas. La modification se fait directement sur la variable originale. C’est le passage de paramètre par adresse. - 58 - Chapitre 8 - Les pointeurs 5. Conclusion Dans ce dernier chapitre de la partie « cours », nous avons présenté la notion des pointeurs avec des exemples sur leur utilisation. Le lecteur est initié aussi au mécanisme de gestion dynamique de mémoire à travers les opérations d’allocation et de libération. A la fin de ce chapitre, un survol sur les principales applications des pointeurs notamment en langage C a été présenté dans lequel le mode de passage de paramètres par adresse a été pris comme exemple d’application. - 59 - Partie II - Exercices corrigés - 60 - Exercices Série 1 : Initiation aux algorithmes Exercice 1 Soit l’algorithme suivant : Algorithme A ; Var a, b, c : entier ; Début a5 ; ba+1 ; ca+b ; Fin a) Expliquer chaque ligne, mot et symbole dans cet algorithme. b) Sur la base de cette explication, ajouter des commentaires à cet algorithme. c) A quoi servent ces commentaires ? Est-ce qu’ils sont obligatoires ? d) Dérouler l’algorithme et donner les valeurs des variables a, b et c. Exercice 2 Soit l’algorithme suivant : Algorithme B ; Var a, b, c, d : entier ; Début Ecrire (″Donner a et b″) ; Lire (a, b) ; ca+b ; da*b ; Ecrire (c, d) ; Fin a) Que fait cet algorithme ? b) Dérouler l’algorithme pour a=5 et b=6. c) Même question pour a=6 et b=5. - 61 - Exercices Exercice 3 Soit l’algorithme suivant : Algorithme C ; Var x,y :entier ; Début Ecrire (Donner x, y) ; Lire (x,y) ; x  y+1 ; z  z+x ; Ecrire (‘x,z’) ; Fin a) Corriger l’algorithme s’il y a des erreurs. b) Dérouler l’algorithme pour x=9 et y=3. Exercice 4 Soit l’algorithme suivant : Algorithme D ; Var a, b, c : entier ; Début Ecrire (donner a et b) ; Lire (‘a, b’) ; ca*a ; db*b ; Ecrire (c, d) ; Fin a) L’algorithme contient-il des erreurs ? b) Dérouler l’algorithme pour a=5 et b=7 et déduire qu’est-ce qu’il fait. Exercice 5 Corriger l’algorithme suivant, s’il le faut, et donner son résultat : Algorithme A ; Var x, y, z, s : entier ; Début x ← 10 ; y ← 15 ; - 62 - Exercices z ← 20 ; m ← (x + y + z) / 2 ; Ecrire (m) ; Ecrire (x + y + z / 2) ; Fin Exercice 6 a) Quel résultat produira-t-il le déroulement de l’algorithme suivant ? Algorithme B ; Var val, double, triple : entier ; Début val ← 1000 ; double ← val * 2 ; triple ← val * 3 ; Ecrire val ; Ecrire double ; Ecrire triple ; Fin b) Proposer une simplification de cet algorithme en produisant le même résultat. Exercice 7 Supposons que l’on veut afficher à l’écran de l’utilisateur le message « Bonjour à tous ». a) Essayer d’écrire l’algorithme correspondant. b) Quelle est la sortie (output) de cet algorithme ? et l’entrée (input) ? c) Quelles sont les instructions à utiliser pour manipuler les entrées (et les sorties) d’un algorithme ? d) Reformuler votre algorithme pour qu’il y ait une entrée et une sortie. - 63 - Exercices Série 2 : Instructions algorithmiques de base Exercice 1 a. Ecrire un algorithme qui permet de lire un nombre (donné par l’utilisateur), puis il calcule et affiche son carré. b. Même question pour calculer et afficher le cube, ensuite l’inverse de ce nombre. Exercice 2 a. Ecrire un algorithme qui permet de lire les notes de trois matières ensuite il calcule et affiche leur moyenne. b. Modifier l’algorithme dans le cas où les matières ont des coefficients qui doivent être donnés avec les notes. Exercice 3 Ecrire un algorithme qui permet de lire deux variables numériques a et b et de les afficher avant et après leur permutation. Par exemple, avant : a=5 et b=7, après : a=7 et b=5. Exercice 4 Proposer un algorithme qui réalise la permutation de deux variables numériques sans avoir utiliser une troisième variable. - 64 - Exercices Série 3 : Les instructions conditionnelles Exercice 1 Ecrire un algorithme qui permet d’afficher la valeur absolue d’un nombre donné. Exercice 2 Ecrire un algorithme qui permet de déterminer si un entier donné est pair ou impair. Exercice 3 Ecrire un algorithme qui demande trois lettres à l’utilisateur, et l’informe ensuite si leur ordre de lecture et le même que l’ordre alphabétique. Exercice 4 a) Écrire un algorithme qui lit trois variables au clavier et affiche le maximum des trois. b) Même question pour plus de trois variables. Exercice 5 a) Ecrire un algorithme qui demande deux nombres à l’utilisateur et l’informe ensuite si leur produit est négatif ou positif mais sans le calculer. (On laisse de côté le cas où le produit est nul). b) Même question en incluant cette fois-ci le cas où le produit peut être nul. Exercice 6 Ecrire un algorithme qui permet de lire un numéro du jour de la semaine (numéro entre 1 et 7) et d’afficher le nom du jour correspondant. Par exemple, le dimanche correspond au numéro 1. - 65 - Exercices Série 4 : Les instructions itératives Exercice 1 Donner les affichages produits par l'exécution des algorithmes suivants : Algorithme 1 : Var i : entier ; Début Pou

Polycopié Algorithmique L1 PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue