Cours AlgoFHG

Ministre de lEnseignement Suprieur, de la Recherche Scientifique et de la Technologie

Direction Gnrale des tudes Technologiques *****

Institut Suprieur des tudes Technologiques de Kef Dpartement INFORMATIQUE

*****

Matire : Algorithmique Niveau 1

Mots-cls du Support

Introduction lAlgorithmique, les Structures Simples, les Actions Simples, les Types numrs, les Actions Alternatives, les Actions Itratives, les Tableaux

Simples, les Tableaux Multidimensionnels, les Chanes de Caractres, les Algorithmes de Recherche, le Tri, la Programmation Procdurale, les Fonctions, les

Procdures etc.

Support de cours adress aux tudiants du Premier Niveau (Tronc commun) ISETs

Enseignant : Mossaab BOUKHCHIM

Anne Universitaire : 2005-2006

Algorithmique Niveau 1

2/102

Sommaire

Fiche de prsentation 5

But du cours et objectifs gnraux 6

Dcomposition des objectifs gnraux en objectifs spcifiques 8

Chapitre 1: Introduction lAlgorithmique 19

I. Dfinitions 19

II. Le Matriel informatique 19

III. Les Logiciels 19

IV. La Mthodologie Suivre 20

V. La Dmarche 21

VI. Algorithme et Algorithmique 23

Chapitre 2 : Les structures de donnes Notion de Base 27

I. Prsentation Sommaire de la Structure dun Algorithme 27

II. Notion de Variable 28

III. Notion de Type 28

IV. Notion de Constante 29

Chapitre 3 : Les structures de donnes Les types simples 31

I. Rappel 31

II. Le Type Entier 31

III. Le Type Rel 33

IV. Le Type Caractre 34

V. Le Type Boolen ou Logique 36

Chapitre 4 : Les actions simples 40

I. Introduction 40


3/102

II. Laction de Lecture 40

III. Laction dcriture 41

IV. Laffectation 44

Chapitre 5 : Les structures conditionnelles 48

I. Problmatique 48

II. Structure Conditionnelle un Choix 48

III. Structure Conditionnelle deux Choix 49

IV. Structure Conditionnelle Imbrique 50

V. Structure Conditionnelle Choix Multiple 51

Chapitre 6 : Les structures rptitives 55

I. Problmatique 55

II. Dfinition 55

III. Le Schma Itratif avec Rpter 56

IV. Le Schma Itratif avec Tant que 57

V. Le Schma Itratif avec Pour 59

VII. Exercice rcapitulatif 59

VIII. Tableau Comparatif des Trois Schmas Itratifs 63

Chapitre 7 : Le type Tableau 65

I. Problmatique 65

II. Dfinition 65

III. Reprsentation Algorithmique (tableau) 66

IV. Oprations de base sur un tableau 67

V. Recherche dans un Tableau 68

VI- Exercices dapplication 70


4/102

VII. Les Tableaux deux dimensions : Les Matrices 71

Chapitre 8 : Le type Chane de caractres 76

I. Introduction 76

II. Dfinition 76

III. Reprsentation Algorithmique 76

IV. Les Oprations de base sur les Chanes 77

V- Les Fonctions Prdfinies sur les Chanes 77

VI. Exercices dapplication 80

Chapitre 9 : Les types composes 83

I. Introduction 83

II. Le Type numr 83

III. Le Type Intervalle 85

III. Le Type Enregistrement 85

Chapitre 10 : Les procdures et fonctions 88

I. Problmatique 88

II. Les Fonctions 90

III. Les Procdures 94

IV. La Porte des Variables 96

Chapitre 11 : Les algorithmes de trie 98

I. Introduction 98

II. Le Tri par Slection 99

III. Le Tri par Insertion 99

IV. Le Tri Bulles 100


5/102

Fiche de Prsentation ALGORITHMIQUE ET STRUCTURES DE DONNEES 1

Enseignant Mossaab BOUKHCHIM

Population : tudiants du premier niveau (Tronc Commun) ISETs. Crdits : 67,5 heures par semestre Volume Horaire : 4,5 heures par semaine sur 15 semaines Pr-requis : Informatique de base Langue : Franais

Objectifs du cours Prsenter les principales structures de donnes ainsi que les algorithmes de traitement qui

leur sont associs. Amener les tudiants construire de petites applications selon le principe de la

programmation structure par contrat, cest--dire en sappuyant sur les spcifications

valuations Test N : 1 dune heure. Devoir surveill dune heure. Test N :2 dune heure. Examen final crit de 2 heures sur tout le programme.

Moyens Pdagogiques Support de cours papier. Support de cours numrique. Srie de travaux dirigs.


6/102

But du cours et objectifs gnraux ALGORITHMIQUE 1 ET STRUCTURES DE DONNEES

Objectifs Gnraux Conditions de ralisation de la performance

Critres dvaluation de la performance

Connatre la dfinition dun algorithme, sa structure gnrale et la dmarche suivre pour produire un algorithme.

A partir des notes de cours et des rfrences bibliographiques, ltudiant devrait identifier les lments constitutifs dun algorithme.

Aucune erreur nest permise.

Savoir dclarer des variables et des constantes, aprs avoir compris ces nouvelles notions.

A partir des notes de cours, des rfrences bibliographiques et les TDs ltudiant devrait tre capable de reconnatre une variable et une constante et de pouvoir les dclarer correctement.

Aucune erreur nest permise. Ltudiant doit pouvoir identifier avec succs les variables et les constantes.

Connatre les types simples et les oprations dfinies sur ces types.

A partir des notes de cours, des rfrences bibliographiques et les TDs ltudiant devrait tre capable de reconnatre et dnumrer les types de donnes simples.

Ltudiant doit pouvoir dclarer correctement des variables et utiliser les fonctions dfinies sur les types simples.

Connatre et comprendre les oprations simples (affectation, criture et lecture)

A partir des notes de cours et les TDs ltudiant devrait tre capable de connatre le rle des oprations simples.

Ltudiant doit tre capable dcrire correctement un algorithme utilisant les oprations simples.

Connatre les structures conditionnelles et crire des algorithmes en utilisant ces nouvelles notions.

A partir des notes de cours et les TDs ltudiant devrait tre capable de connatre les structures conditionnelles.

Ltudiant doit tre capable dcrire correctement un algorithme utilisant les structures conditionnelles.

Etudier, comparer et crire les structures itratives.

A partir des notes de cours et les TDs ltudiant devrait tre capable de connatre les structures itratives.

Ltudiant doit tre capable dcrire correctement un algorithme utilisant la structure itrative adquate pour la rsolution dun problme donne.


7/102

Etudier le type Tableau. A partir des notes de cours et les TDs ltudiant devrait tre capable de connatre les diffrents types de donnes composs.

Ltudiant doit tre capable dcrire correctement un algorithme utilisant des types de donnes composs.

Etudier le type chane de caractre.

A partir des notes de cours et les TDs ltudiant devrait tre capable de manipuler le type chane de caractre.

Ltudiant doit tre capable dcrire correctement un algorithme utilisant le type chane de caractre.

Connatre les types intervalle, enregistrement et numr.

A partir des notes de cours et les TDs ltudiant devrait tre capable de dfinir des nouveaux types et de les utiliser pour dclarer les variables.

Ltudiant doit tre capable dcrire correctement un algorithme utilisant des types dfinis par le programmeur.

Connatre le principe de dcomposition des problmes et saisir limportance de lutilisation des procdures et fonctions.

A partir des notes de cours et les TDs ltudiant devrait tre capable de connatre lutilit de dcomposition des problmes. En outre, il devrait tre capable dutiliser cette nouvelle notion.

Ltudiant doit tre capable de dcomposer un problme complexe et dcrire correctement un algorithme utilisant les fonctions et procdures.

Comprendre les algorithmes de tri

A partir des notes de cours et les TDs ltudiant devrait Comprendre les algorithmes de tri.

Ltudiant doit tre capable dcrire un algorithme de tri dun tableau.


8/102

Dcomposition des objectifs gnraux en objectifs spcifiques Objectif gnral (Chapitre 1 : Introduction lalgorithmique)

Connatre la dfinition dun algorithme, sa structure gnrale et la dmarche suivre pour

produire un algorithme.

Objectifs spcifiques Elments du cours Mthodologies Dure

Connatre les concepts indispensables pour lapprentissage de lalgorithmique.

I. Dfinitions II. Le Matriel informatique III. Les Logiciels IV. La Mthodologie Suivre V. La Dmarche

Expos informel (tableau et Notes de cours)

30 min

Connatre lutilit dun algorithme dans la phase de production dun logiciel.

VI. Algorithme et Algorithmique 1. Introduction 2. Dfinitions 3. Algorithmique et programmation 4. Les conventions dun algorithme


60 min

Total 1h30

Objectif gnral (Chapitre 2 : Les Structures de Donnes Notions de base ) Savoir dclarer des variables et des constantes, aprs avoir compris ces nouvelles notions.

Objectifs spcifiques Elments du cours Mthodologies Dure Connatre la structure dun algorithme.

I. Prsentation Sommaire de la Structure dun Algorithme


30 min

Connatre la notion de variable et comprendre son utilit.

II. Notion de Variable III. Notion de Type

Expos informel (tableau, exemples dapplications et Notes de cours)

45 min

Connatre la notion de variable et comprendre son utilit.

IV. Notion de Constante


45 min

Total 2h00


9/102

Objectif gnral (Chapitre 3 : Les Structures de Donnes Les Types Simples ) Connatre les types simples et les oprations dfinies sur ces types.

Objectifs spcifiques Elments du cours Mthodologies Dure

Connatre Le type entier et les oprations associes ce type.

I. Rappel II. Le Type Entier 1. Dfinition 2. Reprsentation Algorithmique 3. Les Oprations de base sur le type Entier


45 min

Connatre Le type rel et les oprations associes ce type. comprendre son utilit.

III. Le Type Rel 1. Dfinition 2. Reprsentation Algorithmique 3.. Les Oprations de base sur le type Rel


45 min

Connatre Le type caractre et les oprations associes ce type. comprendre son utilit.

IV. Le Type Caractre 1. Dfinition 2. Reprsentation Algorithmique 3. Ordre dapparition des lments du type Caractre 4. Les Oprations de base sur le type Caractre


45 min

Connatre Le type Boolen et les oprations associes ce type. comprendre son utilit.

V. Le Type Boolen ou Logique 1. Dfinition 2. Reprsentation Algorithmique 3. Oprateurs Logiques 4. Exemple 5. Utilisation des Oprateurs de Comparaison


45 min

Total 3h00


10/102

Objectif gnral (Chapitre 4 : Les Actions Simples) Connatre et comprendre les oprations simples (affectation, criture et lecture).

Objectifs spcifiques Elments du cours Mthodologies Dure Connatre linstruction de lecture

I. Introduction II. Laction de Lecture 1. Dfinition 2. Reprsentation Algorithmique


30 min

Connatre linstruction dcriture

III. Laction dcriture 1. Dfinition 2. Reprsentation Algorithmique


30 min

Connatre linstruction daffectation

IV. Laffectation 1. Dfinition 2. Reprsentation Algorithmique 3. Exemple 4. Les Expressions Numriques 5. Exercice dapplication


30 min

Exercices de TD 1h30

Total 3h00


11/102

Objectif gnral (Chapitre 5 : Les Structures Conditionnelles SI et SELON ) Connatre les structures conditionnelles et crire des algorithmes en utilisant ces nouvelles

notions.

Objectifs spcifiques Elments du cours Mthodologies Dure Comprendre lintrt de cette structure.

I. Problmatique


30 min Connatre linstruction conditionnelle simple.

II. Structure Conditionnelle un Choix 1. Dfinition 2. Reprsentation Algorithmique 3. Exercice dapplication


45 min

Connatre linstruction conditionnelle deux choix.

III. Structure Conditionnelle deux Choix 1. Dfinition 2. Reprsentation Algorithmique 3. Exercice dapplication


45 min

Connatre les instructions conditionnelles imbriques.

IV. Structure Conditionnelle Imbrique 1. Dfinition 2. Reprsentation Algorithmique 3. Exercices dapplication


1h

Connatre linstruction conditionnelle choix multiples.

V. Structure Conditionnelle Choix Multiple 1. Dfinition 2. Reprsentation Algorithmique 3. Exercice dapplication


1h


Total 8h30


12/102

Objectif gnral (Chapitre 6 : Les Structures Rptitives Rpter Tant que Pour ) Etudier, comparer et crire les structures itratives.

Objectifs spcifiques Elments du cours Mthodologies Dure Comprendre lintrt de la structure itratif et connatre sa signification.

I. Problmatique II. Dfinition


30 min

Connatre la structure itrative rpter

III. Le Schma Itratif avec Rpter 1. Dfinition 2. Reprsentation Algorithmique 3. Excution de la Boucle Rpter 4. Exemples


1h30

Connatre la structure itrative tant que

IV. Le Schma Itratif avec Tant que 1. Dfinition 2. Reprsentation Algorithmique 3. Excution de la Boucle Tant que 4. Exemples


1h30

Connatre la structure itrative pour

V. Le Schma Itratif avec Pour 1. Dfinition 2. Reprsentation Algorithmique 3. Excution de la Boucle Pour 4. Exercices


1h30

Apprendre choisir correctement une structure bien dtermine.

VII. Exercice rcapitulatif VIII. Tableau Comparatif des Trois Schmas Itratifs


1h Exercices de TD 6h

Total 12h


13/102

Objectif gnral (Chapitre 7 : Le type Tableau) Etudier, comparer et crire des types composs.

Objectifs spcifiques

Elments du cours Mthodologies Dure

Comprendre lintrt de lapplication dun type compos

I. Problmatique II. Dfinition


30 min

Manipuler les tableaux unidimensionnels

III. Reprsentation Algorithmique (tableau) IV. Oprations de base sur un tableau V. Recherche dans un Tableau 1. Introduction 2. Recherche Squentielle 3. Recherche Dichotomique VI- Exercices dapplication


1h30min

Manipuler les tableaux deux dimensions.

VII. Les Tableaux deux dimensions : Les Matrices 1. Problmatique 2. Dfinition 3. Reprsentation Algorithmique 4. Oprations de base sur une Matrice 5. Exercice dapplication


4h30min


Total 13h


14/102

Objectif gnral (Chapitre 8 : Le Type Chane de Caractres) Etudier le type chane de caractre.



Connatre le type chane de caractre.

I. Introduction II. Dfinition


30min Manipuler le type chane de caractre.

III. Reprsentation Algorithmique IV. Les Oprations de base sur les Chanes 1. Lecture dune chane 2. Affichage 3. Initialisation V- Les Fonctions Prdfinies sur les Chanes 1. La fonction LONG 2. La fonction CONCAT 3. La fonction POS 4. Les fonctions MAJ et MIN 5. La fonction SUBSTR


1h

Se familiariser avec les chanes de caractre.

VI. Exercices dapplication


1h30


Total 4h30


15/102

Objectif gnral (Chapitre 9 : Les Types Construits Type numr, Type Enregistrement et Type Intervalle )

Connatre les types intervalle, enregistrement et numr.



Connatre le type

numr.

I. Introduction II. Le Type numr 1. Dfinition 2. Reprsentation Algorithmique 3. Application

Expos informel

(tableau, exemples dapplications et Notes de cours)

30 min

Connatre le type

intervalle.

III. Le Type Intervalle 1. Dfinition 2. Reprsentation Algorithmique

Expos informel

(tableau, exemples dapplications et

Notes de cours)

30 min

Connatre le type

enregistrement

III. Le Type Enregistrement 1. Dfinition 2. Reprsentation Algorithmique 3. Accs aux rubriques

Expos informel

(tableau, exemples dapplications et Notes de cours)

30 min

Total 1h30


16/102

Objectif gnral (Chapitre 10 : Les Procdures et les Fonctions) Connatre le principe de dcomposition des problmes et saisir limportance de lutilisation des

procdures et fonctions.



Comprendre lintrt de la dcomposition dun problme donn.

I. Problmatique


30min

Connatre la notion des fonctions

II. Les Fonctions 1. Dfinition 2. Reprsentation algorithmique 3. Appel de la fonction


1h30min

Connatre la notion des procdures

III. Les Procdures 1. Dfinition 2. Reprsentation algorithmique 3. Appel de la procdure


1h30min

Connatre la porte des variables dclars.

IV. La Porte des Variables 1. Variable Locale 2. Variable Globale


30min


Total 11h30


17/102

Objectif gnral (Chapitre 11 : Les Algorithmes de Tri) Comprendre les algorithmes de tri.



Comprendre lintrt des algorithmes de tri.

I. Introduction


30 min

Connatre lalgorithme de tri par slection.

II. Le Tri par Slection 1. Principe 2. Algorithme

Expos informel (tableau, exemples dapplication et Notes de cours)

30 min

Connatre lalgorithme de tri par Insertion.

III. Le Tri par Insertion 1. Principe 2. Algorithme


30 min

Connatre lalgorithme de tri Bulles.

IV. Le Tri Bulles 1. Principe 2. Algorithme


30 min

Exercices de TD 30min

Total 2h30min

Introduction lAlgorithmique Objectif

Connatre les concepts indispensables pour lapprentissage de lalgorithmique.

Connatre lutilit dun algorithme dans la phase de production dun logiciel.

Elments de contenu

Dfinitions Le Matriel informatique Les Logiciels La Mthodologie Suivre La Dmarche Algorithme et Algorithmique

o Introduction o Dfinitions o Algorithmique et programmation

o Les conventions dun algorithme


19/102

Chapitre I Introduction lAlgorithmique

I. Dfinitions Le terme informatique : linformatique est une science qui permet de traiter

automatiquement les informations.

Le terme systme informatique : un systme informatique est un ensemble de

moyens matriel et logiciels permettant de satisfaire les besoins informatiques de lutilisateur.

Le terme utilisateur : un utilisateur est une personne initi linformatique et autoris exploiter et manipuler les ressources du systme informatique.

II. Le Matriel informatique Il sagit des ressources matrielles qui sont exploites pour excuter les diffrents logiciels

destins satisfaire les besoins des utilisateurs : micro-ordinateurs, imprimantes, scanners, units de sauvegarde, etc.

III. Les Logiciels Un logiciel est un ensemble de programmes qui rpond aux besoins frquents de

lutilisateur dans un domaine dactivits bien dtermin : Logiciel de bureautique pour les travaux quotidiens du bureau : Microsoft Word,

Microsoft Excel, Microsoft Power Point, Microsoft Outlook, etc. Logiciel de pointage pour enregistrer rgulirement les journes de travail du personnel :

Ciel-personnel, etc.

Logiciel scientifique pour la rsolution dquations ou ltude des fonctions ou encore pour les travaux de statistiques : Matlab, etc.

Il faut distinguer entre Logiciel et Progiciel ; on dira alors quun Progiciel est un Logiciel standard qui peut tre adapt nimporte quelle organisation : par exemple, les logiciels de bureautique (Microsoft Office ou Star Office) peuvent tre utiliss par nimporte quelle entreprise et quelle que soit son activit.


20/102

Par contre, un logiciel est plutt spcifique cest dire quil ne peut tre exploit que dans un environnement industriel bien dtermin : un logiciel de production dans le domaine du textile

ne peut pas tre exploit dans la fabrication des pices de rechanges automobiles ou dans le domaine de lemballage mtallique.

IV. La Mthodologie Suivre crire un programme, ce n'est pas seulement connatre le langage de dialogue entre

l'ordinateur et vous. Un programme est un discours adress l'ordinateur, et comme tout discours, il prsente deux aspects : un contenu et une forme, un sens et une grammaire.

Pour l'ordinateur, il suffit que le discours soit correct au niveau de la forme. A partir de ce moment, il effectue les manipulations qu'on lui demande d'effectuer. Le contenu est pour l'ordinateur purement syntaxique. Si l'on fait une erreur de syntaxe, l'ordinateur affichera un message d'erreur. L'apprentissage de la programmation est donc ce niveau fortement dpendant du langage que l'on utilise. Mais la cohrence du programme, c'est dire du contenu, n'est pas value. Cette cohrence et cette pertinence de l'analyse du problme traiter sont donc un pralable tout exercice de programmation. On doit fixer l'objectif du programme, tablir la liste donnes et des oprations excuter, et les ordonner. La description de la suite des oprations

lmentaires ordonnes capables de rsoudre le problme pos constitue l'algorithme. Donc, on a intrt crire des algorithmes claires, lisibles, optimal pour avoir un programme de

qualit. Pour y arriver, on doit suivre une mthodologie.


21/102

V. La Dmarche L'criture d'un programme n'est qu'une tape dans le processus de programmation comme le

montre le schma suivant :

Les diffrentes tapes du processus de programmation.

L'analyse d'un problme pos consiste dfinir les diffrentes tapes de sa rsolution. C'est la

partie essentielle dans le processus de programmation. Elle permet de dfinir le contenu d'un programme en termes de donnes et dactions. Une dmarche descendante permettrait de dcomposer le problme initial en sous problmes , plus simples rsoudre. chacun de ces derniers sera associ une spcification formelle ayant des conditions d'entre et le(s) rsultat(s) que l'on souhaiterait obtenir. L'ensemble de ces spcifications reprsente l'algorithme.


22/102

La phase suivante consiste traduire lalgorithme dans un langage de programmation donn. Ce travail, quoiquil semble facile, exige le respect strict de la syntaxe du langage. Lors de ltape

dexcution, soit des erreurs syntaxiques sont signales, ce qui entrane des corrections en gnral simples effectuer, soit des erreurs smantiques plus difficiles dceler. Dans le cas derreur syntaxique, les retours vers le programme peuvent tre frquents. Dans le cas derreur smantique, le programme produit des rsultats qui ne correspondent pas ceux escompts : les retours vers lanalyse (algorithme) sont alors invitables. Remarques :

On ne peut excuter un programme quaprs lavoir compil sans erreurs ; cest uniquement dans ce cas que le programme excutable sera gnr.

La compilation est faite par le compilateur qui dpend dun langage de programmation un autre.

Certains langages (cest devenu rare), ne comportent pas de compilateurs mais ils inclurent des interprteurs : le programme peut tre excut sans gnrer pralablement le code excutable, instruction par instruction. Vous pouvez alors imaginer les inconvnients qui en dcoulent.

Pratiquement, cest le microprocesseur qui se charge de lexcution dun programme instruction par instruction en respectant le cycle dexcution dune instruction du cours darchitecture des ordinateurs. Cependant, pour le faire, il faut que le programme ainsi que ses donnes soient chargs pralablement en mmoire centrale.

Dans la suite de ce cours, tous les problmes quon va rsoudre seront structurs cest

dire qui possdent lavance une solution mathmatique : rsolution dune quation du second degr, classification ABC du stock, facturation, Bulletin de paie, etc. Pourquoi on voque cette remarque, parce que certains problmes peuvent se prsenter dune

manire non structur : crire un algorithme qui permet de choisir quel fournisseur doit opter pour lacquisition du matriel. Deux aspects peuvent tre retenus : loffre financire et loffre

SAV(service aprs vente) ; si le premier aspect est mesurable, le second ne peut pas ltre objectivement ; cest pour cette raison que le problme prsent nest pas bien structur.


23/102

VI. Algorithme et Algorithmique 1. Introduction

Un algorithme est une suite d'actions que devra effectuer un ordinateur, en un temps fini, pour arriver un rsultat, partir d'une situation donne.

Un algorithme est une suite finie d'instructions indiquant de faon prcise l'ordre dans lequel doit tre effectu un ensemble d'oprations pour obtenir la solution dun problme.

Lalgorithmique est la logique utilise pour crire des algorithmes.

2. Dfinition Avez-vous dj ouvert un livre de recettes de cuisine ? Avez vous dj dchiffr un mode

demploi traduit directement du coren pour faire fonctionner un magntoscope ou un rpondeur tlphonique rticent ? Si oui, sans le savoir, vous avez dj excut des algorithmes. Plus fort : avez-vous dj indiqu un chemin un touriste gar ? Avez vous fait chercher un objet quelquun par tlphone ? crit une lettre anonyme stipulant comment procder une remise de ranon ? Si oui, vous avez dj fabriqu et fait excuter des algorithmes. Comme quoi, lalgorithmique nest pas un savoir sotrique rserv quelques rares initis touchs par la grce divine, mais une aptitude partage par la totalit de lhumanit. Donc, pas

dexcuses Un algorithme, cest une suite dinstructions, qui une fois excute correctement, conduit un rsultat donn. Si lalgorithme est juste, le rsultat est le rsultat voulu, et le touriste se retrouve l o il voulait aller. Si lalgorithme est faux, le rsultat est, disons, alatoire, et dcidment, cette saloperie de rpondeur ne veut rien savoir. Compltons toutefois cette dfinition. Aprs tout, en effet, si lalgorithme, comme on vient de le dire, nest quune suite dinstructions menant celui qui lexcute rsoudre un problme, pourquoi ne pas donner comme instruction unique : rsous le problme , et laisser linterlocuteur se dbrouiller avec a ? A ce tarif, nimporte qui serait champion dalgorithmique sans faire aucun effort. Pas de a Lisette, ce serait trop facile. Le malheur (ou le bonheur, tout dpend du point de vue) est que justement, si le touriste vous demande son chemin, cest quil ne le connat pas. Donc, si on nest pas un goujat intgral, il ne sert rien de lui dire de le trouver tout seul. De mme les modes demploi contiennent gnralement (mais pas toujours) un peu plus dinformations que dbrouillez vous pour que a marche . Pour fonctionner, un algorithme doit donc contenir uniquement des instructions comprhensibles par celui qui devra lexcuter. Cest dailleurs


24/102

lun des points dlicats pour les rdacteurs de modes demploi : les rfrences culturelles, ou lexicales, des utilisateurs, tant variables, un mme mode demploi peut tre trs clair pour

certains et parfaitement abscons pour dautres. En informatique, heureusement, il ny a pas ce problme : les choses auxquelles ont doit donner des instructions sont les ordinateurs, et ceux-ci ont le bon got dtre tous strictement aussi idiots les uns que les autres.

3. Algorithmique et programmation Pourquoi apprendre lalgorithmique pour apprendre programmer ? En quoi a-t-on besoin

dun langage spcial, distinct des langages de programmation comprhensibles par les ordinateurs ? Parce que lalgorithmique exprime les instructions rsolvant un problme donn

indpendamment des particularits de tel ou tel langage. Pour prendre une image, si un programme tait une dissertation, lalgorithmique serait le plan, une fois mis de ct la rdaction

et lorthographe. Or, vous savez quil vaut mieux faire dabord le plan et rdiger ensuite que linverse Apprendre lalgorithmique, cest apprendre manier la structure logique dun programme informatique. Cette dimension est prsente quelle que soit le langage de programmation ; mais lorsquon programme dans un langage (en C, en Visual Basic, etc.) on doit en plus se colleter les problmes de syntaxe, ou de types dinstructions, propres ce langage. Apprendre lalgorithmique de manire spare, cest donc srier les difficults pour mieux les vaincre.

cela, il faut ajouter que des gnrations de programmeurs, souvent autodidactes (mais pas toujours, hlas !), ayant directement appris programmer dans tel ou tel langage, ne font pas mentalement clairement la diffrence entre ce qui relve de la structure logique gnrale de toute

programmation (les rgles fondamentales de lalgorithmique) et ce qui relve du langage particulier quils ont appris. Ces programmeurs, non seulement ont beaucoup plus de mal passer ensuite un langage diffrent, mais encore crivent bien souvent des programmes qui mme sils

sont justes, restent laborieux. Car on nignore pas impunment les rgles fondamentales de lalgorithmique Alors, autant lapprendre en tant que telle !

Un langage de programmation est une convention pour donner des ordres un ordinateur. Ce nest pas cens tre obscur, bizarre et plein de piges subtils. a, ce sont les caractristiques de la magie. Dave Small


25/102

4. Les conventions dun algorithme Historiquement, plusieurs types de notations ont reprsent des algorithmes. Il y a eu

notamment une reprsentation graphique, avec des carrs, des losanges, etc. quon appelait des organigrammes. Aujourdhui, cette reprsentation est quasiment abandonne, pour deux raisons. Dabord, parce que ds que lalgorithme commence grossir un peu, ce nest plus pratique du tout du tout. Ensuite parce que cette reprsentation favorise le glissement vers un certain type de programmation, dite non structure (nous dfinirons ce terme plus tard), que lon tente au contraire dviter. Cest pourquoi on utilise gnralement une srie de conventions appele pseudocode , qui ressemble un langage de programmation authentique dont on aurait vacu la plupart des problmes de syntaxe. Ce pseudo-code est susceptible de varier lgrement dun

livre (ou dun enseignant) un autre. Cest bien normal : le pseudocode, encore une fois, est purement conventionnel ; aucune machine nest cense le reconnatre. Donc, chaque cuisinier

peut faire sa sauce sa guise, avec ses petites pices bien lui, sans que cela prte consquence. Comme je nai pas moins de petites manies que la majorit de mes semblables, le pseudo-code que vous dcouvrirez dans les pages qui suivent possde quelques spcificits mineures qui ne doivent qu mes nvroses personnelles. Rassurez-vous cependant, celles-ci restent dans les limites tout fait acceptables. En tout cas, personnellement, je les accepte trs bien.

Remarque :

Dans certains ouvrages surtout canadiens, on utilise le terme Algorithmie au lieu

dAlgorithmique.

Les Structures de Donnes : Notions de base

Objectif

Connatre la structure dun algorithme. Connatre la notion de variable et comprendre son utilit. Connatre la notion de constante et comprendre son utilit

Elments de contenu

Prsentation Sommaire de la Structure dun Algorithme Notion de Variable Notion de Type Notion de Constante


27/102

Chapitre II Les Structures de Donnes : Notions de base

I. Prsentation Sommaire de la Structure dun Algorithme Dans un algorithme, on trouve deux parties essentielles :

Une partie dclarative contenant tous les objets qui seront impliqus par les diffrentes actions de lalgorithme (constantes, types, variables, etc.).

Une partie rserve aux actions (en programmation, on dit les instructions) ; elle est dlimite par les deux mots-cls Dbut et Fin.

En outre, un algorithme est caractris par son nom qui devrait tre significatif.

Algorithme nomalgo Constante . Type .

Variable .

Partie dclarative

Dbut

..

Partie rserve aux actions

Remarque :

Le nom dun algorithme et dune manire gnrale le nom dun objet impliqu dans les actions de lalgorithme doivent respecter lors de leur dfinition les rgles dun identificateur qui disent :

Un identificateur doit tre significatif. Un identificateur doit tre crit sur 8 positions (Taille


28/102

II. Notion de Variable On rappelle que lexcution dun programme doit impliquer les donnes qui sont lies ce

programme. Ces donnes se trouvent ce moment au niveau de la mmoire centrale et chacune occupe une case mmoire.

Une variable est donc un espace mmoire qui va contenir des donnes au fur et mesure que le programme avance dans son excution. Cependant, un instant donn, une variable ne peut contenir quune seule donne (valeur). Remarques :

une variable est caractrise par son nom qui doit tre significatif et respecter les rgles

dun identificateur. une variable est galement identifie par son adresse en mmoire centrale ; cette adresse

sera intressante un stade avanc de lalgorithmique (les pointeurs). une variable est caractrise par son contenu : les valeurs quelle peut prendre lors de

lexcution dun programme. une variable possde un type cest dire un ensemble contenant toutes les valeurs

possibles quelle peut prendre.

III. Notion de Type Une variable utilis dans un algorithme ne peut prendre quun ensemble de valeurs connues lavance ; toute variable possde un domaine de dfinition. En terme informatique, ce domaine est appel le Type de la variable. Un type est alors caractris par :

ses valeurs

les oprations qui peuvent seffectuer sur des variables ayant ce type. On distingue deux familles de types :

les types simples : ce sont des types qui sont supports et reconnus par la majorit des langages de programmation. Lors de lcriture de lalgorithme ou du programme, ce nest

pas la peine de les dclarer dans la partie dclarative rserve aux types. Les types composs ou complexes : ce sont des types qui sont construits partir des types

simples mais quil faut les dclarer dans la partie rserve aux types : tableaux, chanes, enregistrements, etc.


29/102

IV. Notion de Constante Une constante est une variable qui ne change pas de valeurs lors de lexcution dun programme.

Par exemple :

La constante PI = 3.14

La constante e=2.7

Remarque :

Le nom dune constante doit respecter les rgles de constitution dun identificateur. Ainsi, on ne

peut pas dclarer =3.14 comme constante car le symbole est un caractre spcial non permis lors de la dfinition dun identificateur ; cest pour cette raison quon utilise PI=3.14.

Les Structures de Donnes : Les Types Simples

Objectif

Connatre Le type entier et les oprations associes ce type.

Connatre Le type rel et les oprations associes ce type et comprendre son utilit.

Connatre Le type caractre et les oprations associes ce type et comprendre son utilit.

Connatre Le type Boolen et les oprations associes ce type et comprendre son utilit

Elments de contenu

Rappel Le Type Entier

Le Type Rel Le Type Caractre Le Type Boolen ou Logique


31/102

Chapitre III Les Structures de Donnes : Les Types Simples

I. Rappel : On a vu dans le chapitre prcdent que toute variable possde un type et on a distingu deux

familles de types : les types simples et les types composs. Dans le prsent chapitre, on va passer en revue les types simples qui sont au nombre de quatre :

Le Type Entier.

Le Type Rel.

Le Type Caractre.

Le Type Boolen ou Logique.

II. Le Type Entier 1. Dfinition

Le type Entier comprend un sous ensemble fini de nombres entiers, dont la taille varie en

fonction des performances techniques de la machine et celles du langage de programmation utilis.

2. Reprsentation Algorithmique Le type entier tant reconnu automatiquement, il nest pas ncessaire de le dclarer dans la partie des types. Il suffit dindiquer devant le nom de la variable son type.


Variable .

Cest ici !!!! Dbut


32/102

Variable Nomvar : Entier (Nomvar tant la variable qui sera utilise dans lalgorithme) Si on plusieurs variables en mme temps, ce nest pas la peine de les dclarer sparment ; on peut les regrouper en les sparant par une virgule.

Variable Nomvar1, Nomvar2, ., NomvarN : Entier

3. Les Oprations de base sur le type Entier Sur le type Entier, on distingue deux catgories doprations :

les oprations arithmtiques les oprations algorithmiques telles que la lecture, lcriture, etc ; elles feront lobjet dun

chapitre part.

Opration Symbole Exemple Addition + A=5, B=7 ; A+B renvoie 12

Soustraction - A=5, B=7 ; A-B renvoie 2

Multiplication * A=5, B=7 ; A* B renvoie 35

Division (entire) DIV A=5, B=7 ; A DIV B renvoie 0 Reste de la Division entire MOD A=5, B=7 ; A MOD B renvoie 5

Remarques :

Le Reste de la division entire est not parfois par le symbole %.

On risque dans certaines oprations de dpasser les limites du type ; on dit quil y a dpassement de capacit, ou dbordement ou en anglais Overflow.


33/102

III. Le Type Rel 1. Dfinition

Le type Rel comprend un sous ensemble fini de nombres rels, dont la taille varie en fonction des performances techniques de la machine et celles du langage de programmation

utilis.

2. Reprsentation Algorithmique Le type Rel tant reconnu automatiquement, il nest pas ncessaire de le dclarer dans la partie

des types. Il suffit dindiquer devant le nom de la variable son type.

Algorithme nomalgo

Constante . Type .

Variable .

Cest ici !!!! Dbut

Variable Nomvar : Rel (Nomvar tant la variable qui sera utilise dans lalgorithme) Si on plusieurs variables en mme temps, ce nest pas la peine de les dclarer sparment ; on peut les regrouper en les sparant par une virgule.

Variable Nomvar1, Nomvar2, ., NomvarN : Rel


34/102

3. Les Oprations de base sur le type Rel Sur le type Rel, on distingue deux catgories doprations :

les oprations arithmtiques les oprations algorithmiques telles que la lecture, lcriture, etc ; elles feront lobjet dun

chapitre part.

Opration Symbole Exemple Addition + A=5.5, B=7.0 ; A+B renvoie 12.5

Soustraction - A=5.5, B=7.0 ; A-B renvoie 2.5

Multiplication * A=5.5, B=7.0 ; A* B renvoie 38.5

Division normale / A=5.5, B=7.0 ; A / B renvoie 0.79

IV. Le Type Caractre 1. Dfinition

Le type Caractre est ensemble de caractres comportant : les 26 lettres alphabtiques en majuscules (A jusqu Z) les 26 lettres alphabtiques en minuscules (a jusqu z) les 10 chiffres arabes (0 jusqu 9). quelques caractres spciaux.

Remarque :

Chaque valeur dun caractre est dlimite par deux apostrophes c.

2. Reprsentation Algorithmique Le type Caractre tant reconnu automatiquement, il nest pas ncessaire de le dclarer dans la partie des types. Il suffit dindiquer devant le nom de la variable son type.


35/102


Variable .

Cest ici !!!! Dbut

.

Variable Nomvar : Caractre (Nomvar tant la variable qui sera utilise dans lalgorithme) Si on plusieurs variables en mme temps, ce nest pas la peine de les dclarer sparment ; on

peut les regrouper en les sparant par une virgule.

Variable Nomvar1, Nomvar2, ., NomvarN : Caractre

Remarque :

Une variable de type caractre contient un instant donne un seul caractre. dfaut, on ne parle plus de caractre mais de chane de caractres (voir chapitre chane de caractres).

3. Ordre dapparition des lments du type Caractre Lapparition des diffrentes valeurs du type caractre suit lordre suivant :

0


36/102

4. Les Oprations de base sur le type Caractre Sur le type Caractre, on distingue deux catgories doprations :

les oprations propres aux caractres les oprations algorithmiques telles que la lecture, lcriture, etc. ; elles feront lobjet dun

chapitre part.

Opration Symbole Exemple Successeur ou Suivant Succ ou Suiv Si A=C alors Suiv(A) renvoie D Prdcesseur ou Prcdent Pred ou Prec Si A=C alors Prec(A) renvoie B Remarques :

Les oprations successeur et prdcesseur respectent lordre dapparition des caractres mentionn ci-dessus.

la fonction successeur et prdcesseur sappliquent sur des variables de type caractre ou des constantes caractres.

Exemple : succ (A) envoie B par contre succ (A) avec A variable contenant le caractre C renvoie D.

V. Le Type Boolen ou Logique 1. Dfinition

Un type boolen dit galement logique est un ensemble qui est constitu de deux lments dont la valeur de lun contredit celle de lautre. Les valeurs attribues ces lments varient dun contexte un autre.

Pour reprsenter des nombres binaires, on dclare un type boolen form de 0 et 1. Pour reprsenter une variable rponse, on dclare un type boolen form de Oui et Non.

Pour reprsenter une variable logique, on dclare un type boolen form de Vrai et Faux. Pour reprsenter ltat dune lampe, on dclare un type boolen form de Allume et

teinte. Pour reprsenter ltat dun interrupteur, on dclare un type boolen form de Ouvert et

Ferm.


37/102

2. Reprsentation Algorithmique Le type Boolen tant reconnu automatiquement, il nest pas ncessaire de le dclarer dans la

partie des types. Il suffit dindiquer devant le nom de la variable son type.


Variable .

Cest ici !!!! Dbut

Variable Nomvar : Boolen (Nomvar tant la variable qui sera utilise dans lalgorithme) Si on plusieurs variables en mme temps, ce nest pas la peine de les dclarer sparment ; on peut les regrouper en les sparant par une virgule.

Variable Nomvar1, Nomvar2, ., NomvarN : Boolen

3. Oprateurs Logiques Sur le type boolen, on applique des oprateurs logiques pour constituer une expression logique ;

ces oprateurs sont Non

Et

Ou En les appliquant sur des variables boolennes, voil ce que a donne :

Var1 Var2 Non Var1 Var1 Et Var2 Var1 Ou Var2 0 0 1 0 0

0 1 1 0 1

1 0 0 0 1

1 1 0 1 1


38/102

4. Exemple Var2 va contenir la valeur faux

Algorithme Essai Variable Var1, Var2 : Boolen Dbut Var1=vrai Var2=Non(Var1) Fin.

Les Actions Simples

Objectif Connatre linstruction de lecture Connatre linstruction dcriture Connatre linstruction daffectation

Elments de contenu Introduction Laction de lecture Laction dcriture Laction daffectation


40/102

Chapitre IV Les Actions Simples

I. Introduction On rappelle quun algorithme comporte deux parties : une partie dclarative et une partie rserve aux actions. Parmi ces actions, on cite les actions simples qui couvrent laction de Lecture, laction dcriture et laction dAffectation.

II. LAction de Lecture 1. Dfinition

La lecture est une opration dentre qui seffectue des priphriques dentre (clavier, souris, stylo optique, etc.) vers la mmoire centrale. Elle permet lutilisateur dintroduire les donnes au programme pour quil produise les rsultats attendus.

2. Reprsentation Algorithmique Une action de Lecture est reprsente par le terme Lire ; elle peut concerner une variable ou plusieurs variables. Pour une variable laction de lecture ou encore la primitive de lecture doit se prsenter comme suit : Lire (Nomvariable). Pour plusieurs variables, deux formats de lecture peuvent tre appliqus :

soit une lecture de toutes les variables ensemble Lire(Nomvariable1, Nomvariable2, ., NomvariableN).

soit une lecture pour chaque variable et dans ce cas on a le schma suivant : Lire(Nomvariable1) Lire(Nomvariable2)

Lire(NomvariableN) Remarques :

Il est interdit de lire une constante.

Si PI=3.14 dclare comme constante, Lire (PI) est impossible.


41/102

Il est interdit de lire une expression arithmtique ou logique. Lire (a+b) est impossible. Il est interdit de lire un message . Lire (Bonjour) est impossible. Dans certains problmes rsoudre, certains tudiants trouvent parfois des difficults

pour se dcider sils vont lire la variable ou faire autre chose. Dans ce qui suit, on va prsenter les phrases ayant le contexte de lecture :

Saisir des donnes partir du clavier : il sagit dune lecture. Entrer des donnes partir du clavier : il sagit dune lecture. Introduire les donnes : il sagit dune lecture.

Exploiter les donnes stockes dans une disquette pour rsoudre tel problme. couter un morceau sonore revient lire un fichier son.

III. LAction dcriture 1. Dfinition

Lcriture est une opration de sortie (de la mmoire ou du microprocesseur vers les priphriques de sortie). Elle permet lutilisateur dafficher les rsultats dun programme sur le(s) priphrique(s) de sortie, tels que : cran, imprimante, traceur, etc.

2. Reprsentation Algorithmique Une action dcriture, parfois dite une primitive dcriture peut se faire :

sur une ou plusieurs variables,

sur des constantes, sur des expressions arithmtiques et logiques, sur des messages.

Une action dcriture peut tre mixte, cest dire quelle regroupe des variables, des constantes, des expressions et des messages.

a) criture sur une ou plusieurs variables Pour une variable laction dcriture ou encore la primitive dcriture doit se prsenter comme

suit : crire(Nomvariable). crire(Nomvariable) consiste afficher le contenu de la variable Nomvariable lcran.


42/102

Pour plusieurs variables, deux formats d criture peuvent tre appliqus :

soit une criture de toutes les variables ensemble crire (Nomvariable1, Nomvariable2, ., NomvariableN).

soit une criture pour chaque variable et dans ce cas on a le schma suivant : crire (Nomvariable1) crire (Nomvariable2)

crire (NomvariableN) b) criture dune constante

Cest une opration qui consiste afficher la valeur dune constante. crire(Valconstante) ou crire(Nomconstante), sachant que cette constante contient la valeur Valconstante.

Exemples

crire(3.14) crire(PI)

c) criture dune expression arithmtique ou logique Dans certains programmes, et en vue doptimiser le nombre de variables ainsi que le nombre dinstructions, on ralise directement une primitive dcriture sur une expression.

crire(expression) Exemples :

crire(a+b*c) avec a,b,c des entiers crire(a ou b et c) avec a,b,c des boolens


43/102

Application directe crire un algorithme qui calcule la somme de deux entiers a et b saisis partir du clavier. Algorithme Somme Variable a,b,S : entier Dbut Lire(a) Lire(b) S=a+b crire(S) Fin.

Algorithme Somme Variable a,b : entier Dbut Lire(a) Lire(b) crire(a+b) Fin.

Gain dune variable et dune instruction

d) criture dun message Lutilisation des messages dans un programme ne fait que faciliter son utilisation ; il devient de plus en plus convivial. Un message est une suite de caractre ayant un sens et dlimit par deux apostrophes.

crire(message) Exemple :

crire(Bonjour) : cette opration affichera lcran le mot Bonjour. Remarque

Quelle est la diffrence entre crire(Bonjour) et crire(Bonjour) ? crire(Bonjour) : cette opration affichera lcran le mot Bonjour. crire(Bonjour) : cette opration affichera lcran le contenu de la variable Bonjour.

e) criture Mixte Dans certains programmes, laffichage doit tre trs clair. Par exemple, on veut afficher la ligne suivante : Le Montant de la Facture est = 1250 DT. Pour obtenir un tel affichage, on doit prsenter laction dcriture comme suit : crire(Le Montant de la Facture est = , MNTFACT, DT) o MNTFACT est la variable qui contient ce montant. On parle dans ce cas dcriture mixte.


44/102

crire(message,Nomvariable,constante,message,.) IV. LAffectation

1. Dfinition On utilise des variables pour manipuler des donnes. Il faut donc que ces variables contiennent

pralablement des valeurs, pour ce faire on leur affecte une valeur. Laffectation se fait de la manire suivante :

V := expression Variable

Nom de la variable mme type Nom Type Valeur

2. Reprsentation Algorithmique : Nomvariable := Valeur

3. Exemple crire un algorithme qui permet de saisir deux entiers puis les permute. Solution Cest un problme classique ; imaginez que vous dsiriez changer le contenu dun plat dans un autre plat qui est dj plein, que faut-il faire ? il suffit de chercher un plat vide et procder lchange. De mme dans ce problme, on va utiliser une variable dite intermdiaire.

Algorithme permute2 Variable a,b,x : entier Dbut Lire (a) Lire (b) x:= a a:= b b :=x crire(a) crire(b) Fin.


45/102

4. Les Expressions Numriques Une expression numrique peut contenir les lments suivants :

des constantes, des variables, des oprateurs numriques : +,-,*,/, DIV,MOD des parenthses.

Cette expression ne peut pas apparatre dans un programme toute seule ; elle doit tre affecte une variable ayant le mme type que cette expression.

Exemples dexpression : A+B

3+2-B (A+B)*C-2 C

Dans un programme, on trouve X := (A+B)*C-2 par exemple. Si on veut valuer le rsultat de X, comment doit on procder ? Il ne faut pas se hasarder et mme si vous allez obtenir un rsultat, il se peut quil soit erron !!? En fait, il y a une certaine priorit respecter au niveau des oprateurs arithmtiques : Priorit 1 : Fonctions ( voir plus tard). Priorit 2 : Parenthses. Priorit 3 : Multiplications et Divisions. Priorit 4 : Additions et Soustractions. Remarque :

Si dans une expression, on rencontre des oprateurs ayant la mme priorit, on commencera par loprateur situ le plus gauche dans lexpression.


46/102

5. Exercice dapplication Remplir le tableau suivant en respectant la priorit des oprateurs ?

A B C X

A :=1

B :=2

C :=3

X :=A+B*C

X :=(A+B)/C X := A+B/C

Les Structures Conditionnelle

Objectif Comprendre lintrt de cette structure. Connatre linstruction conditionnelle simple. Connatre linstruction conditionnelle deux choix. Connatre les instructions conditionnelles imbriques. Connatre linstruction conditionnelle choix multiples.

Elments de contenu Problmatique

Structure Conditionnelle un Choix o Dfinition o Reprsentation Algorithmique o Exercice dapplication

Structure Conditionnelle deux Choix o Dfinition o Reprsentation Algorithmique o Exercice dapplication

Structure Conditionnelle Imbrique o Dfinition o Reprsentation Algorithmique o Exercices dapplication

Structure Conditionnelle Choix Multiple o Dfinition o Reprsentation Algorithmique

o Excution du Selon o Exercice dapplication


48/102

Chapitre V Les Structures Conditionnelles

I. Problmatique Lors du cours sur les actions simples, les problmes traits possdent des solutions lmentaires constitues dune suite finie et ordonne dactions simples. En ralit, les problmes sont plus complexes que a. La rsolution de certains dentre eux ne peut se faire que sous condition et

pour chaque condition un traitement spcifique sera dclench et exclura les traitements des autres conditions. On doit alors trouver une autre structure algorithmique capable de prendre en

charge les diffrents traitements relatifs aux diffrentes conditions et den dclencher exclusivement le traitement qui respecte une certaine condition. Une telle structure est appele Structure Conditionnelle. On distingue plusieurs formes :

Structure Conditionnelle un seul choix. Structure Conditionnelle deux choix.

Structure Conditionnelle imbrique. Structure Conditionnelle choix multiple.

II. Structure Conditionnelle un Choix 1. Dfinition

Il sagit dun traitement qui ne peut sexcuter que si une condition logique est satisfaite ; dans le cas contraire, rien ne devrait se passer.

2. Reprsentation Algorithmique

Si (Condition_Satisfaite) Alors Finsi

Exemple : On veut octroyer une prime pour les salaris maris ayant plus de 3 enfants. SI (Nbr_Enfants >= 3) ALORS Salaire Salaire + Prime FinSi


49/102

3. Exercice dapplication crire un algorithme qui permet de rsoudre une quation de 1er degr : ax+b=0 en supposant que a >0.

Solution Algorithme Equation1 Variable a,b,x : rel Dbut Lire(a) Lire(b) Si ( a > 0 ) Alors x -b/a Finsi crire(x) Fin

III. Structure Conditionnelle deux Choix 1. Dfinition

Il sagit dun traitement qui ne peut sexcuter que si une condition logique est satisfaite ; dans le cas contraire, un autre traitement sera excut.


Si (Condition_Satisfaite) Alors Sinon Finsi

Avec et comportant une suite finie dactions simples.


50/102

3. Exercice dapplication crire un algorithme qui permet de rsoudre une quation de 1er degr : ax+b=0 avec b non nul.

Solution Algorithme Equation1 Variable a,b,x : rel Dbut Lire(a) Lire(b) Si ( a > 0 ) Alors x -b/a crire(x) Sinon crire(Pas de Solutions) Finsi Fin

IV. Structure Conditionnelle Imbrique 1. Dfinition

Il sagit dun traitement qui ne peut sexcuter que si une condition logique est satisfaite ; dans le cas contraire, un autre traitement sera excut. Les diffrents traitements ne comportent plus uniquement des actions simples mais on peut leur imbriquer des structures conditionnelles.


Si (Condition_Satisfaite) Alors Sinon Finsi

Avec et comportant une suite finie dactions simples et dactions conditionnelles.


51/102

3. Exercice dapplication Ecrire un algorithme Mois qui lit un numro de mois et affiche son nom respectif.

Algorithme Mois Variable NumMois : entier DEBUT Lire (NumMois)

SI NumMois = 1 ALORS Ecrire(Janvier) SINON SI NumMois = 2

ALORS Ecrire(Fvrier) SINON

SINON SI NumMois = 1 ALORS Ecrire(Dcembre) SINON Ecrire(Erreur) FINSI FINSI FINSI FINSI FIN

V. Structure Conditionnelle Choix Multiple 1. Dfinition

Partant de lnonc prcdant, on remarque limportance de la longueur et la complexit de cet algorithme, on y trouve trop de conditions imbriques. La solution est lutilisation dune

autre structure conditionnelle appele structure conditionnelle choix multiple. Par dfinition, une structure choix multiple est une structure qui partir dun choix va se positionner sur le bon

traitement sans passer par les autres ; on la note par SELON.


52/102


Selon (nomvariable) Faire Val1 :

Val2 :

..

ValN :

Sinon FinSelon

Remarques :

nomvariable est appele Slecteur ou Variable de choix. Le slecteur doit tre dclar et comporter une valeur avant dtre impliqu dans le Selon.

Si pour diffrentes valeurs, le traitement est le mme, on peut les regrouper ensemble en les sparant par des virgules :

Val1, Val2, .., ValK :

Val1, Val2, ., ValN doivent tre de mme type que nomvariable. Les valeurs Val1,., ValN ne peuvent avoir que les types suivants :

o Entier

o Caractre

o Intervalle dentiers o Intervalle de caractres.

les traitements relatifs aux valeurs peuvent comporter galement dautres structures

conditionnelles.


53/102

3. Exercice dapplication Reprendre lalgorithme mois : Algorithme Mois Variable NumMois : entier DEBUT Lire (NumMois) DEBUT SELON NumMois FAIRE 1 : Ecrire(Janvier) 2 : Ecrire(Fvrier)

12 : Ecrire(Dcembre) SINON: Ecrire(Erreur) FINSELON FIN

Les Structures Rptitives

Objectif

Comprendre lintrt de la structure itratif et connatre sa signification. Connatre la structure itrative rpter Connatre la structure itrative tant que Connatre la structure itrative pour Apprendre choisir correctement une structure bien dtermine

Elments de contenu Problmatique Dfinition Le Schma Itratif avec Rpter

o Dfinition o Reprsentation

Algorithmique o Excution de la Boucle

Rpter

o Exemples Le Schma Itratif avec Tant que

o Dfinition o Reprsentation

Algorithmique

o Excution de la Boucle Tant que

o Exemples

Le Schma Itratif avec Pour o Dfinition o Reprsentation

Algorithmique o Excution de la Boucle

Pour

o Exercices

Exercice rcapitulatif Tableau Comparatif des Trois

Schmas Itratifs


55/102

Chapitre VI Les Structures Rptitives

I. Problmatique Supposons quon veuille afficher les 10 premiers entiers positifs. Si on utilise le traitement le plus

simple c'est--dire le traitement squentiel on aura lalgorithme suivant :

Algorithme affiche Dbut Ecrire(0) Ecrire(1) Ecrire(2)

Ecrire(9) Fin

Cette mthode reste raisonnable pour un petit nombre mais si on veut afficher les n premiers entiers avec n = 1000, lalgorithme devient alors absurde et impossible crire. Pour

pouvoir crire un tel algorithme, on aura besoin dune structure qui permet de rpter une instruction ou un groupe dinstructions. On doit alors utiliser des structures rptitives.

II. Dfinition Une structure rptitive est une structure qui rpte un mme traitement autant de fois que lon veut pour vue que la condition dexcution soit satisfaite. Cette structure sarrte lorsque cette condition nest plus vrifie. Il existe trois schmas de reprsentation dune structure rptitive savoir :

le schma Rpter le schma Tant que

le schma Pour Lutilisation dun tel ou tel schma dpend essentiellement de la nature du problme rsoudre.


56/102

III. Le Schma Itratif avec Rpter 1. Dfinition :

La boucle Rpter permet de rentrer dans la boucle quelque soit la condition et ritre lexcution jusqu' ce que la condition soit vrifie.

2. Reprsentation Algorithmique :

.

Rpter

Jusqu' (Condition_Arrt_Atteinte)

Remarques :

Dans une boucle Rpter, le traitement est excut au moins une seule fois quelle que soit

la valeur de la condition darrt. Dans une boucle Rpter, on parle de condition darrt ; quant elle est atteinte, on sort de

cette boucle. Il est indispensable dinitialiser correctement les variables de la condition darrt et de les

mettre jour la fin de chaque itration : condition ncessaire et obligatoire pour pouvoir reboucler.

La structure Rpter est conseille surtout pour les problmes indiquant dans leur nonc

une condition darrt.


57/102

3. Excution de la Boucle Rpter On suppose quon est dj entrain dexcuter un algorithme, et on a rencontr une boucle Rpter. 1re tape : on entre directement dans le traitement associ Rpter et on lexcute. 2me tape : on met jour les variables impliques dans la condition darrt. 3me tape : on teste la condition darrt : si elle nest pas atteinte, on revient la re tape, sinon on passe la 4me tape.

4me tape : la condition darrte tant atteinte, on sort de la boucle Rpter et on continue lexcution du programme partir de la 1re instruction qui vient aprs Jusqu.

Test V

F

Remarque : Si la condition darrt reste inchange (non mise jour), on risque de boucler indfiniment et par consquent le programme se bloque.

IV. Le Schma Itratif avec Tant que 1. Dfinition

La boucle Tant que permet dexcuter le corps de la boucle lorsque la condition

dexcution est vrifie ; on s'arrtera ds que la condition nest plus vrifie.

2. Reprsentation Algorithmique :

.

Initialisation des variables de la condition dexcution

Tant que (Condition_excution_vrifie) Faire

Fin Tant que

Dbut boucle Action Fin boucle


58/102

Remarques :

Dans une boucle Tant que, le traitement associ la boucle peut ne pas tre excut : la

condition dexcution nest pas vrifie ds le dpart. Dans une boucle Tant que, on parle de condition dexcution ; quant elle nest plus

vrifie, on sort de cette boucle. Il est indispensable dinitialiser correctement les variables de la condition dexcution et

de les mettre jour la fin de chaque itration : condition ncessaire et obligatoire pour pouvoir reboucler.

La mise jour de ces variables peut se faire soit par une lecture, soit par une affectation. La structure Tant que est conseille surtout pour les problmes indiquant dans leur nonc

une condition dexcution. Une condition dexcution est la ngation de la condition darrt.

3. Excution de la Boucle Tant que On suppose quon est dj entrain dexcuter un algorithme, et on a rencontr une boucle Tant que.

On suppose galement que les variables impliques dans la condition dexcution sont initialises.

1re tape : On teste si la condition dexcution est vrifie ou non : si oui alors aller la 2me tape sinon aller la 5me tape. 2me tape : On excute le traitement associ la boucle. 3me tape : On met jour les variables de la condition dexcution. 4me tape : Aller la 1re tape. 5me tape : On sort de la boucle et on continue lexcution du programme partir de la premire instruction qui vient aprs Fin Tant que.

Test V

F

Remarque : Si la condition dexcution reste inchange (non mise jour), on risque de reboucler indfiniment et par consquent le programme se bloque.

Dbut boucle Action Fin boucle


59/102

V. Le Schma Itratif avec Pour 1. Dfinition

La boucle Pour est une structure rptitive qui itre le mme traitement pour une plage de valeurs entires comprises entre une borne infrieure et une borne suprieure. La mise jour tant automatique, larrt du traitement de la boucle Pour se ralise lorsquon dpasse lune des bornes.

2. Reprsentation Algorithmique : Optionnel

.

Pour I allant de Val_initiale jusqu Val_finale, [Pas = Val_pas] Faire

Fin Pour

.

Avec

I : variable de type entier servant de compteur. Val_initiale : valeur initiale que va prendre I.

Val_finale : valeur finale que prendra I. Pas : contient une valeur entire indiquent la valeur de lincrmentation de I (mise jour de I ). Du fait que le nombre d'itrations est connu lavance, on se sert d'un compteur (ici I) qui sera initialis automatiquement la valeur initiale et sera incrment de la valeur du pas, jusqu' la valeur finale.

Remarques :

Le traitement de la boucle Pour est excut pour toutes les valeurs comprises entre Val_initiale et Val_finale.

Le sens de la boucle Pour peut tre croissant (Pas > 0) ou dcroissant (Pas < 0). Si la valeur du Pas = 0, on sera en prsence dune boucle infinie. Lincrmentation de I est automatique en fonction de la valeur du Pas. Dans une boucle Pour, on ne peut reprsenter quun seul compteur : on ne peut pas avoir

Pour I de et J de . ????

Dans une boucle Pour, si le Pas napparat pas, il vaut 1 par dfaut. La boucle Pour est conseille si le nombre ditrations faire est connu lavance.


60/102

3. Excution de la Boucle Pour : On suppose quon est dj entrain dexcuter un algorithme, et on a rencontr une boucle Pour. 1re tape : Affectation de Val_initiale au compteur I et vrification si cette valeur est dans lintervalle ou non.

2me tape : Si la valeur de I est dans lintervalle alors aller la 2me tape, sinon aller la 5me tape.

3me tape : Excution du traitement de la boucle. 4me tape : Incrmentation automatique de la valeur de I en fonction de la valeur du Pas (I I + Val_pas ou I I Val_pas) et retour la 2me tape. 5me tape : Sortie de la boucle et suite de lexcution du programme partir de la premire instruction qui vient aprs Finpour.

VI. Exercices dapplication: Nous allons re-crire notre algorithme avec les trois types quon vient de les voir

Exemple 1 : Solution : avec le schma Tant que Algorithme afficher Variable i : entier N : entier Dbut Lire (N) i := 0 Tant que i


61/102

Solution : avec le schma Rpter Algorithme afficher Variable i : entier N : entier Dbut Lire (N) i := 0 Rpter Ecrire(i) i := i + 1 Jusqu' i = N Fin

Contrairement la structure Tant que Faire le contrle de la condition darrt se fait la fin, on est donc sr que le corps de la boucle sera excut au moins une fois.

Solution : avec le schma Pour Algorithme afficher Variable i : entier N : entier Dbut Lire (N) Pour i Allant De 0 Jusqu (N-1) Faire Ecrire(i) Fin Pour Fin

Contrairement aux autres formes, ici on na pas besoin dincrmenter le compteur puisque lincrmentation est automatique. Le nombre de rptition peut tre connu puisquil sagit de la diffrence entre la valeur initiale et la valeur finale laquelle on ajoute la valeur 1 ((N-1) 0) + 1 = N).


62/102

Exemple 2 : En utilisant les 3 schmas itratifs, on vous demande dcrire les algorithmes

correspondants au calcul du factoriel dun entier N donn.

Solution : avec le schma Pour Algorithme Factoriel Variable N,I,F : entier Dbut Lire(N) F :=1 Pour I allant de 1 jusqu N Faire F := F * I FinPour crire(F) Fin Solution : avec le schma Tant que Algorithme Factoriel Variable N,I,F : entier Dbut Lire(N) F :=1 I :=1 (* initialisation *) Tant que (I N) crire(F) Fin


63/102

VII. Tableau Comparatif des Trois Schmas Itratifs :

Critre Rpter (1) Tant que (2) Pour (3) Traitement Au moins 1 fois De 0 N fois De Val_initiale

jusuq Val_finale Initialisation Oui avant Rpter Oui avant Tant que Oui : Val_initiale

Mise jour variable

Oui aprs traitement Oui aprs traitement Oui, Automatique en fonction du Pas

Sortie de la boucle Condition_arrt atteinte

Condition_excution non vrifie

Compteur dpassant les bornes

Type de la

condition

Expression logique avec ET, OU, etc.

Expression logique avec ET, OU, etc.

Une seule variable de type Entier

Passage dun

schma lautre Vers (2) oui sans

problme Vers (3) nest pas

toujours possible

Vers (1) oui sans problme

Vers (3) nest pas toujours possible



Le Type Tableau

Objectif Comprendre lintrt de lapplication dun type compos Connatre les tableaux unidimensionnels Connatre les tableaux deux dimensions.

Elments de contenu Problmatique Dfinition Reprsentation Algorithmique (tableau) Oprations de base sur un tableau

o Initialiser un Tableau o Remplir un Tableau o Affichage les lments d'un tableau o Exercice d'application

Recherche dans un Tableau o Introduction o Recherche Squentielle o Recherche Dichotomique

Exercices d'application Les Tableaux deux dimensions : Les Matrices

o Problmatique o Dfinition o Reprsentation Algorithmique

o Oprations de base sur une Matrice o Exercice d'application


65/102

Chapitre VII Le type Tableau

I. Problmatique Jusque l, et avec les structures de donnes simple quon a dj dfinies (entier, rel, caractre,), on nest capable de dfinir que des variables de types simples qui, un instant donn, ne peut contenir quune seule valeur, et laffectation dune nouvelle valeur dtruit

lancienne.

Si par exemple ou voulais reprsenter les moyennes annuelle de 50 tudiants, la dclaration de 50 variables de type Rel est alors absurde, il sera plus commode si on avait une structure qui puisse englober toutes ces donnes. On parlera alors du type Tableau

II. Dfinition Un tableau est une structure qui regroupe plusieurs lments de mme type, chaque lment est repr par un ou plusieurs indices avec lesquels on pourra accder sa valeur ou lui

en affecter une nouvelle. Chaque indice est compris entre une borne infrieure et une borne suprieure dfinie lors de la dclaration du tableau.

Un tableau est dit vecteur si le nombre de dimension est gal 1(unidimensionnel), matrice de dimension n si gale n>1(multidimensionnel). Remarques :

Un tableau est constitu dun nombre finie de cases contigus e situ en mmoire centrale. Un tableau est caractris par :

son nom

sa taille (borne infrieure et borne suprieure connues lavance) ses lments : chaque lment est dfini par son type et son contenu.

Laccs un lment du tableau se fait laide dun indice.


66/102

III. Reprsentation Algorithmique

Type

Nomtableau = Tableau[borne_inf .. borne_sup] de type_lment Variable Nomvar : Nomtableau

Indice : entier

Exemple : on veut dclarer un tableau de moyennes Type

Tab_Moy = Tableau[1..4] de rel Variable T : Tab_Moy I : entier (* indice du tableau T *) En mmoire, on va avoir une variable T comportant 4 cases et dans chacune on placera une moyenne qui est de type rel.

I 01 02 03 04

T 10.5 08.2 12 09.7

Le premier lment de T contient la valeur 10.5 ; on note T(1) := 10.5 Le deuxime lment de T contient la valeur 08.2 ; on note T(2) := 08.2 Dune manire gnrale, le Ime lment de T est not T(I) et contient une valeur de type rel. T(I) dsigne galement le contenu de la Ime case du tableau T.

Remarques :

Lindice du tableau doit tre obligatoirement de type entier. Il serait prfrable que cet indice soit initialis la valeur 1.

Un tableau, sil est rempli, ne doit pas faire lobjet dune lecture supplmentaire sauf sil sagit dune opration de mise jour o on doit modifier le contenu des lments du tableau.

La taille du tableau doit tre connu lavance.


67/102

IV. Oprations de base sur un tableau Pour reprsenter ces diffrentes oprations, on va utiliser un tableau T dentiers.

1. Initialiser un Tableau

Algorithme Ini_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier Dbut Pour I allant de 1 N faire T(I) := 0 FinPour Fin

2. Remplir un Tableau

Algorithme Remp_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier Dbut Pour I allant de 1 N faire Lire(T(I)) FinPour Fin Remarque : Lire (T (I)) consiste entrer une valeur partir du clavier et la mmoriser dans la Ime case du tableau T.

3. Affichage les lments dun tableau On va afficher les lments strictement positifs du tableau T

Algorithme Aff_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier Dbut Pour I allant de 1 N faire crire(T(I)) FinPour Fin


68/102

V. Recherche dans un Tableau 1. Introduction

Il sagit de rechercher un lment saisi partir du clavier, dans un tableau. Ds quon le trouve ce nest plus la peine de continuer le parcours du tableau ; on doit sortir et afficher un message

dexistence. Deux faons de faire :

soit faire une recherche squentielle,

soit faire une recherche plus optimise dite recherche dichotomique et dans ce cas, il y a des prcautions et des actions pralables faire.

2. Recherche Squentielle Algorithme Rech_Seq Constante N = 20 Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier X : entier (* X est llment chercher dans le tableau *) Trouve : Boolen (* cette variable va nous permettre de sortir ds quon trouve X *) Dbut Lire(X) I :=1 Trouve := Faux Tant que (I


69/102

3. Recherche Dichotomique Pour pouvoir appliquer la recherche dichotomique, il faut que :

le tableau T soit Rempli et le tableau soit Tri.

Il sagit dune recherche qui consiste rduire le temps de recherche dun lment X dans un tableau T qui doit tre obligatoirement tri. On commence par comparer X avec le contenu de llment du milieu : si X est infrieur cette valeur alors on va continuer la recherche dans la partie gauche du tableau T avec modification de la borne suprieure, sinon on continuera la recherche dans partie droite du tableau avec modification de la valeur de la borne infrieure. On sarrtera quand X serait gale la valeur du

milieu ou quand on dpasse les bornes du tableau.

Algorithme Dichoto Constante N=Val1 M= Val2 Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I,inf,sup,mil : entier X : entier (* X est llment chercher dans le tableau *) Dbut Lire(X) inf N sup M Rpter mil (inf+sup) div 2 Si X < T(mil) Alors sup mil 1 Sinon inf mil +1 FinSi Jusqu (X=T(mil)) ou (inf > sup) Fin


70/102

VI. Exercice dapplication crire un algorithme qui permet dafficher :

le nombre dapparition dune valeur X donne dans un tableau T, la position de la premire apparition de X,

la dernire position dapparition de X.

Algorithme StatX Constante N=20 Type Tab_Ent = Tableau[1..N] de Entier Variable I,X,NA,PP,DP : entier Dbut NA := 0 Lire(X) Pour I allant de 1 N Faire Si (T(I) = X) Alors NA := NA+1 FinSi FinPour crire(NA) PP := 0 Pour I allant de 1 N Faire Si (T(I) = X) Alors PP := I I :=999 A viter FinSi FinPour crire(PP) DP := 0 Pour I allant de N 1 Faire Si (T(I) = X) Alors DP :=I I := -999 FinSi FinPour crire(DP) Fin


71/102

VII. Les Tableaux deux dimensions : Les Matrices 1. Problmatique

Pour prsenter lintrt de ce paragraphe, on va partir de lexemple de la gestion des notes. On a propos alors la structure de donnes suivante :

Un tableau de n lments comportant les numros de CIN des tudiants TCIN. Un tableau de n lments comportant les notes des tudiants dans la premire preuve

TN1.

Un tableau de n lments comportant les notes des tudiants dans la deuxime preuve TN2.

Un tableau de n lments comportant les notes des tudiants dans la troisime preuve TN3.

Un tableau de n lments comportant les moyennes des tudiants TMOY. On suppose que chaque tudiant a pass 3 matires. Avec les structures vues jusque l (vecteurs), on ne peut pas esprer mieux. Malheureusement, elle peut poser parfois certains problmes :

Nombre important de vecteurs en mmoire ce qui entrane une lourdeur au niveau du fonctionnement de la machine.

Manipulation pouvant devenir difficile avec ce nombre important. Risque derreurs lors des calculs : la moindre distraction, ou le moindre oubli dinitialiser

un indice, entrane systmatiquement une erreur au niveau du traitement.

Solution Proposer une structure de donnes capable de regrouper toutes les donnes de mme type (notes, moyenne) pour un tudiant donn. Une telle structure existe et on parle alors de tableau deux dimensions ou encore Matrice.

2. Dfinition Un tableau deux dimensions appel galement matrice est une structure de donnes permettant dorganiser des informations de mme type en lignes et en colonnes. Il est caractris

donc par son nombre de lignes et son nombre de colonnes.


72/102


Constante Nbr_Lig = Val1 (* Nombre de Lignes *) Nbr_Col = Val2 (* Nombre de Colonnes *) Type

Matrice = Tableau [1..Nbr_Lig, 1..Nbr_Col] de Type_lment_Matrice Variable M : Matrice I, J : Entier (* I tant lindice des lignes et J celui des colonnes *)

Remarques

Le Type_lment_Matrice peut tre simple ou structur. Laccs un lment de la matrice ne peut se faire quavec deux indices : un lment

est identifi par son numro de ligne et son numro de colonne.

Si M est la matrice, M(I,J) dsigne llment de M situ la Ime Ligne et la Jme Colonne.

4. Oprations de base sur une Matrice On va supposer que le Type_lment_Matrice est Entier

a) Initialiser une matrice Pour I allant de 1 Nbr_Lig Faire Pour J allant de 1 Nbr_Col Faire M(I,J) := 0 FinPour FinPour

b) Remplir une matrice Pour I allant de 1 Nbr_Lig Faire Pour J allant de 1 Nbr_Col Faire Lire(M(I,J)) FinPour FinPour Remarque : La primitive Lire(M(I,J)) consiste lire partir du clavier un lment et le placer la Ime Ligne et la Jme Colonne.


73/102

c) Parcourir une matrice Par exemple, on veut afficher tous les lments de la matrice dont la valeur est suprieure 10.

Pour I allant de 1 Nbr_Lig Faire Pour J allant de 1 Nbr_Col Faire Si (M(I,J) >= 10) Alors crire(M(I,J)) FinSi FinPour FinPour

5. Exercice dapplication On va utiliser la structure matrice pour grer les notes et les moyennes des tudiants.

Solution Algorithme Gest_Notes Constante N=100 (* 100 tudiants grer par exemple *) M=4 (* 4 colonnes : les 3 notes et la moyenne *) Type Matrice = Tableau[1..N, 1..M] de rel TCIN = Tableau[1..N] de Entier (* cest un tableau qui va contenir les numros de CIN des 100 tudiants *) Variable CIN : TCIN M : Matrice I,J : Entier C1,c2,c3 : rel (* coefficients associs aux notes *) Dbut (* Remplir CIN et Matrice *) Pour I allant de 1 N Faire Lire(CIN(I)) Pour J allant de 1 M-1 Faire Lire(M(I,J)) FinPour M(I,4) := 0 (* la colonne relative la moyenne sera initialise zro *) FinPour (* Lecture des coefficients une seule fois *) Lire(c1,c2,c3) (* Calcul et affichage de la moyenne de chaque tudiant *) Pour I allant de 1 N Faire M(I,4) := (M(I,1)*c1 + M(I,2)*c2 + M(I,3)*c3) / (c1+c2+c3) crire(CIN(I), , M(I,4)) FinPour (* Classement des tudiants selon leur moyenne *) Pour I allant de 1 N-1 Faire Pour J allant de I+1 N Faire


74/102

Si M(I,4) < M(J,4) Alors Permute(M(I,4),M(J,4)) Permute(CIN(I),CIN(J)) FinSi FinPour FinPour (* Affichage par ordre de mrite *) Pour I allant de 1 N Faire crire(CIN(I)) crire(M(I,4)) FinPour FinAlgo

Le Type Chane de Caractres

Objectif

Connatre le type chane de caractre. Se familiariser avec les chanes de caractre. Connatre les fonctions prdfinies sur les chanes de caractres.

Elments de contenu

Introduction Dfinition Reprsentation Algorithmique Les Oprations de base sur les Chanes

o Lecture dune chane o Affichage o Initialisation

Les Fonctions Prdfinies sur les Chanes o La fonction LONG o La fonction CONCAT o La fonction POS o Les fonctions MAJ et MIN o La fonction SUBSTR

Exercice d'application


76/102

Chapitre VIII Le Type Chane de Caractres

I. Introduction Il sagit de trouver une structure de donnes permettant de reprsenter une suite de caractres. Deux structures peuvent tre envisages selon le mode de lexploitation quon veut appliquer cette suite :

Si on veut la manipuler caractre par caractre, la solution est dans ce cas facile deviner : il suffit dutiliser un tableau de caractres.

Si on veut exploiter cette suite dans sa totalit et en un seul coup, il conviendrait alors dutiliser ne structure de donnes capable de regrouper cette suite en une seule variable pour la manipuler dans sa totalit. Une telle structure sappelle Chane de Caractres.

II. Dfinition Une chane de caractres est une structure de donnes permettant de regrouper une suite

finie de caractres dans une mme variable pour pouvoir lexploiter dans sa totalit. Dans certains ouvrages, on dit quune chane de caractres est un tableau de caractres.

Remarque

Une chane de caractres peut tre exploite en tant que variable chane, dans ce cas on manipule des variables chanes : on peut lire un mot en un seul coup (Lire (nom)), ou bien en tant que tableau de caractres : parcourir la chane caractre par caractre (compter le nombre dapparition de la lettre A dans un nom).

III. Reprsentation Algorithmique

Type

Nom_Chaine = Chaine[Taille_Maxi] Variable Nom_Variable : Nom_Chaine

Remarque

Taille_Maxi dsigne la taille maximale que peut avoir une chane de caractres ; il doit tre strictement positif.


77/102

Exemple Type Nom = Chaine[20] Variable Nom1, Nom2 : Nom On a dclar une chane Nom qui est de taille maximale 20 et deux variables Nom1 et Nom2.

Remarque

Dans certains langages de programmation et lors de la dclaration dune chane de caractres, on peut ne pas indiquer la taille maximale. En fait, cest le langage qui sen occupe et affectera automatiquement la taille maximale quil puisse supporter. En Pascal, cette taille est de 255.

IV. Les Oprations de base sur les Chanes 1. Lecture dune chane

Lire (Nom1,Nom2)

2. Affichage

crire(Nom1,Nom2) 3. Initialisation

Nom1 :: (* chane vide *) Nom2 :=

V. Les Fonctions Prdfinies sur les Chanes Les langages de programmation comportent un jeu de fonctions prdfinies sur le type Chane de caractres. On cite principalement les fonctions suivantes :

La fonction LONG qui retourne la longueur dune chane. La fonction CONCAT qui rassemble plusieurs chanes en une seule. La fonction POS qui retourne la position dune sous chane dans une chane. La fonction MAJ qui rend une chane en Majuscules La fonction MIN qui rend une chane en minuscules La fonction SUBSTR qui permet dextraire une sous-chane partir dune chane.


78/102

1. La fonction LONG Cette fonction lorsquelle est applique une chane de caractres, retourne sa taille relle

et non pas la taille maximale.

Algorithmiquement, elle est note

LONG (nom_chaine)

Exemple CH : chaine X : entier CH :=ISET du kef X := LONG(CH) crire(LONG(CH) Dans la variable X, on va trouver la valeur 11.

Remarque

La longueur dune chane tant un entier, on ne peut pas le mettre isol dans un algorithme ; on doit laffecter une variable de type entier ou on doit le mettre dans une primitive dcriture.

2. La fonction CONCAT Cette fonction permet de concatner plusieurs chanes non ncessairement de mme taille, en une seule.

Algorithmiquement, elle est note

CONCAT (CH1,CH2,,CHN)

o les CHI sont des chanes.

Exemple Nom : Chane Prenom : Chane Etudiant : Chane Etudiant CONCAT(Nom, Prenom) crire(CONCAT(Nom, Prenom) Dans la variable Etudiant, on va trouver une chane contenant le nom et le prnom ensemble.

Remarque

La concatnation de plusieurs chane est une chane , on ne peut pas la mettre isole dans un algorithme ; on doit laffecter une variable de type Chane ou on doit la mettre dans une primitive dcriture.


79/102

3. La fonction POS La fonction POS retourne la position partir de laquelle une sous-chane apparaisse dans

une chane. Dans le cas o cette sous-chane nexiste pas, elle retourne la valeur zro. Algorithmiquement, cette fonction est note POS et le rsultat est un entier.

X := POS (nom_chane, nom_sous_chane)

X prendre pour valeur, la position partir de laquelle la sous_chane apparaisse dans la chane.

Exemple CH := ISET de Kef CH1 := Kef X :=POS (CH, CH1) On trouvera dans X la valeur 9 ; de mme pour X POS(CH,Rads), on trouvera le mme rsultat.

Remarque

La position tant un entier, on ne peut pas la mettre isole dans un algorithme ; on doit laffecter une variable de type entier ou on doit la mettre dans une primitive dcriture.

4. Les fonctions MAJ et MIN Ces fonctions permettent de transformer une chane en majuscules, respectivement en minuscules, en une chane en minuscules, respectivement en majuscules. Algorithmiquement, on les note par

MAJ (CH) ou MIN (CH)

Exemple CH:=set CH:=MAJ(CH) dans ce cas CH prendra la valeur ISET CH:=MIN(CH), on aura dans CH l

Documents

Cours AlgoFHG