Program Mat Ion Structuree Version Mars2001

Programmation structurée

LA PROGRAMMATION STRUCTUREE

page n° 1

Programmation structurée

SOMMAIRE CARACTERISTIQUES GENERALES DE LA METHODE DE PROGRAMMATION STRUCTUREE..5 1APPARITION DE L'INFORMATIQUE.....................................................................................................6 1.1Définition de l'Informatique......................................................................................................................6 1.2Rôle de l'Informatique...............................................................................................................................7 1.3Spécificité de l'Informatique......................................................................................................................8 2 LE SYSTEME INFORMATIQUE............................................................................................................9 2.1Définition d'un système informatique........................................................................................................9 2.2Caractéristiques d'un système informatique.............................................................................................9 2.3Le programme ...........................................................................................................................................9 2.3.1Définition d'un programme...............................................................................................................................9 2.3.2Définition d'une instruction...............................................................................................................................9 2.3.3Représentation du système informatique........................................................................................................10 2.3.4Exemple de programme...................................................................................................................................10 2.3.5La programmation...........................................................................................................................................10

3CARACTERISTIQUES DE LA METHODE DE PROGRAMMATION STRUCTUREE.........................11 3.1 schéma de résolution d'un problème......................................................................................................11 3.2 Les phases de résolution d'un problème................................................................................................11 3.3Détail de la phase d'analyse....................................................................................................................11 3.3.1La démarche retenue.......................................................................................................................................12 3.3.2Principe de décomposition..............................................................................................................................13 3.3.3Détail de la méthode descendante...................................................................................................................13 3.3.4 Détail de la méthode Analyse ascendante .....................................................................................................14 3.3.5Les méthodes dirigées par les données...........................................................................................................14 3.3.6L'algorithme....................................................................................................................................................15 3.3.7Les tests...........................................................................................................................................................16

4 LA NECESSITE D'UNE METHODE.....................................................................................................17 4.1Caractéristiques et conséquences de la programmation sans méthode.................................................17 FORMALISME DE L'ENVIRONNEMENT D'UN PROBLEME.................................................................18 5NOTION DE PROCESSEUR ET D'ENVIRONNEMENT........................................................................19 6NOTION D'ACTION ET DE PRIMITIVE...............................................................................................20 6.1Définition d'une Action............................................................................................................................20 6.2Définition d'une Primitive.......................................................................................................................20 6.3Nouvelle approche de la notion d'Algorithme........................................................................................21 7NOTION D'OBJET..................................................................................................................................22 7.1Définition d'un objet................................................................................................................................22 7.2Caractéristiques d'un objet......................................................................................................................22 8NOTION DE CONSTANTE ET DE VARIABLE....................................................................................24 8.1 Intérêt des constantes.............................................................................................................................24 8.2Intérêt des variables................................................................................................................................24 9LES TYPES D'OBJET ET LEURS OPERATEURS ASSOCIES..............................................................25 9.1Le type entier...........................................................................................................................................25 9.2Le type réel..............................................................................................................................................25 9.3Le type booléen........................................................................................................................................25 9.4 Le type caractère....................................................................................................................................26 9.5Le type chaîne..........................................................................................................................................26 9.6Le type enregistrement............................................................................................................................26 9.7Le type pointeur.......................................................................................................................................26 10LES EXPRESSIONS ET LA PRIORITE DES OPERATEURS..............................................................27 10.1 Composition d'opérations élémentaires : Expressions........................................................................27 10.2Tableau des opérateurs par ordre de priorité décroissante.................................................................27 11LES PRIMITIVES DE BASE EN ALGORITHMIQUE..........................................................................28 11.1Notion de lecture...................................................................................................................................28 11.2Notion d'affectation...............................................................................................................................29 11.3Notion d'initialisation............................................................................................................................31 page n° 2

Programmation structurée 11.4 Notion d'écriture...................................................................................................................................31 11.5Les Commentaires..................................................................................................................................32 STRUCTURE GENERALE D'UN ALGORITHME........................................................................................33 12 DEFINITION D'UN ALGORITHME....................................................................................................34 13 STRUCTURE D’UN ALGORITHME...................................................................................................34 13.1Déclaration des variables et des constantes méthode n°1 :.................................................................35 13.2Déclaration des variables et des constantes méthode n°2 :.................................................................35 13.3Définition des paramètres méthode n°1 :..............................................................................................36 13.4Définition des paramètres méthode n°2 :..............................................................................................36 13.5Le bloc instructions................................................................................................................................36 13.5.1Présentation générale.....................................................................................................................................36

14EXERCICE RECAPITULATIF.............................................................................................................37 L'ORDONNANCEMENT....................................................................................................................................39 15RAPPEL DE LA METHODOLOGIE EMPLOYEE EN P.S...................................................................40 16LA THEORIE PAR L'EXEMPLE..........................................................................................................40 16.1Exposé du problème...............................................................................................................................40 16.2Etude de l'environnement de départ .....................................................................................................40 16.3Etude du traitement...............................................................................................................................42 16.4Nécessité et caractéristiques de l'ordonnancement..............................................................................42 17EN RESUME.........................................................................................................................................44 APPLICATION DE LA METHODE AUX ALTERNATIVES ET ITERATIONS......................................45 18 LES STRUCTURES FONDAMENTALES ..........................................................................................46 18.1Notion de programme propre................................................................................................................46 18.2Enchaînement des actions.....................................................................................................................46 18.3Structure alternative ou conditionnelle.................................................................................................47 18.4Structure itérative..................................................................................................................................48 18.5Exercices................................................................................................................................................49 19LES STRUCTURES COMPLÉMENTAIRES..............................................................................................................50 19.1L'alternative généralisée.......................................................................................................................50 19.2La répétition...........................................................................................................................................51 20 EXERCICES ET CORRIGÉS DES EXERCICES...............................................................................................53 NOTION DE SOUS-PROGRAMME.................................................................................................................63 21LE SOUS-PROGRAMME......................................................................................................................64 21.1Rappel de la définition d’un programme..............................................................................................64 21.2Définition d’un sous-programme...........................................................................................................64 21.3Les paramètres.......................................................................................................................................64 21.3.1Définition d'un paramètre..............................................................................................................................64

21.4Utilité des paramètres à travers un exemple:.......................................................................................65 21.5Schéma de synthèse................................................................................................................................65 FONCTIONS ET PROCEDURES....................................................................................................................66 22NOTION DE PARAMETRE..................................................................................................................67 22.1Ecriture d'un algorithme paramétrique................................................................................................67 22.2Intérêt des paramètres...........................................................................................................................69 22.3Paramètres formels et paramètres effectifs...........................................................................................69 22.4Les paramètres données.........................................................................................................................70 22.5Les paramètres résultats........................................................................................................................70 22.6Passage par valeur, passage par adresse.............................................................................................70 22.6.2Passage par adresse ( @ ).............................................................................................................................71

22.7Variables globales et variables locales.................................................................................................73 23NOTION DE FONCTION ET DE PROCEDURE..................................................................................73 23.1Intérêts...................................................................................................................................................73 23.2Caractéristiques.....................................................................................................................................73 23.3Différences entre fonction et procédure................................................................................................74 23.3.1Les particularités des fonctions.....................................................................................................................74 23.3.2Les particularités des procédures..................................................................................................................74

23.4Parallèle entre procédure et fonction...................................................................................................74 23.5les prédicats...........................................................................................................................................74 23.6EXERCICE N° 5....................................................................................................................................75 page n° 3

Programmation structurée LES STRUCTURES DE DONNEES STATIQUES..........................................................................................78 24LES TABLEAUX..................................................................................................................................79 24.1Intérêt des tableaux...............................................................................................................................79 24.2Caractéristiques.....................................................................................................................................79 24.2.1Définition d'un tableau..................................................................................................................................79 24.2.2Les différents types de tableaux....................................................................................................................79 24.2.3Les notions d'indice et de rang......................................................................................................................81 24.2.4Accés aux éléments du tableau......................................................................................................................81

24.3Opérations sur les tableaux...................................................................................................................82

24.3.1Etude du tableau unidimensionnel : le vecteur.............................................................................................82

25LES ENREGISTREMENTS...................................................................................................................87 26EXERCICES..........................................................................................................................................88 NOTIONS SUR LES FICHIERS.......................................................................................................................91 27GENERALITES SUR L'ORGANISATION DES INFORMATIONS......................................................92 28NOTION DE FICHIER..........................................................................................................................92 28.1Définition d'un fichier............................................................................................................................92 28.2Les principaux accès..............................................................................................................................93 28.2.1Accès séquentiel............................................................................................................................................93 28.2.2Accès direct...................................................................................................................................................93

28.3Les éléments du fichier..........................................................................................................................93 28.3.1Notion 28.3.2Notion 28.3.3Notion 28.3.4Notion

d'enregistrement logique...................................................................................................................93 de rubrique ou champ........................................................................................................................94 de caractère........................................................................................................................................95 d'indicatif...........................................................................................................................................95

28.4Les primitives d’accès...........................................................................................................................95 29LE TRANSFERT DES DONNEES........................................................................................................97 30CE QU'IL FAUT RETENIR...................................................................................................................99 31EXERCICES........................................................................................................................................100 A N N A L E S.....................................................................................................................................................104 32 EXAMEN DE L’EA2/FS DU BSTAT 2000..........................................................................................105 33 EXAMEN BLANC DE L’EA2/FS DU BSTAT 2001............................................................................113 34EXAMEN DE L’EA2/FS DU BSTAT 2001...........................................................................................118

page n° 4

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

CARACTERISTIQUES GENERALES DE LA METHODE DE PROGRAMMATION STRUCTUREE

.

page n° 5

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

1 APPARITION DE L'INFORMATIQUE

Depuis la nuit des temps l'homme cherche des solutions aux problèmes qu'il rencontre.

PROBLEME

REFLEXIO N

SOLUTION

L'espèce humaine en évoluant a fait de plus en plus appel à des outils, des savoirfaire et des modèles qu'elle inventait pour résoudre ses problèmes et modifier son environnement. Si l'on se réfère à la préhistoire, on peut citer, à titre d'exemples l'apparition des outils en pierre taillée ,en pierre polie, puis en bronze et en fer. On peut également trouver des exemples similaires dans des périodes plus "contemporaines" comme l'apparition des mathématiques, de la règle à calcul, de la machine à calculer etc... Dans le cadre de cette perpétuelle évolution, les années d'après guerre ont vu l'apparition d'un nouvel outil : l'informatique. Le premier véritable ordinateur a été créé en 1942 à BERLIN : il s'agissait du Z3. En 1946 on construit l'ENIAC qui suit le modèle inventé par Mr Von Neumann, considéré comme le fondateur de l'informatique. Il comporte 800 km de fils, 18000 lampes, 50000 commutateurs et pèse 30 tonnes.

1.1

Définition de l'Informatique. On peut trouver plusieurs définitions de l'informatique. Si l'on se réfère à la norme AFNOR (Association Française de NORmalisation).

L'INFORMATIQUE est l'ensemble des disciplines scientifiques applicables au traitement de l'information effectué notamment par des moyens automatiques. L'académie française l'a pour sa part défini en 1966 dans les termes suivants: L'INFORMATIQUE est la science du traitement rationnel, notamment par machines automatiques, de l'information considérée comme le support des connaissances humaines dans les domaines techniques, économiques et sociaux.

page n° 6

Programmation structurée

1.2

Caractéristiques générales de la méthode de programmation structurée

Rôle de l'Informatique. Des différentes définitions de l'informatique, on peut en déduire que :

L'informatique sert à traiter des données.

(INFORMATIQUE) TRAITEMENT

DONNEES

RESULTATS

Qu'est-ce qu'une donnée? Une donnée est une entité connue, déterminée dans l'énoncé d'un problème qui sert à découvrir ce qui est inconnu (Source Petit Robert). Dans cette acception, le terme de donnée est opposé à celui de résultat. En informatique, cette définition n'est pas à prendre au pied de la lettre car un résultat peut également être une donnée pour un autre traitement. En particulier si ce résultat est stocké sur un support il devient une donnée pour les personnes qui l'utiliseront dans le futur. DONNE E A

DONNE E B

TRAITEMENT N°1

DONNE E C DONNE E D

TRAITEMENT N°3

TRAITEMENT N°2

DONNE E E

Les données B et C sont le résultat du traitement N°1 mais se sont également les données initiales des traitements N°2 et 3 En informatique, une donnée ce peut être : - une information permettant de définir ou de quantifier n'importe quoi, - un code correspondant à un événement provenant de l'extérieur via un capteur quelconque, - un code émis vers l'extérieur (pouvant déclencher d'autres mécanismes).

page n° 7

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

Un traitement Un traitement est le déroulement systématique d'une suite d'opérations.

Une opération Une opération est une action définie qui, appliquée à toute combinaison permise de données, en effectue le transfert ou engendre une nouvelle donnée.

Un transfert Un transfert est un déplacement de données sans modification de leur valeur. EXEMPLES : Opération arithmétique ADDITION des nombres 3 + 5 = 8

Opération le plus petit de 3 et 5

3 et 5 sont les opérandes

3

8 est le résultat + est l'opérateur

Le résultat est ici obtenu par transfert de données.

Dans cet exemple on engendre une nouvelle donnée.

Une opérande Une opérande est une donnée à laquelle s'applique une opération.

Un opérateur Un opérateur (dans le cas présent) est un symbole indiquant la nature de l'opération à effectuer.

1.3

Spécificité de l'Informatique. L'informatique sert à traiter des données mais elle n'est pas seule à avoir ce rôle.

Ce qui fait sa spécificité c'est qu'elle est capable de traiter des quantités énormes de données en très peu de temps. En dehors de cela tout ce qui est réalisable par l'informatique peut l'être par d'autres moyens (en y mettant le temps...).

page n° 8

Programmation structurée

2 2.1

Caractéristiques générales de la méthode de programmation structurée

LE SYSTEME INFORMATIQUE Définition d'un système informatique.

Un système informatique est un ensemble d'éléments (matériels - hardware ou logiciel software) qui permet de rendre le service informatique escompté.

DONNEES

SYSTEME INFORMATIQUE

RESULTATS

Par souci de simplification, nous appellerons ce système informatique ORDINATEUR en gardant à l'esprit que c'est un abus de langage puisque l'ordinateur n'est en réalité que l'élément central du SI.

2.2

Caractéristiques d'un système informatique.

Tout matériel devant réaliser un traitement informatique doit être en mesure de : - récupérer, selon divers modes, les données à traiter, - effectuer les traitements désirés sur ces données, - fournir à l'utilisateur les données modifiées ou un code correspondant à un traitement à réaliser. Pour effectuer le traitement désiré sur les données, il est indispensable que l'ordinateur connaisse ce traitement. On pourrait envisager de lui communiquer élément par élément, mais cette méthode ne permettrait pas d'exploiter sa qualité fondamentale : la rapidité de fonctionnement. On regroupe donc tous les éléments du traitement dans ce qu'on appelle un programme. Ce programme est ensuite globalement communiqué à l'ordinateur en vue de son exécution.

2.3 2.3.1

Le programme Définition d'un programme.

Un programme est donc une suite d'instructions établie en vue de son traitement par un ordinateur. Il doit être mémorisé pour pouvoir être exécutéautomatiquement dès que l'utilisateur en donne l'ordre. Nous voyons apparaître ici deux termes nouveaux : INSTRUCTION et MEMORISATION.

2.3.2

Définition d'une instruction.

Une instruction est une expression décrivant une partie du traitement en désignant la nature des opérations et le cas échéant les opérandes sur lesquelles elle porte ainsi que la destination à donner au résultat.

page n° 9

Programmation structurée

2.3.3

Caractéristiques générales de la méthode de programmation structurée

Représentation du système informatique

Le fait que le programme doive être mémorisé pour être exécuté, nous conduit à une représentation un peu plus détaillée du système informatique.

DONNEES MEMOIRE UNITE de TRAITEMENT

RESULTATS

PROGRAMME

Un système informatique apparaît donc maintenant comme composé : - d'une mémoire centrale qui contient les programmes et les données, - d'une unité de traitement qui exécute le programme, - et pour mémoire d'unités périphériques d'entrée et de sortie permettant les échanges avec l'extérieur.

2.3.4

Exemple de programme Entrez la Donnée1 Entrez la Donnée2 Faire Résultat = Donnée1 + Donnée2 Ecrire Résultat On comprend le rôle joué par un programme dans le cadre du travail d'un ordinateur. La réalisation d'un tel programme s'appelle la programmation.

2.3.5

La programmation

La programmation est donc le moyen de définir et de spécifier à l'ordinateur l'ensemble des opérations nécessaires pour résoudre un problème. Si la réalisation d'un programme permettant l'addition de deux entiers ne pose aucune difficulté, il n'en est pas de même pour résoudre les problèmes plus complexes.

page n° 10

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

3 CARACTERISTIQUES DE LA METHODE DE PROGRAMMATION STRUCTUREE 3.1

schéma de résolution d'un problème. DONNEES ORDINATEUR

PROBLEME

RESULTATS

PROGRAMME

Deux facteurs font de la programmation un travail difficile : d'une part la distance entre le problème posé et le programme, d'autre part la diversité des formes que peut prendre un programme.

3.2

Les phases de résolution d'un problème. Le passage du problème au programme se fait en deux étapes : −

résolution du problème, c'est la phase d'analyse,

− expression de la solution dans un langage acceptable par le système informatique sur lequel on travaille, c'est la phase de codage.

3.3

Détail de la phase d'analyse.

La phase d'analyse passe par la formulation de l'énoncé, la recherche d'une solution explicite, exprimée par son algorithme.

ANALYSE

Problème

Enoncé

CODAGE

Algorithme

page n° 11

Programme

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

Le passage par un énoncé clair et exhaustif est indispensable. En effet, l'expérience prouve que l'énoncé initial d'un problème posé à un informaticien est en général formulé dans une langue naturelle (par exemple le français) ce qui le rend souvent flou, incomplet et parfois même incohérent. Il décrit (dans le meilleur des cas ) les caractéristiques du résultat du problème. Par contre, le programme est écrit dans un langage artificiel, formel et précis. Il décrit un "calcul", permettant, à partir des données du problème, d'obtenir le résultat. La reformulation de l'énoncé est donc dans la plupart des cas indispensable.

3.3.1

La démarche retenue

Le but est d'obtenir des résultats, qui seront sous différentes formes: papier, fichier magnétique, écran ... Ces résultats sont les sorties du programme.

PROGRAMME

SORTIES

Ces résultats doivent être connus et définis, c'est l'étude de: L'ENSEMBLE DES DONNEES A OBTENIR (E.D.O.) C'EST L'ETUDE DU QUOI (c'est à dire du RESULTAT) Pour produire ces résultats, tout programme utilise des données en entrée:

PROGRAMME

ENTREES

Ces données doivent être définies, et le programmeur doit savoir où les trouver, ou comment les fabriquer. C'est l'étude de: L'ENSEMBLE DES DONNEES A UTILISER (E.D.U.) C'EST L'ETUDE DU AVEC QUOI

ENTREES ES

PROGRAMME

SORTIES

Lorsque l'on sait ce que l'on veut obtenir et ce que l'on dispose pour arriver à ces fins, il ne nous reste plus qu'à voir comment. C'EST L'ETUDE DU COMMENT (ou UT unité de traitement) page n° 12

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

Les étapes d'analyse du programme sont alors dans l'ordre :

ENTRE E

SORTIE

3.3.2

PROGRAMME

Principe de décomposition

Nous venons de voir que la résolution de notre problème va se faire par l'étude successive de trois modules EDO, EDU, UT. L'étude de ces modules va se faire de manière méthodique en employant la méhode descendante ou "Top down design". Cette méthode consiste à partir de la fonction de plus haut niveau pour "descendre" petit à petit vers les fonctions de plus bas niveau.

3.3.3

Détail de la méthode descendante

La décomposition passe par la description d'actions intermédiaires. Les principes généraux mis en oeuvre résultent de quelques remarques : - pour aborder une tâche complexe, il est indispensable de la diviser, - la division s'arrête quand chaque partie est suffisamment petite pour que son fonctionnement puisse être vérifié facilement, - l'analyse du problème ne doit rien laisser au hasard et pour cela il est fondamental de procéder en progressant du général au particulier et non pas le contraire. On peut représenter le processus de décomposition par un arbre. La racine de l'arbre symbolise la tâche à effectuer, chaque ramification représente une décomposition jusqu'aux éléments terminaux (feuilles) qui sont, en fin d'analyse, des actions élémentaires.

PROBLEME GLOBAL AE 2

AI1 AI11

AE111

AE12

AE3 1

AI3 AE3 2

AE 4

AE3 AE3 3

AE3 4

AE = Action Elémentaire AI = Action Intermédiaire

AE112 page n° 13

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

Pour atteindre le niveau de décomposition suivant, chaque action non élémentaire est divisée en plusieurs sous-actions ou actions intermédiaires. Du point de vue de l'environnement, ceci conduit à l'apparition de nouveaux éléments. Il est clair qu'au cours de la conception d'un algorithme, on procède à de nombreux retours en arrière, chaque étape pouvant conduire à revenir à un niveau supérieur. La méthodologie descendante joue un double rôle : celui de support à la compréhension même du problème (permettant de n'en négliger aucun aspect), aussi bien que celui d'un cadre pour sa résolution. Elle débouche sur la réalisation d'un algorithme.

3.3.4

Détail de la méthode Analyse ascendante

Elle consiste à identifier dès le début les actions élémentaires qu'il faudra savoir résoudre. Avec la méthode descendante appliquée de façon rigide, il est possible de rencontrer ou de résoudre plusieurs fois le même problème ou des problèmes voisins. La méthode ascendante consiste à déterminer les objets (ou classes d'objets) de l'application, une classe d'objets étant caractérisée: − par un ensemble de valeurs ou d'états (on parle aussi d'attributs ou de propriétés), − et par un ensemble d'actions ou d'opérations sur ces objets d'autre part.

3.3.5

Les méthodes dirigées par les données

Dans la méthode descendante, l'accent est mis sur la décomposition en actions. Les données manipulées et nécessaires sont affinées au fur et à mesure mais ne jouent pas un rôle stratégique dans la décomposition. Dans un système de gestion de base de données (SGBD), le programmeur commence par décrire les données de l'application (parce que les données jouent le rôle central). Il utilise pour cela un langage de description de données (LDD) qui permet de décrire les objets ou les classes d'objets qu'il utilise ainsi que les associations entre classes d'objets et les contraintes d'intégrité éventuelles. On construit ainsi le modèle conceptuel des données. On écrit ensuite les programmes qui permettront la création, la mise à jour de la base de données en utilisant un langage de manipulation de données (LMD). page n° 14

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

Evolution de la programmation impérative vers la programmation objet 1ère étape: la programmation procédurale Langages Algol, Pascal, C Notions de types Structures de contrôles

2ème étape: la programmation modulaire A un module correspond un sous-système, ce sous-système rend au reste de l'application un service. Pour l'utilisateur, il suffit de savoir ce que fait le module et comment on y accède. C'est le premier pas vers le composant logiciel réutilisable.

3ème étape: la programmation par type générique (ou abstraction) Une abstraction fait ressortir les caractéristiques essentielles d'un objet (qui le distinguent de tous les autres genres d'objets) et donc procure des frontières conceptuelles rigoureusement définies par rapport au point de vue de l'observateur. (Ex : le chat vu par la mémère et par le vétérinaire).

4ème étape: les objets L'accent est mis sur la réutilisation et l'adaptation en utilisant les mécanismes d'héritage (ou de sous-typage) et la programmation par interfaces. On décrit le monde comme étant formé d'objets ainsi que les relations existant entre les objets.

3.3.6 3.3.6.1

L'algorithme Définition d'un algorithme

Un algorithme est la description, dans un langage universel, des opérations nécessaires pour résoudre un problème L'algorithme permet donc de décrire la méthode de résolution d'un problème dans un langage "proche du français" donc compréhensible par le plus grand nombre. L'analyse sera ainsi guidée par un langage adapté aux langages de programmation sans avoir à suivre les règles syntaxiques et sémantiques d'un langage plutôt que d'un autre. L'algorithme est donc le résultat d'une démarche logique de résolution d'un problème appelée méthodologie de programmation.

page n° 15

Programmation structurée

Caractéristiques générales de la méthode de programmation structurée

En résumé : la méthodologie est donc le fait de poser un problème et de le traiter de manière structurée pour la programmation en s'appuyant sur la conception d'un algorithme qui suit des règles bien précises. Encore appelée Programmation Structurée elle permet, grâce au découpage d'un problème global en un certain nombre de sous-problèmes, une programmation beaucoup plus simple. Cette décomposition permet ainsi, de réduire de niveau en niveau, la complexité du problème initial.

3.3.6.2

Propriétés d'un algorithme

LA PRECISION Un algorithme doit indiquer : - l'ordre des étapes - Le début et l'arrêt des actions - Comment choisir entre les différentes possibilités LE DETERMINISME Une suite d'exécutions de l'algorithme partant des mêmes données doit obtenir les mêmes résultats. LE CARACTERE FINI L'algorithme doit être fini dans le temps, c'est à dire s'arrêter. Les algorithmes reposent sur un nombre restreint de structures fondamentales qui feront l'objet d'une étude détaillée. exemple : la réalisation d'une recette de cuisine

3.3.7 3.3.7.1

Les tests Intérêt

En programmation, il n'est pas concevable de livrer un programme qui "marche presque dans tous les cas". Aussi la phase de test est impérative avant de délivrer "l'Aptitude au service" pour un programme. Seuls ces tests nous permettrons d'être sûr de la qualité de notre produit.

3.3.7.2

Caractéristiques du jeu d'essai

Le jeu d'essai doit être un échantillon représentatif des situations possibles. Il doit prendre en compte avec beaucoup de précision les cas particuliers qui sont généralement la source de la majorité des erreurs détectées après la phase de conception.

3.3.7.3

La trace

La trace est un tableau représentant le déroulement séquentiel du jeu d'essai. Elle ne constitue en aucun cas une preuve de correction de l'algorithme mais permet de concrétiser son déroulement, et par là même de faciliter sa compréhension. page n° 16

Programmation structurée

4 4.1

Caractéristiques générales de la méthode de programmation structurée

LA NECESSITE D'UNE METHODE Caractéristiques et conséquences de la programmation sans méthode.

1) Commencer par écrire un programme 2) Tester ce programme et détecter les erreurs 3) Corriger chaque erreur détectée en modifiant un morceau de programme (ceci s'appelle mettre des rustines) 4) Retourner au 2 Cette façon de procéder peut parfois avoir quelques succès relatifs avec de très petits programmes. Au niveau supérieur de nombreux projets élaborés avec ce manque de méthode ont dû être abandonnés faute d'une mise au point satisfaisante

page n° 17

Programmation structurée

Formalisme de l’environnement d’un problème

FORMALISME DE L'ENVIRONNEMENT D'UN PROBLEME

Page n° 18

Programmation structurée

Formalisme de l’environnement d’un problème

5 NOTION DE PROCESSEUR ET D'ENVIRONNEMENT. Considérons les deux exemples suivants: EX1 - Confection de frites

EX2 - Calcul de la moyenne de deux notes à l'aide d'une calculatrice

A) Eplucher les pommes de terre. B) Couper les pommes de terre en frites C) Laver les frites crues. D) Mettre de l'huile à chauffer dans une friteuse. E) Verser les frites dans l'huile. F) Lorsque les frites sont cuites les retirer de l'huile.

A) Appuyer sur la touche "C". B) Taper la première note. C) Appuyer sur "+". D) Taper la seconde note. E) Appuyer sur "/".. F)Taper "2". G) Appuyer sur " = ". Le résultat est affiché

Les énoncés EX1 et EX2 décrivent chacun un certain travail. Nous appellerons PROCESSEUR toute entité capable de comprendre un tel énoncé et d'exécuter le travail indiqué.

Dans le cas des énoncés EXI et EXII une personne sachant lire et disposant des ustensiles nécessaires, peut être un processeur convenable. Pour qu'un processeur puisse mener à terme la tâche qui lui a été confiée, il faut mettre à sa disposition les outils et matériaux indispensables. Dans l'exemple I, les ustensiles seront : des pommes de terre, un couteau, une friteuse, de l'huile.

Tout ce qui est nécessaire (ustensiles) à la réalisation d'unetâche constitue l'ENVIRONNEMENT de cette tâche. Pour exécuter son travail, le processeur va, à l'aide des outils, mesurer et modifier les matériaux et, par conséquent, modifier son environnement.

page n° 19

Programmation structurée

Formalisme de l’environnement d’un problème

6 NOTION D'ACTION ET DE PRIMITIVE. 6.1

Définition d'une Action

On appelle ACTION tout événement de durée finie dans le temps qui examine ou modifie l'environnement. Ou encore Etant donné un environnement décrit formellement comme un ensemble d'objets, une action sur cet environnement est un événement de durée finie qui, à partir d'un état initial particulier de l'environnement, a pour conséquence un nouvel état bien défini.

6.2

Définition d'une Primitive

Considérons l'exemple d'un adolescent qui veut calculer la consommation moyenne pour 100 km de son vélomoteur après une promenade. 1) 2) 3)

Ecrire le nombre de kilomètres parcourus Ecrire le nombre de litres de carburant consommé Faire la règle de trois.

On constate que si les actions 1 et 2 sont réalisables telles qu'elles par la personne, il n'en est pas de même pour l'action 3 qui doit être décomposée pour être réalisée. 3)

Diviser le nombre de litres par le nombre de km Multiplier le résultat obtenu par 100.

Pour un processeur, une action est primitive si l'énoncé de cette action est à lui seul suffisant pour que le processeur puisse l'exécuter sans information supplémentaire. (Dans l'exemple précédant le résultat de la division était une information supplémentaire nécessaire pour exécuter l'action). La description de l'ensemble des actions élémentaires qu'un processeur est capable d'effectuer le détermine totalement. On appelle ces actions les PRIMITIVES.

page n° 20

Programmation structurée

Formalisme de l’environnement d’un problème

Toute action à exécuter par un processeur doit être décomposée en utilisant les primitives de ce processeur. Il existe généralement plusieurs utilisations performantes) des primitives pour obtenir le même résultat.

6.3

possibles (plus

ou

moins

Nouvelle approche de la notion d'Algorithme

Nous avons vu qu'un algorithme est la description dans un langage universel des opérations nécessaires pour résoudre un problème. Il est possible d'aborder cette notion d'une autre manière en considérant qu'un algorithme du problème est une succession d'actions qui permet de faire passer l'environnement de l'état initial donné à l'état final désiré, succession telle que chaque action soit : - une primitive, - ou bien un algorithme déjà connu et décrit.

page n° 21

Programmation structurée

Formalisme de l’environnement d’un problème

7 NOTION D'OBJET. 7.1

Définition d'un objet

On appelle OBJET, les éléments constituant l'environnement d'un processeur. Ces objets contiennent les informations relatives au problème traité. Exemple : Le processeur "Menuisier" modifie le bois brut de son environnement en utilisant ses outils pour construire une table en bois.

7.2

Caractéristiques d'un objet.

Dans l'environnement d'un algorithme, lorsqu'on veut définir une action, il faut préciser quelle partie de l'environnement est traitée (observée et/ou modifiée) par l'action, ou encore sur quels objets va porter l'action. Exemple : Pour effectuer l'action "Clouer deux planches", le menuisier a besoin des objets PLANCHE - MARTEAU - POINTE. On constate donc la nécessité de citer la nature des objets que l'on veut manipuler et de ne pas les utiliser n'importe comment. Le fait que ces éléments aient des noms distincts permet de les distinguer sans ambiguïté.

Le NOM apparaît donc comme un attribut d'un objet permettant sa désignation. On parlera encore de CONTENANT.

Conseil :Le choix du nom est très important, il doit évoquer le plus clairement possible le rôle joué par l'objet afin d'assurer la lisibilité de l'algorithme. Ne pas se laisser tenter par la facilité qui consiste à choisir des identificateurs courts et vite écrits car leur valeur mnémotechnique est faible voire nulle. Chaque objet est destiné à une utilisation bien particulière et les utilisations ne sont pas interchangeables (on ne peut pas impunément planter un marteau avec une pointe). Pour marquer ces particularités nous dirons que les objets sont de TYPES différents. Exemple : Dans l'atelier de menuiserie, on pourra introduire les types : outils, visserie, enduit, peinture, vernis... page n° 22

Programmation structurée

Formalisme de l’environnement d’un problème

Le TYPE d'un objet détermine l'ensemble dans lequel l'objet prend ses valeurs. Modalité de déclaration : - Pour décrire des objets de même nature et admettant les mêmes opérateurs, il suffit d'avoir décrit le type une fois pour toutes et d'annoncer que tel ou tel objet est de tel ou tel type. Intérêt des types :

☞On dispose d'un moyen pour détecter un certain nombre d'erreurs sans exécuter le programme, simplement par l'examen des opérations effectuées sur les objets et en contrôlant qu'elles sont licites.

☞ On optimise la taille mémoire nécessaire ainsi que les processus de codage et de décodage des valeurs.

Ceci permet au programmeur de ne pas mélanger les torchons et les serviettes, de ne pas être tenté d'additionner le nom du bateau avec l'âge du capitaine.

Exemple : On pourrait définir le type PEINTURE par l'énoncé des états possibles suivants : (FRAICHE - SECHE - MOLLE - DURCIE).C'est l'ensemble des états qui constitue la définition du type. Un objet de TYPE PEINTURE pourrait prendre l'un des quatre états ci-dessus. Le type d'un objet est un attribut de cet objet invariable dans le temps. La VALEUR d'un objet indique son état à un moment bien déterminé et est variable dans le temps. EN RESUME : Pour caractériser parfaitement un objet, il est nécessaire de donner son NOM (ou contenant ou enveloppe). son TYPE qui traduit l'ensemble des valeurs qu'il peut prendre. sa VALEUR (ou contenu) qui caractérise l'objet à l'instant donné. son ADRESSE qui caractérise son emplacement en mémoire.

page n° 23

Programmation structurée

Formalisme de l’environnement d’un problème

8 NOTION DE CONSTANTE ET DE VARIABLE Rappel : tout algorithme se compose d'une suite d'actions à exécuter ( ces actions sont encore appelées instructions). Ces actions manipulent des objets qui peuvent être: − des objets dont la valeur est toujours la même : les CONSTANTES − des objets dont la valeur peut varier au cours de l'exécution de l'algorithme : les VARIABLES

8.1

Intérêt des constantes

En informatique il est commode de pouvoir donner un nom à certains objets, ils sont ainsi plus faciles à manipuler. C'est le cas, par exemple du nombre PI qui suivant la précision que l'on désire dans les calculs, doit être exprimé avec un nombre adéquat de chiffres après la virgule. Une autre raison de nommer certains objets à l'aide d'un identificateur, est d'expliquer plus clairement ce qu'ils expriment. Ainsi au lieu de noter 12 le nombre de mois dans une année, n’est il pas plus agréable de nommer ce nombre 12 par l'identificateur mois.Cette dénomination apporte plus de lisibilité dans l'algorithme où cette valeur est utilisée. Nous verrons également plus tard que le nommage de certains objets facilite grandement la modification que doivent subir les programmes lors de la maintenance des logiciels.

8.2

Intérêt des variables

L'intérêt d'une variable est de nommer un objet dont la valeur peut évoluer au cours de l'algorithme pour aboutir à un résultat final. Ainsi la variable apparaît comme une "boîte" ou "casserole" dont le contenu peut être modifié au cours du déroulement de l'algorithme. A tout moment, le contenu de cette boite, est appelé valeur de la variable. Il suffit de citer le nom de la variable pour accéder à la valeur qu'elle contient. Exemples :

Total imposable sur la feuille de solde. Cumul des achats du mois. page n° 24

Programmation structurée

Formalisme de l’environnement d’un problème

9 LES TYPES D'OBJET ET LEURS OPERATEURS ASSOCIES On peut considérer qu'il existe cinq types simples d'objets et deux que l'on peut qualifier de particulier. On peut ensuite, par combinaison, obtenir un nombre infini de types composés.

9.1

Le type entier.

Ce type correspond à l’ensemble mathématique des entiers relatifs Z. Les valeurs sont des nombres entiers en notation décimale avec ou sans signe ( une valeur sans signe est considérée comme positive). Exemples : +12 56 -24 Les opérations usuelles associées sont l'addition, la soustraction, la multiplication, la division, la mise à la puissance, la division entière et les comparaisons. On peut en outre utiliser certaines opérations particulières comme par exemple valeur absolue ABS(-12) = 12.

9.2

Le type réel. Ce type correspond à l’ensemble mathématique des réels R.

Les valeurs sont des nombres réels en notation anglo-saxonne pour la virgule ( le séparateur est le point). Exemples :

13.6

0.18

-956.345

Les opérations associées sont les mêmes que pour les nombres entiers.

9.3

Le type booléen. Les valeurs booléennes sont au nombre de deux : VRAI et FAUX.

Les opérateurs associés sont les opérateurs logiques NON, OU, ET ainsi que les opérateurs de comparaison: = (égal) , # ou < > (différent), < (inférieur), > (supérieur), < = (inférieur ou égal à ), >= ( supérieur ou égal à ).

page n° 25

Programmation structurée

9.4

Formalisme de l’environnement d’un problème

Le type caractère.

Les valeurs sont tous les caractères usuels lettres, chiffres et les caractères dits spéciaux : $, . %, §, @, #, * .... En notation, on entoure le caractère d'apostrophes. Exemples : 'A', '9', '#’ Les opérateurs associés sont les opérateurs de comparaison = (égal) et # (différent). Exemple : Le résultat de 'A' = '6' est FAUX.

9.5

Le type chaîne.

Les valeurs sont l'ensemble des combinaisons que l'on peut former à l'aide des caractères usuels ou spéciaux. Pour éviter de confondre une chaîne de caractères avec le nom d'une variable, on la représente toujours entre deux apostrophes. Comme avec les caractères, ces deux apostrophes délimitent le début et la fin de la chaîne et ne sont pas à considérer comme faisant partie de la chaîne. Exemples:

'Nom' , 'prénom'

Si la chaîne de caractères contient une apostrophe, celle-ci sera doublée. ' Il s''appelle Pierre'. Comme pour le type caractère, les opérateurs associés sont les opérateurs d'égalité et de comparaison.

9.6

Le type enregistrement.

Ces différents types d'objets peuvent être associés en les regroupant au sein d'un type particulier le type enregistrement. Ce type étant modulable à volonté il faudra le définir avec précision chaque fois que l'on voudra l'employer.

9.7

Le type pointeur. Cité pour mémoire.

page n° 26

Programmation structurée

Formalisme de l’environnement d’un problème

10 LES EXPRESSIONS ET LA PRIORITE DES OPERATEURS 10.1

Composition d'opérations élémentaires : Expressions

Une expression peut être définie comme une combinaison d'objets de base et d'opérateurs pris parmi ceux qui correspondent au type d'objet concerné. Exemple : Soient A, B, C, D de type ENTIER A + B * C / D est une expression Pour lever toute ambiguïté, à chaque opérateur est associé une priorité permettant de classer les opérateurs entre eux. Les règles suivantes représentent l'ordre des calculs − Une opération, est à évaluer en premier, si sa priorité est plus forte que celle des opérations adjacentes. − En cas d'égalité des priorités, l'évaluation a lieu de gauche à droite. − Le parenthèsage force l'ordre d'évaluation.

10.2

Tableau des opérateurs par ordre de priorité décroissante

OPERATEUR + - unaires

NOTATION + -

Type des opérandes Entier/Réel

Type du résultat Entier/Réel

Négation logique

NON

Booléen

Booléen

Entier/Réel

Entier/Réel

Entier/Réel Entier/Réel Entier Entier Entier/Réel Entier/Réel Entier/Réel Tout type Booléen

Entier/Réel Entier/Réel Entier Entier Entier/Réel Entier/Réel Booléen Booléen Booléen

Puissance Multiplication Division Division entière Reste Addition Soustraction Comparaison

* / DIV MOD + = , <> , < , <= , >, >=,

Et / OU logiques

ET , OU

Exemple :

Dans l'exemple précédent, le processeur calculera dans l'ordre : - B * C puis - (B * C) / D puis - A + (B * C) / D

POUR FACILITER LA LISIBILITE, IL NE FAUT PAS HESITER A METTRE DES PARENTHESES

page n° 27

Programmation structurée

Formalisme de l’environnement d’un problème

11 LES PRIMITIVES DE BASE EN ALGORITHMIQUE Nous avons vu que chaque variable est représentée dans l'algorithme par son Identificateur ( ou Nom). On peut faire évoluer la valeur d'une variable par l'instruction de lecture ou celle d'affectation.

11.1

Notion de lecture.

Il peut arriver qu'une valeur ne fasse pas partie de l'environnement d'un travail : pour pouvoir enregistrer cette valeur, il sera nécessaire de la faire entrer dans l'environnement. Cette entrée se fera par l'intermédiaire d'une instruction de lecture. L'instruction de lecture permet donc d'affecter à une variable une valeur saisie au clavier ou une valeur lue dans un fichier. On précise l'endroit où se fait la lecture. Syntaxe : Exemple :

LIRE (Fichier ; Nom)

Dans le cadre d'un calcul de moyenne

Lire(clavier ; note)

A) Appuyer sur la touche "C" B) Taper la première note Lire (clavier ; note) C) Appuyer sur "+" D) Taper la seconde note Lire (clavier ; note) E) Appuyer sur "/" F)Taper "2" G) Appuyer sur "=". Le résultat est affiché On peut factoriser l'instruction de lecture Syntaxe :

LIRE (Fichier ; Ident1, Ident2, … , IdentN)

Dans un exemple de dialogue Homme Machine (inter activité), l'instruction Lire provoque l'arrêt de la machine, l'utilisateur frappe alors au clavier une valeur qui sera affectée à la variable désignée par son Nom (ou Identificateur).

Les valeurs doivent alors être rentrées dans l'ordre de leur affectation et être du même type que chaque identificateur auquel elles correspondent.

Conventions : page n° 28

Programmation structurée

Formalisme de l’environnement d’un problème

On considérera que par défaut l'instruction lire se fait à partir du clavier. Il ne sera donc pas nécessaire dans ce cas le spécifier. Syntaxe :

LIRE (Nom)

On peut, dans ce cas également factoriser l'instruction de lecture. Syntaxe :

11.2

LIRE (Ident1, … , IdentN)

Notion d'affectation

Dans un environnement donné, pour attribuer à une variable une valeur qui provient de ce même environnement, nous conviendrons d'utiliser la notation suivante:

Ident ← Val _ Ident

est le nom ( ou identificateur) de la variable à laquelle le processeur

doit attribuer la valeur, _

←

_ Val

est le symbole qui caractérise l'affectation, est la valeur à affecter et peut être: − une constante, − le nom d'une autre variable qui contient la valeur, − une expression arithmétique décrivant un calcul à effectuer.

Il est important de bien noter que les deux entités qui, dans une affectation, apparaissent de part et d'autre du signe ← , doivent toujours être du même type ou de type compatible

page n° 29

Programmation structurée

Formalisme de l’environnement d’un problème

L'affectation de valeur à une variable peut-être effectuée autant de fois que l'on veut au cours du programme. La valeur de la variable sera alors modifiée à chaque affectation. Exemples : A)

Note1 ← 12

Note1 ← 13

L'action A affecte à la variable Note1 la valeur numérique 12, puis écrase cette valeur avec 13. B)

Prenom ← 'Pierre'

L'action B affecte à la variable Prenom la chaîne de caractères 'Pierre'. Il est donc indispensable que la variable Prenom soit du type chaîne. C)

Total ← Somme

L'action C représente une affectation dans laquelle la valeur à affecter est indiquée par une variable. Les deux variables Total et Somme doivent bien sûr être de même type. Exemple : les variables Total et Somme ont respectivement pour valeur 124 et 18 avant l'instruction d'affectation. Après exécution de l'opération d'affectation, elles auront toutes les deux la valeur 18.

En d'autres termes, seule la variable située à gauche du signe lors de l'exécution d'une instruction d'affectation.

D)

←

change de valeur

Somme ← Note1 + Note2

L'action D affecte à la variable Somme le résultat d'un calcul arithmétique. Les trois variables concernées doivent être du même type. L'action D s'exécute en deux temps : calcul de la valeur de l'expression Note1 + Note2 affectation de cette valeur à la variable Somme. L'expression est toujours évaluée avant d'être affectée. page n° 30

Programmation structurée

11.3

Formalisme de l’environnement d’un problème

Notion d'initialisation.

Lorsque l'on utilise une variable dans une expression ou une instruction, il est absurde d'effectuer un traitement sur cette variable si son contenu est inconnu. Il faut donc avant toute utilisation initialiser cette variable, c'est à dire lui donner une première valeur. Toute première affectation d'une variable s'appelle l'initialisation de la variable. Cette initialisation est d'autant plus importante qu'une variable qui n'a pas été initialisée contient une valeur aléatoire qui faussera tous les calculs que l'on pourrait effectuer sur cette variable avant son initialisation.

A retenir Après la déclaration d'une variable, l'état initial de sa valeur n'ayant pas été précisée, celle-ci est indéterminée.

11.4

Notion d'écriture.

A l'inverse de la lecture, il est également nécessaire de faire sortir une valeur de l'environnement pour communiquer une information vers l'extérieur. Cette communication se fait à l'aide de la primitive Ecrire. Syntaxe :

Ecrire (Fichier ; Val)

L'action permet de communiquer à l'extérieur la valeur de la variable Val en l'écrivant dans un fichier. Il faut insister sur le fait que cette action, qui transmet vers l'extérieur une copie de la valeur de Val, ne modifie aucunement la valeur de cette variable. On peut, dans ce cas également factoriser l'instruction d'écriture. Syntaxe :

ECRIRE (Fichier ; Ident1, Ident2, … , IdentN)

page n° 31

Programmation structurée

Formalisme de l’environnement d’un problème

Conventions : On considérera que l'instruction écrire se fait par défaut sur l'écran. Il ne sera donc pas nécessaire de le spécifier dans ce cas. Syntaxe :

ECRIRE (Variable)

On peut, dans ce cas également factoriser l'instruction de lecture Syntaxe :

ECRIRE (Ident1, … , IdentN)

On peut également utiliser un libellé en tant qu'argument d'une primitive d'écriture. La syntaxe sera alors :

ECRIRE ('bonjour')

On peut également utiliser une expression en tant qu'argument d'une primitive d'écriture. La syntaxe sera alors : ECRIRE ( A+B) En résumé L'action Lire (Val) affecte une nouvelle valeur à Val, l'action Ecrire (Val) ne modifie en rien la valeur de la variable.

11.5

Les Commentaires

Afin d'améliorer la lisibilité d'un algorithme, on peut utiliser des commentaires. Un commentaire est une suite de caractères quelconques encadrée par les symboles DCO et FCO. Exemple: DCO ceci est un commentaire FCO

page n° 32

Programmation structurée

STRUCTURE GENERALE D'UN ALGORITHME

Page n° 33

Programmation structurée

Structure générale d’un algorithme

12 DEFINITION D'UN ALGORITHME Rappel : Un algorithme est la description, dans un langage universel, des opérations nécessaires pour résoudre un problème.

Autre approche de la notion d'Algorithme Un algorithme du problème est une succession d'actions qui permet de faire passer l'environnement de l'état initial donné à l'état final désiré, succession telle que chaque action soit : - une primitive, - ou bien un algorithme déjà connu et décrit (encore appelé par abus de langage sous-programme).

En programmation structurée, on n'écrit que des sous-programmes. Le programme principal est en fait un sous-programme généralement sans paramètre.

13 STRUCTURE D’UN ALGORITHME Dans tout programme écrit en langage de description ou autrement dit dans tout algorithme, on distingue une première méthode d’écriture qui se compose de trois parties: - la partie déclaration , - la partie définition des arguments, - la partie instructions. Et une deuxième méthode qui elle ne se compose que de deux parties : - la partie déclaration , - la partie instructions ( identique dans les deux méthodes ).

page n° 34

Programmation structurée

13.1

Structure générale d’un algorithme

Déclaration des variables et des constantes méthode n°1 :

La partie déclaration rassemble la liste descriptive des constantes et des variables que le programmeur se définit pour écrire son algorithme. Ces objets sont donc déclarés UNE SEULE FOIS en début d'algorithme. Cette déclaration se fait sous la forme d'un tableau comportant pour les variables : - en colonne 1, le nom de la variable, - en colonne 2, le type de la variable, - en colonne 3, la signification de la variable.

VARIABLE

TYPE

SIGNIFICATION

Et pour les constantes : - en colonne 1, le nom de la constante, - en colonne 2, le type de la constante, - en colonne 3, la valeur de la constante, - en colonne 4, la signification de la constante.

CONSTANTE 13.2

TYPE

VALEUR

SIGNIFICATION

Déclaration des variables et des constantes méthode n°2 :

Après avoir écrit le nom de l’algoritme on écrira simplement sur la ligne suivante : VARIABLES Nom_de_la_variable : son_type Nom_de_la_variable : son_type Nom_de_la_variable : son_type ( l’écriture des variables se fait généralement en minuscule )

page n° 35

Programmation structurée

Structure générale d’un algorithme

CONSTANTES NOM_DE_LA_CONSTANTE = valeur NOM_DE_LA_CONSTANTE = valeur NOM_DE_LA_CONSTANTE = valeur ( l’écriture des constantes se fait généralement en majuscule )

13.3

Définition des paramètres méthode n°1 :

Les variables utilisées en paramètres d'un algorithme sont décrites sous la forme d'un tableau. On distingue les paramètres données, des paramètres résultats.

DONNEES : RESULTATS : ( SERA DETAILLE PLUS SOUS_PROGRAMME )

13.4

V1, V2 V3,V4

LONGUEMENT

DANS

LE

CHAPITRE

NOTION

DE

NOTION

DE

Définition des paramètres méthode n°2 :

La définition des paramètres s’écrit dans l’en-tête du sous-programme. ( SERA DETAILLE PLUS SOUS_PROGRAMME )

13.5 13.5.1

LONGUEMENT

DANS

LE

CHAPITRE

Le bloc instructions Présentation générale

Tout bloc d’instructions commence par le TYPE D'ALGORITHME (Fonction ou procédure) suivi du NOM de l'algorithme et (éventuellement) des paramètres entre parenthèses.

ALGORITHME

Nom_de_l'algorithme()

Le bloc d’instructions est délimité par le terme DEBUT avant la première instruction et le terme FIN après la dernière.

page n° 36

Programmation structurée

Structure générale d’un algorithme

14 EXERCICE RECAPITULATIF Exemple: Moyenne de deux notes. METHODE N°1 Déclaration des variables VARIABLE

TYPE

SIGNIFICATION

Note1

Entier

Première note à saisir

Note2

Entier

Deuxième note à saisir

Somme

Entier

Somme des notes

Moyenne

Réel

Moyenne des notes

Définition des paramètres DONNEES : RESULTATS :

Instructions ALGORITHME

MOYENNE ( )

DEBUT LIRE (Note1, Note2) Somme ← Note1 + Note2 Moyenne ← Somme / 2 ECRIRE (Moyenne) FIN

page n° 37

Programmation structurée

Structure générale d’un algorithme

METHODE N°2

ALGORITHME

MOYENNE ( )

VARIABLES note1 note2 somme moyenne

: : : :

entier entier entier réel

DEBUT LIRE (note1, note2) somme ← note1 + note2 moyenne ← somme / 2 ECRIRE (moyenne) FIN

page n° 38

Programmation structurée

L'ORDONNANCEMENT

Page n° 39

Programmation structurée

L’ordonnancement

15 RAPPEL DE LA METHODOLOGIE EMPLOYEE EN P.S. Pour résoudre un problème global, on aborde lors de l'analyse trois phases : L'étude des données à obtenir (réponse à la question QUOI), L'étude des données à utiliser (réponse à la question AVEC QUOI) L'étude du traitement à effectuer (réponse à la question COMMENT) Pour aborder chacune de ces différentes phases on utilise la méthode descendante, c'est-à-dire que l'on divise le problème global en actions élémentaires de complexité moindre. A leur tour, les actions élémentaires sont, si nécessaire, divisées jusqu'à ce qu'elles soient suffisamment simples pour être résolues sans difficulté. Ce découpage peut se représenter sous la forme d'un arbre. CF : chapitre : caractéristiques générales de la méthode de programmation structurée.

Jusqu'à présent nous nous sommes contentés de décrire une démarche permettant en théorie de résoudre un problème. Mais notre but est bien de faire effectuer le travail par un ordinateur. Or l'organe central de l'ordinateur (le processeur) travaille séquentiellement, c'està-dire en effectuant une opération après l'autre. Il faut donc lui préciser l'ordre dans lequel on veut qu'il effectue ces opérations : c'est l'objectif de l'ordonnancement.

16 LA THEORIE PAR L'EXEMPLE 16.1

Exposé du problème Nous voulons faire du café.

16.2

Etude de l'environnement de départ

Enoncé Précisons et délimitons le problème (c'est la formulation de l'énoncé):

Page n° 40

Programmation structurée

L’ordonnancement

La cafetière est prête à fonctionner (elle est branchée), seuls manquent l'eau, le café, et le filtre (ce sont les objets manipulés ou données du problème). Le café liquide est le résultat recherché.

Eau Café Filtre

CAFETIERE

Café liquide

EDO et EDU Ce schéma global reste vague, et donc trompeur : en effet si nous mettons de l'eau, du café, un filtre dans la cafetière dans n'importe quel ordre, nous avons peu de chance d'obtenir quelque chose de buvable.

Le coeur du problème apparaît mieux dans le schéma suivant :

Données

(Eau, Café, Filtre)

FAIRE DU CAFE

Résultat

(Café liquide)

L'étude des données ( ou résultat) à obtenir ainsi que celle des données à utiliser sont triviales et ne nécessitent aucune précision supplémentaire dès lors que l'énoncé du problème a été correctement exposé.

page n° 41

Programmation structurée

16.3

L’ordonnancement

Etude du traitement

Il nous faut maintenant étudier le traitement c'est-à-dire décomposer le problème FAIRE DU CAFE. Ce problème peut se décomposer en plusieurs sous-problèmes : - 1) Mettre le café dans le filtre. - 2) Appuyer sur le bouton de mise en route. - 3) Mettre l'eau dans la cafetière. - 4) Mettre un filtre. Dans un premier temps nous considérerons ces actions suffisamment simples pour être traitées sans décomposition supplémentaire. Nous avons donc déterminé les différentes actions nécessaires pour faire du café. On peut considérer que la décomposition est suffisante pour que l'on puisse effectuer chacune des actions sans difficulté. Jusqu'à présent on ne s'est pas soucié de l'ordre dans lequel vont s'effectuer les traitements. La méthode a été déroulée de manière statique. Il est néanmoins évident que ces différentes actions ne peuvent être effectuées dans un ordre quelconque. Il ne faut pas mettre la charrue avant les boeufs.

16.4

Nécessité et caractéristiques de l'ordonnancement

Ces actions doivent maintenant séquentiellement par l'ordinateur.

être

ordonnancées

pour

être

exécutées

Cet exemple étant tiré de la vie courante, il est bien évident que l'ordonnancement relève ici du simple bon sens et correspond à la chronologie des actions que vous devez vous même adopter (en tant que processeur manuel) lorsque vous voulez faire du café. - 1) Mettre l'eau dans la cafetière. - 2) Mettre un filtre. - 3) Mettre le café dans le filtre. - 4) Appuyer sur le bouton de mise en route.

page n° 42

Programmation structurée

L’ordonnancement

Il ne faut cependant pas perdre de vue que pour un ordinateur, rien ne relève de l'évidence et donc que tout doit lui être clairement défini.

Les actions seront exécutées une seule fois et séquentiellement c'est-à-dire les unes après les autres dans l'ordre normal de la lecture. Nous pouvons remarquer, qu'en toute logique, seules certaines actions peuvent être permutées sans introduire de changement dans le déroulement de la fabrication du café. - 1) Mettre l'eau dans la cafetière.

(permutation 1 et 2 possible)

- 2) Mettre un filtre. - 3) Mettre le café dans le filtre.

(permutation 2 et 3 peu logique)

- 4) Appuyer sur le bouton de mise en route.

page n° 43

Programmation structurée

L’ordonnancement

17 EN RESUME L'utilisation de la méthode permet de hiérarchiser le découpage de notre problème en éléments simples que nous savons traiter. Cependant cette hiérarchisation ne nous donne qu'une vue statique de note résolution. Cette vision n'est pas suffisante pour écrire correctement l'algorithme qui correspond à notre problème. Il est pour cela nécessaire d'ordonnancer nos éléments afin de définir l'ordre dans lequel ils devront être exécutés. Nous aboutissons ainsi à l'écriture d'une structure séquentielle.

Les caractéristiques d'une structure séquentielle sont les suivantes : - les actions sont traitées une à une, - chaque action n'est traitée qu'une fois, - les actions sont exécutées dans l'ordre d'arrivée (de lecture), - l'exécution de la dernière action est la fin de l'algorithme.

page n° 44

Programmation structurée

Application de la méthode aux alternatives et itérations

APPLICATION DE LA METHODE AUX ALTERNATIVES ET ITERATIONS

page n° 45

Programmation structurée

Application de la méthode aux alternatives et itérations

18 LES STRUCTURES FONDAMENTALES 18.1

Notion de programme propre

On appelle programme propre un traitement qui possède une seule entrée et une seule sortie. Avantage: si l'on doit apporter des modifications dans ce programme propre, il est beaucoup plus facile de déterminer l'impact de ces modifications . e

T1 s Les structures fondamentales utilisées pour écrire les algorithmes sont au nombre de 3.

18.2

Enchaînement des actions

On utilisera cette structure lorsqu'une action doit succéder à une autre e1

T1

T1, T2 : traitements ou algorithmes (programmes propres)

s1

Exemples: DEBUT

DCO traitement 1 FCO

e2

FIN

DCO fin du traitement 1 FCO

DEBUT

DCO traitement 2 FCO

FIN

DCO fin du traitement 2 FCO

T2 s2

Le résultat obtenu est aussi un programme propre

page n° 46

Programmation structurée

18.3

Application de la méthode aux alternatives et itérations

Structure alternative ou conditionnelle e

SI Condition ALORS T1 SINON T2 FINSI

condition

T1

T2 s

Condition désigne une expression booléenne dont la valeur est VRAI ou FAUX. T1 et T2 désignent une suite d'instructions (pouvant elles mêmes être des structures alternatives). La structure alternative est une structure parenthésée, chaque partie étant délimitée par les symboles SI, ALORS, SINON et FINSI. Le traitement T2 est facultatif. Exemple : ALGORITHME MAXIMUM_DE_DEUX_NOMBRES VAR A, B : ENTIER DCO les deux nombres à comparer FCO MAX : ENTIER DCO le plus grand FCO DEBUT ECRIRE('Entrez le premier nombre :') LIRE(A) ECRIRE('Entrez le deuxième nombre :') LIRE(B) SI A >= B ALORS MAX ← A SINON MAX ← B FINSI ECRIRE('le maximum de ', A,' et de ',B,' est : ',MAX) FIN On pourrait remplacer la conditionnelle de cet exemple par MAX ← B; SI A > B ALORS MAX ← A FINSI On remarque que cette alternative ne comporte pas de clause SINON.

page n° 47

Programmation structurée

18.4

Application de la méthode aux alternatives et itérations

Structure itérative

La notion d'itération est l'une des notions fondamentales de l'algorithmique. Elle est utilisée lorsque l'on doit exercer plusieurs fois le même traitement sur un même objet. Si le nombre de répétitions est grand, il serait fastidieux de réécrire n fois le même algorithme et même impossible si n était inconnu.

Lorsque la condition a pour valeur VRAI, on exécute le traitement T1 puis on revient tester la condition. Il est donc nécessaire que l'action T1 modifie la condition sinon l'itération ne s'arrêtera pas. Lorsque la condition a pour valeur FAUX, le traitement séquentiel continue. L'itération est terminée.

e VRAI condition FAUX T1 s

En pseudo-langage, on écrira la structure itérative de la façon suivante: TANT QUE Condition FAIRE T1 FIN FAIRE Il existe bien d'autres méthodes pour représenter une itération. Théorème : Tout programme propre peut être ramené à l'un de ces trois types de structures.

page n° 48

Programmation structurée

18.5

Application de la méthode aux alternatives et itérations

Exercices

La solution des exercices qui suivent se trouve en fin de ce chapitre. Ex1 : Marchand de vin Un marchand de vin expédie une quantité Q de bouteilles de prix unitaire P. Si le total de la commande HT est au moins égal à 500 F, le port est gratuit sinon il est facturé 10% de la commande HT avec un minimum de 10 F. Ecrire l'algorithme qui donne le détail et la somme à payer pour des valeurs entrées P et Q. La TVA (taux en cours) ne s'applique pas sur les frais de port.

Ex2 : Facture EDF On veut établir la facture d'un abonné EDF, connaissant le dernier et l'avant-dernier relevé du compteur. Les règles de tarification sont les suivantes: Consommation inférieure à 100 kwh : prix du kwh = 0.5 F Consommation comprise entre 100 kwh et 500 kwh : prix du kwh = 0.4 F Consommation supérieure à 500 kwh : prix du kwh = 0.35 F Coût de l'abonnement 250 F Ecrire l'algorithme qui donne la montant de la facture à acquitter toutes taxes comprises.

Ex3 : Jeu de l'oie. Un joueur est caractérisé par un nombre PLACE compris entre 0 et 66 qui situe sa position sur le jeu de l'oie. Donner l'algorithme permettant de déterminer la nouvelle place du joueur après un jet de 2 dés DE1 et DE2, sachant qu'il applique les règles suivantes: - il faut arriver juste à 66 sinon on recule d’autant de cases que l’on dépasse 66. - une oie toutes les 9 cases sauf au 63 double le déplacement (9, 18, 27, ...) - une tête de mort au 58 renvoie au départ (position 0).

page n° 49

Programmation structurée

Application de la méthode aux alternatives et itérations

19 LES STRUCTURES COMPLÉMENTAIRES 19.1

L'alternative généralisée e

Expression

T1

T2

T3

T4

s Suivant la valeur de l'expression, un des traitements T1, T2, T3 ou T4 est exécuté. Ce traitement pourrait être obtenu à l'aide de SI imbriqués. SI valeur = valeur1 ALORS T1 SINON SI valeur = valeur2 ALORS T2 SINON SI valeur = valeur3 ALORS T3 SINON SI valeur = valeur4 ALORS T4 FINSI FINSI FINSI FINSI Beaucoup de langages proposent en outre un traitement pour les autres cas.

page n° 50

Programmation structurée

Application de la méthode aux alternatives et itérations

En pseudo-langage, on écrira Au CAS expression = valeur1 : T1 valeur2 : DEBUT T21 T22 FIN valeur3 : T3 valeur4 : T4 AUTRE T_autre FIN CAS

19.2

La répétition e

On effectue le traitement T. Si la condition est FAUX, on recommence le traitement T. L'itération se terminera lorsque la condition (de sortie) sera VRAI.

T

condition FAUX s

Traduction de la répétition en pseudo-langage REPETER T JUSQU'A condition

page n° 51

VRAI

Programmation structurée

Application de la méthode aux alternatives et itérations

A l'aide des structures fondamentales, on aurait le schéma suivant: e

T VRAI

Bien noter que la condition de sortie n'est plus la même DEBUT T TANT QUE NON Condition FAIRE T FIN FAIRE FIN

non condition FAUX

T

s

Théorème : il faut toujours se ramener à une des structures (fondamentales ou complémentaires). Exercice : Traduire le schéma suivant : e

T1

VRAI condition FAUX

T2

page n° 52

Programmation structurée

Application de la méthode aux alternatives et itérations

20 EXERCICES ET CORRIGÉS DES EXERCICES Enoncé de l'exercice n°01 Un article est vendu 12,5 Frs l'unité si la quantité demandée est inférieure à 100. Il est vendu 40 % moins cher si la quantité demandée est supérieure ou égale à 100 unités. On souhaite écrire un programme qui affiche le prix unitaire à payer ainsi que le montant global de la facture en fonction d'une quantité achetée, saisie au clavier.

Ecriture de l'algorithme ALGORITHME

FACTURE

()

CONSTANTE PU = 12,5 VARIABLES qte : entier prix_ven : réel DEBUT ECRIRE ("Quantité achetée?") LIRE(qte) SI qte > = 100 ALORS prix_ven  PU * 0,6 SINON prix_ven  PU FINSI ECRIRE ("FACTURE") ECRIRE ("Quantité achetée", qte) ECRIRE ("Prix de vente unitaire", prix_ven) ECRIRE ("Total facture", prix_ven * qte) FIN On peut ici entrevoir l'utilité de la déclaration de constante. Si le prix unitaire varie, il n'est pas nécessaire de parcourir tout le programme pour changer la valeur 12,5 chaque fois qu'on l'a utilisée. Il suffit de la changer une fois et une seule dans le pavé de déclaration des constantes.

page n° 53

Programmation structurée

Application de la méthode aux alternatives et itérations

Cette façon de procéder est à la fois plus rapide et plus sûre : - plus rapide car on n'a qu'une seule donnée à changer, - plus sûre car on ne risque pas d'oublier une valeur. SIMPLIFICATION DE LA CONDITION On aurait pu affecter arbitrairement le prix unitaire de référence au prix de vente et changer ce prix uniquement si la quantité commandée était supérieure ou égale à 100. ALGORITHME FACTURE ( ) DEBUT prix_ven  PU ECRIRE ("Quantité achetée?") LIRE(qte) SI Qté > = 100 ALORS prix_ven  PU * 0,6 FINSI ECRIRE ("FACTURE") ECRIRE ("Quantité achetée", qte) ECRIRE ("Prix de vente unitaire", prix_ven) ECRIRE ("Total facture", prix_ven * qte) FIN Cette façon de faire nous fait découvrir une structure simplifiée de l'alternative SOIT SOIT . Elle peut se résumer sous la forme :

SI

condition ou booléen ALORS Instruction 1 Instruction 2

FINSI

page n° 54

Programmation structurée

Application de la méthode aux alternatives et itérations

Enoncé de l'exercice n°02 Ecrire un algorithme qui affiche en clair un mois à l'écran à partir de son numéro saisi au clavier. L’algorithme sera traité dans un premier temps, avec une structure ‘’SOIT SOIT’’, dans un deuxième temps avec une structure "AU CAS OU". Ecriture de l'algorithme Résolution en utilisant des alternatives "SOIT SOIT" imbriquées. ALGORITHME MOIS () VARIABLE num_mois : entier DEBUT ECRIRE ("Entrez le numéro du mois") LIRE(num_mois) SI num_mois = 1 ALORS ECRIRE("Janvier") SINON SI num_mois = 2 ALORS ECRIRE("Février") SINON SI num_mois =3 ALORS ECRIRE("Mars") SINON SI num_mois =4 ALORS ECRIRE("Avril") SINON .......................... .......................... FINSI FINSI FINSI FINSI FIN

page n° 55

Programmation structurée

Application de la méthode aux alternatives et itérations

Résolution en utilisant des alternatives ‘AU CAS’.

ALGORITHME

MOIS ( )

VARIABLE num_mois : entier DEBUT ECRIRE ("Entrez le numéro du mois") LIRE(num_mois) AU CAS

num_mois =

01: 02: 03: 04: 05: 06: 07: 08: 09: 10: 11: 12:

ECRIRE("Janvier") ECRIRE("Février") ECRIRE("Mars") ECRIRE("Avril") ECRIRE("Mai") ECRIRE("Juin") ECRIRE("Juillet") ECRIRE("Août") ECRIRE("Septembre") ECRIRE("Octobre") ECRIRE("Novembre") ECRIRE("Décembre")

AUTRE

ECRIRE("Saisie incorrecte")

FIN CAS FIN

page n° 56

Programmation structurée

Application de la méthode aux alternatives et itérations

Enoncé de l'exercice n° 3 Ecrire un algorithme qui permet l'affichage des 9 tables de multiplication, avec une ligne blanche entre chaque table.

Ecriture de l'algorithme ALGORITHME

TABLES_MULTI

()

VARIABLES i, j : entier DEBUT POUR i VARIANT DE 1 A 9 ( au pas de 1 ) FAIRE ECRIRE ("Table de multiplication par" , i) POUR j VARIANT DE 0 A 10 ( au pas de 1 ) FAIRE ECRIRE( i , "*" , j , "=", i*j) FINFAIRE SAUT DE LIGNE FINFAIRE FIN

page n° 57

Programmation structurée

Application de la méthode aux alternatives et itérations

Enoncé de l'exercice n° 4 Ecrire un algorithme qui lit un entier N strictement positif au clavier et qui, si N est pair, effectue la somme des N premiers entiers et l'affiche.

Ecriture de l'algorithme ALGORITHME

CALCUL

VARIABLES nbre , i , somme

( )

: entier

DEBUT somme  0 REPETER ECRIRE(‘Entrez un nombre entier strictement positif’) LIRE (nbre) JUSQU’A nbre > 0 Si nbre MOD 2 = 0 ALORS POUR i VARIANT DE nbre A 1 ( au pas de –1 ) FAIRE somme  somme + I FINFAIRE ECRIRE (‘La somme des N premiers entiers est ‘, somme) SINON ECRIRE (‘Le nombre : ‘, nbre, ‘ n’est pas pair’) FINSI FIN

EXERCICE ‘Marchand de vin’ page n° 58

Programmation structurée

ALGORITHME

Application de la méthode aux alternatives et itérations

VIN

( )

CONSTANTES TAUX PORT_NUL PORT_MINI TVA

= = = =

VARIABLES q p , port , p_ht

: entier : réel

0.1 500 10 1,196

DEBUT dco Initialisation du port à zéro fco port  0 dco Saisie de la quantité de bouteilles et du prix unitaire fco ECRIRE ("Quantité de bouteilles expédiées?") LIRE(q) ECRIRE ("Prix unitaire des bouteilles expédiées?") LIRE(p) dco Calcul du montant hors taxe de la commande et du port fco p_ht  p * q SI p_ht < PORT_NUL ALORS port  p_ht * TAUX SI port < PORT_MINI ALORS port  PORT_MINI FINSI FINSI dco Affichage du résultat fco ECRIRE ("TOTAL de la COMMANDE hors taxe : ", P_ht) ECRIRE ("Montant du port", port) ECRIRE ("Somme à payer", P_ht * TVA + FIN

page n° 59

port)

Programmation structurée

Application de la méthode aux alternatives et itérations

EXERCICE ‘Facture E. D. F ALGORITHME

FACTURE_EDF

CONSTANTES BORN1 BORN2 TAR_1 TAR_2 TAR_3 LOC TVA

= = = = = = =

( )

100 500 0.5 0.4 0.35 250 1,196

VARIABLES Rel_M_1 , Rel_M , Conso: entier Prix_HT : réel DEBUT REPETER ECRIRE ("Entrez la consommation de l'avant dernier mois") LIRE(Rel_M_1) ECRIRE ("Entrez la consommation du dernier mois") LIRE(Rel_M) JUSQU'A Conso SI

Rel_M > Rel_M_1

 Rel_M - Rel_M _1 Conso < BORN1 ALORS Prix_HT  ( ( Conso * TAR_1 ) + LOC ) SINON SI Conso < BORN2 ALORS Prix_HT  ( ( BORN1 * TAR_ 1) + ( Conso – BORN1 ) * TAR_2 ) + LOC ) SINON Prix_HT  ( ( BORN1 * TAR_1 ) + ( BORN2 * TAR_2 ) + ((Conso – BORN2 ) * TAR_3) + LOC ) FINSI

FINSI ECRIRE ( "Le montant HT s'élève à : ", ECRIRE ( "Le montant TTC s'élève à : ", FIN

page n° 60

Prix_HT ) Prix_HT * TVA ) )

Programmation structurée

Application de la méthode aux alternatives et itérations

EXERCICE ‘Jeu de l'oie’ ALGORITHME JEU_OIE () VARIABLES Place , Nbre_coup , Score : entier DEBUT dco Initialisation des variables fco Place  0 Score  0 Nbre_coup  0 dco Boucle principale jusqu’à la place gagnante fco REPETER dco Boucle pour la vérification de la valeur des deux dés comprise entre 2 et 12 fco REPETER dco Saisie des deux valeurs et vérification fco ECRIRE (‘Donnez votre score (total des deux dés)’) LIRE(Score) SI

(Score > 12) OU (Score ALORS ECRIRE (‘Un score entre 2 et 12’) FINSI JUSQU'A

(Score < 13)

ET

<

2)

(Score > 1)

dco Addition du score et du nombre de coups fco Place  Place + Score Nbre_coup  Nbre_coup + 1 dco Recherche si le place est modulo 9, et si oui autre calcul fco TANT QUE ( Place MOD 9 FAIRE Place  Place + Score FINFAIRE

= 0)

page n° 61

ET (Place

<

63)

Programmation structurée

Application de la méthode aux alternatives et itérations

Dco. Vérification si la place est supérieure à 66, et si oui calcul de la nouvelle place fco SI Place > 66 ALORS Place  132 - Place FINSI dco Vérification si la place est égale à 58, et si oui retourner à la case départ fco SI Place = 58 ALORS Place  0 FINSI ECRIRE (‘Vous êtes à la case numéro’, JUSQU'A

Place

=

Place)

66

ECRIRE (‘Vous avez gagné la partie en ‘ , Nbre_coup , ‘coups’) FIN

page n° 62

Programmation structurée

Notion de sous-programmes

NOTION DE SOUS-PROGRAMME

Page n° 63

Programmation structurée

Notion de sous-programmes

21 LE SOUS-PROGRAMME 21.1

Rappel de la définition d’un programme

Un programme est une suite ordonnée d'instructions établie en vue d'un traitement par un ordinateur. Lorsque des séquences d'instructions se répètent plusieurs fois dans des programmes, il est intéressant de ne les écrire qu'une seule fois et de mettre au point des méthodes permettant de les utiliser à volonté.

C'est le but des sous-programmes. 21.2

Définition d’un sous-programme

Un sous-programme est donc un groupe de séquences d'instructions, isolé ou individualisé, utilisable à une ou plusieurs reprises au sein d'un même programme ou dans des programmes différents. Un sous-programme est déterminé par : - un NOM d'appel, - des paramètres.

21.3 21.3.1

Les paramètres Définition d'un paramètre

Un paramètre est une variable dont l'adresse ou la valeur est transmise à un sousprogramme lors de son appel ( on parle aussi d'argument). 1 ) Seuls les paramètres d'entrée (données) et de sortie (résultats) sont nécessaires. 2) Un paramètre peut être une variable simple ou une structure. 3) A l'intérieur d'un sous-programme peuvent être créées des variables intermédiaires qui ne sont connues que par le sous-programme (elles ne sont pas passées en paramètres).

Page n° 64

Programmation structurée

21.4

Application de la méthode aux alternatives et itérations

Utilité des paramètres à travers un exemple:

Exemple : Le calcul de l'imposition Dans le cadre des attributions de prestations particulières il est nécessaire de connaître le montant de l'imposition de l'intéressé. On peut donc envisager la création d'un sous-programme qui calcule ce montant pour n'importe quel individu. Ce sous-programme a besoin de connaître le montant des revenus ainsi que le nombre de parts pour effectuer son calcul. Il fournira en retour le montant de l'imposition. Exemple d'appel de sous-programme dans le cadre de l'étude d'un financement d'une acquisition particulière. Programme principal appelant trois sous-programmes.

21.5

Schéma de synthèse

PROGRAMME PRINCIPAL ( ) S-PROG impots (mtimposable,nbre) DEBUT Saisie Rens Appel impots (revenu,part )

DEBUT FIN S-PROG credits ( ) DEBUT

Appel credits ( ) FIN S-PROG financement ( ) Appel financement ( )

DEBUT FIN

FIN

page n° 65

Programmation structurée

Fonctions et procédures

FONCTIONS ET PROCEDURES

Page n° 66

Programmation structurée

Fonctions et procédures

22 NOTION DE PARAMETRE. 22.1

Ecriture d'un algorithme paramétrique.

Nous avons vu qu'un algorithme est constitué par une séquence d'actions, les unes étant des actions élémentaires ou primitives, les autres étant des actions composées, c'est à dire des algorithmes déjà connus. Pour pouvoir utiliser ces algorithmes dans des environnements différents, nous allons devoir placer des variables en paramètres. Considérons le problème suivant : Un article est vendu 12,5 Frs l'unité, si la quantité demandée est inférieure à 100. Il est vendu 40 % moins cher si la quantité demandée est supérieure à 100 unités. On souhaite écrire un programme qui calcule le montant global de la facture en fonction de la quantité achetée, saisie au clavier.

Ecriture de l'algorithme. ALGORITHME FACTURE CONSTANTE PU = 12,5

()

VARIABLES qte : entier prix_ven , total_fac : réel DEBUT ECRIRE ("Quantité achetée?") LIRE(qte) SI qte ###= 100 ALORS prix_ven ### PU * 0,6 SINON prix_ven ### PU FINSI total_fac ### prix_ven * qte FIN Page n° 67

Programmation structurée

Fonctions et procédures

Supposons que, dans le cadre de résolution de problèmes plus importants plusieurs personnes aient besoin de faire appel à ce calcul de prix. Pour simplifier ces opérations et afin de ne pas avoir dans chacun des programmes à réécrire l'algorithme, nous allons paramètrer l'algorithme afin de lui permettre de travailler directement sur les variables utilisées par les différents utilisateurs. Pour ce faire, nous allons modifier l'algorithme de la manière suivante : PROCEDURE

FACTURE

(qte : entier, @total_fac : entier)

CONSTANTE PU = 12,5 VARIABLES prix_ven : réel DEBUT SI qte ###= 100 ALORS prix_ven ### PU * 0,6 SINON prix_ven ### PU FINSI total_fac ### prix_ven * qte FIN

page n° 68

Programmation structurée

22.2

Fonctions et procédures

Intérêt des paramètres.

L'intérêt d'utiliser des paramètres, est que l'algorithme se comporte maintenant comme une primitive. Il est ainsi capable de s'exécuter en faisant jouer à d'autres variables les rôles de qte et total_fac. Il va pouvoir ainsi être utilisé sans modification dans des environnements différents.

22.3

Paramètres formels et paramètres effectifs.

Un appel d'algorithme consiste à écrire le nom de l'algorithme, suivi s'il y a lieu d'une liste de paramètres.

Un paramètre formel est une variable choisie comme paramètre à la définition d'un algorithme (il est là pour 'la forme', pour définir l'emplacement).

Un paramètre effectif est une variable utilisée dans un appel à la place d'un paramètre formel.

Lors de l'appel les paramètres effectifs sont : − de même type que les paramètres formels, − de même nombre que les paramètres formels, − dans le même ordre de déclaration que les paramètres formels.

A l'exécution d'un appel, la correspondance entre un paramètre formel et un paramètre effectif est définie par leur position dans la liste. Le premier paramètre effectif correspond au premier paramètre formel, le deuxième paramètre effectif correspond au deuxième paramètre formel, et ainsi de suite. La notion de paramètres formels et de paramètres effectifs est identique à celle que l'on rencontre en mathématiques dans la notion de fonction. Ainsi si l'on définit f(x,y) = xy, on peut construire une procédure calcul(x,y,z) dont l'unique instruction sera z ### x * y. Les paramètres formels sont x, y et z.. page n° 69

Programmation structurée

Fonctions et procédures

Si l'on veut calculer la valeur de cette fonction au point particulier (2,3) et affecter le résultat obtenu à la variable U, on appelle : Calcul(2,3,U) 2, 3 et U sont les paramètres effectifs de l'appel. Le résultat de cet appel affecte à U la valeur 6.

Ainsi, on distingue deux catégories de paramètres :

22.4

−

Les paramètres-données

−

Les paramètres-résultats

Les paramètres données

Le paramètre d'un module est un paramètre-donnée lorsque sa valeur initiale est utilisée par le module et reste inchangée après l'exécution de ce dernier.

22.5

Les paramètres résultats

Le paramètre-résultat (ou donnée-résultat) est un paramètre dont la valeur peut être remplacée en fin d'exécution par une valeur différente de la valeur initiale.

Dans l'exemple de la procédure calcul(x,y,z). − x et y sont des paramètres-données − z un paramètre-résultat

22.6

Passage par valeur, passage par adresse.

22.6.1.1

Passage par valeur Lecture seulement (paramètres-données) : Passage par valeur Le module agit sur la copie locale, mais pas sur l'original.

page n° 70

Programmation structurée

Fonctions et procédures

Dans un passage par valeur, c'est la valeur du paramètre et non son nom qui est transmis au sous-programme.

22.6.2

Passage par adresse ( @ )

Lecture/écriture (paramètres-résultats) : Passage par Adresse ou par Variable ou par Référence.

Dans ce cas, le module connaît l'adresse en mémoire du paramètre effectif, et travaille directement à cette adresse sur l'original.

page n° 71

Programmation structurée

Fonctions et procédures

EXEMPLE: Soit une procédure qui effectue la somme de deux nombres passés en paramètre et qui restitue le résultat dans un troisième paramètre.

PROCEDURE SOMME DEBUT Z ### X+ Y FIN

( X,Y : entier, @Z : entier) @Z ( représente l’adresse de Z )

APPEL DU SOUS-PROGRAMME AU SEIN D'UN AUTRE PROGRAMME: a ### 2 b ### 3 SOMME(a,b,c) A l'appel du sous-programme il y a substitution entre les paramètres formels et les paramètres effectifs. Le passage des paramètres se fait par valeur ou par adresse en fonction de ce qui a été décidé dans la déclaration des paramètres de l'algorithme appelé.

Passage par valeur (copie de la valeur)

a

E01

2

b

E02

3

c

E03

Programme appelant

E04 E05 Passage par adresse E06 (copie de l’adresse) E07

Redirection du résultat

x

E08

2

y

E10

3

z

E11

E03

E12

page n° 72

Programme appelé

Programmation structurée

22.7

Fonctions et procédures

Variables globales et variables locales

Les variables globales, déclarées dans la partie Déclaration de l'algorithme principal, sont accessibles depuis n'importe quel point du programme, aussi bien du sous-programme que du programme principal. Les variables locales, déclarées dans les parties Déclaration des différents sous-programmes, ne sont accessibles que par celles-ci, c'est à dire qu'elles ne peuvent être utilisées que dans les instructions du sous-programme où elles sont déclarées.

23 NOTION DE FONCTION ET DE PROCEDURE. 23.1

Intérêts

Ces deux nouveaux modules, très importants, permettent au programmeur de traiter un problème sans s'embarrasser, dans un premier temps, du règlement dans le détail des sous-problèmes le composant. L'utilisation des fonctions et procédures offre un autre intérêt évident dans la résolution d'un problème où l'on est amené à résoudre plusieurs fois le même sousproblème. On utilise alors un algorithme de ce type pour éviter d'écrire plusieurs fois la même suite d'instructions. Il faut ajouter enfin la plus grande facilité de mise au point et de maintenance des programmes, voire la possibilité de faire écrire par plusieurs personnes les différentes parties d'un algorithme.

23.2

Caractéristiques

Une fonction ou une procédure est un bloc d'instructions, nommé et paramétré que l'on déclare afin de pouvoir ensuite l'appeler par son nom en affectant des valeurs aux paramètres. Le résultat d'une fonction ou d'une procédure est évalué à chaque appel.

page n° 73

Programmation structurée

23.3

Fonctions et procédures

Différences entre fonction et procédure

La procédure retourne le(s) résultat(s) par l'intermédiaire du (des) paramètre(s) ‘résultat’. Dans le cas de la fonction le résultat est désigné par le nom même de la fonction ou par le mot réservé resultat.

23.3.1

Les particularités des fonctions Elles sont assez proches de la notion mathématique correspondante.

Une fonction possède des arguments qui correspondent aux informations qui lui sont transmises afin qu'elle fournisse un résultat principal (unique et simple). Ce résultat est désigné par le nom même de la fonction ou par le mot réservé resultat. L'appel d'une fonction peut avoir lieu au sein d'une expression.

23.3.2

Les particularités des procédures

Elles peuvent, posséder des paramètres mais ce n'est pas obligatoire. Elles n'ont pas de valeurs propres. Lorsqu'elles sont destinées à restituer des résultats elles le font par l'intermédiaire de paramètres résultats. L'appel d'une procédure ne peut avoir lieu au sein d'une expression.

23.4

Parallèle entre procédure et fonction

Toute procédure qui ne comporte qu'un paramètre résultat peut être remplacée par une fonction.

23.5

les prédicats

Les prédicats sont des fonctions particulières ne délivrant qu'un résultat principal booléen (VRAI ou FAUX).

page n° 74

Programmation structurée

23.6

Fonctions et procédures

EXERCICE N° 5

Enoncé de l’exercice n° 5 Ecrire un programme qui permette, après avoir saisi 3 entiers, de les afficher dans l'ordre croissant. Ecrire une fonction MAX qui permette de retourner le plus grand de deux entiers passés en paramètres. Ecrire une fonction MIN qui permette de retourner le plus petit de deux entiers passés en paramètres. Ecrire une fonction GRAND qui permette de retourner le plus grand de trois entiers passés en paramètres, en utilisant la fonction MAX. Ecrire une fonction PETIT qui permette de retourner le plus petit de trois entiers passés en paramètres, en utilisant la fonction MIN. Ecrire une fonction MOYEN qui permette de retourner l'élément du milieu entre trois entiers passés en paramètres, en utilisant les fonctions précédemment étudiées.

page n° 75

Programmation structurée

Fonctions et procédures

Ecriture de l'algorithme Instructions Algorithme Principal FONCTION MAX (a,b : entier) Resultat : entier DEBUT SI a > b ALORS Resultat SINON Resultat FINSI FIN

← a ←b

FONCTION MIN (a,b : entier) Resultat : entier DEBUT SI a < b ALORS resultat ← a SINON Resultat ← b FINSI FIN

page n° 76

Programmation structurée

Fonctions et procédures

FONCTION GRAND (a,b,c : entier) Resultat : entier DEBUT Resultat FIN

← MAX(a,MAX(b,c))

FONCTION PETIT (a,b,c : entier) Resultat : entier DEBUT Resultat ← MIN(a,MIN(b,c)) FIN FONCTION MOYEN (a,b,c : entier) Resultat : entier DEBUT Resultat ← PETIT(MAX(a,b),MAX(b,c),MAX(a,c)) DCOc'est aussi: GRAND(MIN(a,b),MIN(b,c),MIN(a,c))FCO FIN PROCEDURE TRI ( ) VARIABLES x, y, z : entier DEBUT ECRIRE("Entrez trois entiers:") LIRE(x,y,z) ECRIRE("Les voici en ordre croissant:",PETIT(x,y,z), MOYEN(x,y,z),GRAND(x,y,z)) FIN DEBUT DCO FIN

UTILISATION DE LA PROCEDURE TRI

page n° 77

FCO

Programmation structurée

LES STRUCTURES DE DONNEES STATIQUES

Page n° 78

Programmation structurée

Les structures de données statiques

24 LES TABLEAUX 24.1

Intérêt des tableaux

Lorsqu'on regroupe des objets, il est fréquemment utile de pouvoir faire un accès direct à un objet particulier du groupe, sans avoir à considérer séquentiellement tous ceux qui le précédent dans le groupe. La notion de table et ses réalisations sous forme de tableau et de fichier à accès direct répondent à ces besoins.

24.2

Caractéristiques

24.2.1

Définition d'un tableau

Un tableau est une collection finie et ordonnée d'éléments de même nature, accessibles directement, en utilisant un ou plusieurs indices. Définition formelle Un tableau est un ensemble d'informations, tel qu'à chaque information soit associé un nom et un seul (clé ou indicatif).

24.2.2 24.2.2.1

Les différents types de tableaux Unidimensionnel : Le vecteur

Déclaration 1

2

3

4

5

6

7

8

8

13

6

14

29

17

3

9

9

10

La déclaration du vecteur se fait dans la section des variables. Exemple : algorithme Le_Vecteur VARIABLES Mon_Vecteur : tableau de 1 à 10 de entier tableau 1 à 10 entier

représente le type de la variable Mon_Vecteur. représente la taille du vecteur. représente le type des données stockées dans le vecteur.

Voici un autre exemple de déclaration d’un vecteur, dans lequel un type a été défini préalablement. page n° 79

Programmation structurée

Les structures de données statiques

algorithme Le_Vecteur TYPE Ttablo = tableau de 1 à 10 de entier VARIABLES Mon_Vecteur : Ttablo

24.2.2.2

Bidimensionnel : Les matrices d'ordre deux Exemples de matrices à deux dimensions particulières: Matrice carrée

Matrice dont le nombre de lignes est égal au nombre de colonnes. Matrice diagonale Les éléments de la matrice se trouvent uniquement sur la diagonale.

1 1 2 3 4

2

3

4

X X X X

Matrice triangulaire Les éléments de cette matrice sont placés de façon triangulaire.

1 2 3 4

1

2

3

4

A B D G

C E H

F I

J

Matrice partiellement remplie ou éparse Matrice qui contient plusieurs éléments nuls répartis un peu partout dans la matrice. Il n'existe pas de définition précise pour identifier une matrice éparse, nous le reconnaissons de façon intuitive. page n° 80

Programmation structurée

24.2.2.3

Les structures de données statiques

Multidimensionnel

Les matrices à plus de deux dimensions sont généralement regroupées sous le terme de matrices multidimensionnelles.

24.2.3

Les notions d'indice et de rang

Les tableaux sont des structures à accès direct, c'est-à-dire que nous pouvons accéder directement à l'information en utilisant des indices. Les données individuelles sont donc repérées par un sélecteur que l'on nomme indice du tableau Le rang d’un tableau est le nombre de dimensions de ce tableau

24.2.4

Accés aux éléments du tableau

Contrairement aux fichiers séquentiels, il n'existe qu'une primitive d'accès aux éléments d'un vecteur : l'opération d'indiçage. Soit T un vecteur, et [1, N] l'intervalle d'entiers repérant les éléments du vecteur. On accède à l’Ième élément de T par l'opération d'indiçage que l'on note T[I]. Si I n'appartient pas à [1, N], le résultat est indéterminé . Dans le cadre des matrices à deux dimensions, on accède à un élément par l'opération d'indiçage que l'on note T[L,C] ou L représente le numéro de ligne et C celui de colonne. ATTENTION LE FAIT QUE LES INDICES SOIENT ENTRE CROCHETS NE VEUT ABSOLUMENT PAS DIRE QU'ILS SONT FACULTATIFS.

page n° 81

Programmation structurée

24.3

Les structures de données statiques

Opérations sur les tableaux

24.3.1 24.3.1.1

Etude du tableau unidimensionnel : le vecteur La création et le chargement A un indice du vecteur correspond une valeur bien précise, alors le contenu nous donne

l’indice. Exemple : variable tableau_mois : tableau 1 à 12 de chaînes de caractères Dans l’hypothèse où ce vecteur a été renseigné avec les clairs des douze mois de l’année, à l’indice 1 correspond la valeur ‘janvier’, à l’indice 2 correspond la valeur ‘février’ etc. . A un indice du vecteur correspond une valeur quelconque, alors à l’indice 1 correspond la 1 valeur, à l’indice 2 la 2ème.valeur. ère

24.3.1.2

La recherche

Il existe plusieurs méthodes de recherche. Pour déterminer la meilleure méthode, il faut considérer la taille du vecteur, son utilisation et son contenu.

Recherche séquentielle Les éléments sont dans un vecteur et l'ordre n'a pas d'importance. Lors de la recherche, on compare l'élément recherché avec tous ceux du vecteur en commençant par l'indice 1. Exemple : 1

2

3

8

13 6

4

5

6

7

8

14 29 17 3

9

Si on cherche 14 - on le compare avec V[1] avec V[2] avec V[3] avec V[4]

→ → → →

9

10

8 13 6 14 trouvé

Si des éléments sont recherchés plus souvent, il est bon de les placer en tête du vecteur et d'avoir un vecteur ordonné selon la fréquence d'utilisation décroissante ; ceci réduit le temps de recherche. Si le vecteur est trié de façon ascendante, on arrête la recherche dès que l'on trouve une valeur supérieure à celle recherchée (et bien sûr inférieure si le tri est descendant).

Recherche binaire page n° 82

Programmation structurée

Les structures de données statiques

Les éléments du vecteur doivent être classés par ordre croissant ou décroissant. Le principe consiste à diviser en deux l'étendue de la recherche et de comparer l'élément recherché avec l'élément milieu. Si ce dernier est plus grand que l'élément recherché, nous continuons la recherche dans la moitié inférieure du vecteur. Par contre, s'il est plus petit, nous travaillerons avec la moitié supérieure. Exemple : 1

2

3

4

5

6

7

8

8

12 19 24 29 33 38 42

9

10

Comparaison entre la recherche séquentielle et la recherche binaire En principe, la recherche binaire ou (dichotomique) est plus efficace que la recherche séquentielle mais il est important de noter que : a°) Les éléments du vecteur doivent être triés pour faire une recherche binaire. b°) Pour un N petit, la recherche séquentielle peut être plus rapide.

24.3.1.3

L'ajout ou l'insertion Si aucune position n'est libre dans le vecteur alors l'insertion est impossible.

Insérer à la fin du vecteur Nous gardons en mémoire l'indice du dernier élément et nous ajoutons après le dernier élément.

page n° 83

Programmation structurée

Les structures de données statiques

Insérer à l'intérieur du vecteur a) Si la position est libre, ajouter à cette position. b) Si la position n’est pas libre : Il s’agit d’insérer le nouvel élément après le Ke élément. Pour N positions occupées dans un vecteur trié ou non, il faut : − Trouver le Ke élément. − Faire de la place c'est à dire transférer l’élément N dans l’élément N+1, l’élément N-1 dans l’élément N, l’élément N-2 dans l’élément N-1, etc.. − Insérer l'élément à K+1. Si le vecteur est trié, on peut ajouter l'élément à la fin du vecteur et le trier à nouveau (Habituellement plus long).

24.3.1.4

La suppression et le tassement Pour supprimer un élément dans un tableau, il est possible de : − remplacer l’élément à supprimer par un élément dont la valeur sera nulle, les autres éléments ne subissant aucun changement. − remplacer l’élément à supprimer par l’élément qui le suit et faire subir un déplacement d’une position à tous les éléments qui suivent (tassement), remplacer le dernier élément déplacé par un élément de valeur nulle. Exemple : Soit le vecteur suivant : 1

2

3

4

5

6

7

A

B

C

D

E

F

G

Si on enlève le 4e élément soit D, on doit transférer le 5e élément dans le 4e , le 6e dans le 5e et le 7e dans le 6e. La dernière position du tableau prendra la valeur ‘ ‘ (espace). 1

2

3

4

5

6

A

B

C

E

F

G

Le vecteur résultant contiendra 6 éléments.

page n° 84

7

Programmation structurée

24.3.1.5

Les structures de données statiques

La copie

La copie d'un vecteur sur un autre ne présente aucune difficulté dès lors que les dimensions sont compatibles.

24.3.1.6

Le tri

Plusieurs méthodes de tri sont envisageables. La méthode dite du TRI A BULLES est présentée dans l’exemple ci-après.

page n° 85

Programmation structurée

Les structures de données statiques

DCO procédure de tri d’un tableau contenant IMAX entiers. les entiers sont triés en ordre croissant FCO Constante IMAX = 10 TYPE Ttab = tableau de 1 à IMAX de entier PROCEDURE trier_tableau

(@ tab :Ttab)

DCO variables locales à la procédure

FCO

VARIABLES borne , i permut tampon

: : :

entier booléen entier

DEBUT DCO initialisation des variables FCO borne  IMAX -1 permut  VRAI DCO Boucle pour sortir en cours de traitement FCO TANT QUE Permut FAIRE permut  FAUX DCO Boucle pour les bulles FCO POUR i variant de 1 à borne FAIRE DCO Permutation des postes du tableau FCO si tab[i] > tab[i+1] ALORS tampon  tab[i] tab[i]  tab[i+1] tab[i+1]  tampon permut  VRAI fin si FIN FAIRE borne  borne – 1 FIN FAIRE FIN

page n° 86

Programmation structurée

Les structures de données statiques

25 LES ENREGISTREMENTS Un enregistrement est une structure constituée d'un nombre fixe de composants appelés champs. Les champs peuvent être de différents types et chaque champ comporte un identificateur de champ permettant de le sélectionner. Exemple: TYPE T_ABONNE = ENREGISTREMENT NOM : CHAINE PRENOM : CHAINE AGE : ENTIER SALAIRE : REEL FIN Une variable du type T_ABONNE sera déclarée et utilisée de la façon suivante : VARIABLE ABONNE1

: T_ABONNE

Dans le programme utilisant cette variable, ABONNE1.NOM identifie le champ NOM de l'enregistrement ABONNE1 de type T_ABONNE. Les opérations permises sur le type chaîne seront possibles sur ABONNE1.NOM (lecture, écriture, affectation, comparaison, etc...).

page n° 87

Programmation structurée

Les structures de données statiques

26 EXERCICES Enoncé de l’ exercice n° 6 Copie d'un vecteur dans un autre vecteur.

Ecriture de l'algorithme Instructions Algorithme Principal CONSTANTE IMAX = 100 TYPE Ttab = tableau de 1 à IMAX de entier PROCEDURE COPIE (Vect1 : Ttab, @ Vect2 : Ttab) VARIABLES i : entier DEBUT

i ←1 TANT QUE i < = IMAX FAIRE Vect2[ i ] ← Vect1[ i ] i ←i + 1

le traitement ci-contre peut être écrit également ainsi : DEBUT Pour i variant de 1 à IMAX FAIRE Vect2[i] ← Vect1[i] FINFAIRE FIN

FINFAIRE FIN DEBUT DCO UTILISATION DE LA PROCEDURE COPIE FIN

page n° 88

FCO

Programmation structurée

Les structures de données statiques

Enoncé de l’exercice n° 7 Saisie de IMAX valeurs entières dans un vecteur.

Ecriture de l'algorithme Instructions Algorithme Principal CONSTANTE IMAX = 25 TYPE Ttab = tableau de 1 à IMAX de entier PROCEDURE SAISIE(@ vect : Ttab) VARIABLES i : entier DEBUT ECRIRE(Ecran,"Entrez", IMAX , " valeurs entières: ") i ←1 TANT QUE i < = IMAX FAIRE LIRE(Clavier,vect[ i ] ) i ← i+1 FINFAIRE FIN DEBUT DCO UTILISATION DE LA PROCEDURE SAISIE FIN

page n° 89

FCO

Programmation structurée

Les structures de données statiques

Enoncé de l’exercice n° 8 Affichage de IMAX valeurs entières stockées dans un vecteur.

Ecriture de l'algorithme Instructions Algorithme Principal CONSTANTE IMAX = 25 TYPE Ttab = tableau de 1 à IMAX de entier PROCEDURE AFFICHE (vect: Ttab) VARIABLES i : entier DEBUT POUR i VARIANT DE 1 A IMAX FAIRE ECRIRE(Ecran,vect[ i ] ) FINFAIRE FIN DEBUT DCO UTILISATION DE LA PROCEDURE AFFICHE FIN

page n° 90

FCO

Programmation structurée

NOTIONS SUR LES FICHIERS

Page n° 91

Programmation structurée

Notion sur les fichiers

27 GENERALITES SUR L'ORGANISATION DES INFORMATIONS En mathématiques, on ne s'intéresse qu'aux ensembles de valeurs. Les valeurs manipulées sont, la plupart du temps, numériques. Par contre en informatique on s'intéresse à d'autres types de valeurs non obligatoirement numériques. les ensembles de valeurs sont d'autre part finis et rangés sur des supports physiques. La notion d'accès à une valeur rangée sur un support devient fondamentale. Aux principaux problèmes associés à la gestion et au traitement automatique par ordinateur des ensembles finis de valeurs sont associées des algorithmes différents plus ou moins complexes suivant la nature de l'accès. Nous verrons comment sont organisés les ensembles d'informations sur leur support ainsi que les opérations de traitement usuelles: - insertion d'un élément, - suppression d'un élément, - consultation d'un élément

28 NOTION DE FICHIER Les informations que le processeur peut avoir à traiter se trouvent soit sur des unités périphériques, soit en mémoire centrale. Seules celles qui sont en mémoire sont directement accessibles à la machine. Les informations qui sont sur des unités périphériques sont rangées en "fichier".

28.1

Définition d'un fichier

Le fichier est un concept fondamental qui apparaît dans toutes les applications de gestion (entre autres). Un fichier contient un ensemble d'informations, concernant des individus ou des objets de même nature. Un fichier est un ensemble organisé d'articles ou d'enregistrements de même nature susceptibles de faire l'objet de traitements par les mêmes programmes ou produits par de tels traitements. Ex: Le fichier des licenciés d'un club sportif ou encore : Une discothèque.

page n° 92

Programmation structurée

28.2

Notion sur les fichiers

Les principaux accès On peut accéder aux informations d'un fichier par deux méthodes séquentiellement (accès séquentiel) directement (accès direct)

28.2.1

Accès séquentiel

Soit P un ensemble d'éléments. L'ensemble P est dit à accès séquentiel si l'on ne peut accéder à un élément quelconque "e" occupant la place n qu'après avoir accédé aux n-1 éléments qui le précèdent. Il existe un premier élément que l'on peut noter par exemple "e1" qui est la porte d'accès à l'ensemble P. On se déplace ensuite au sein de l'ensemble en passant d'un élément à celui qui le suit immédiatement.

28.2.2

Accès direct Soit P un ensemble d'éléments.

L'ensemble P est dit à accès direct lorsqu'il suffit de connaître le rang n de l'élément "e" pour y accéder, sans passer par les autres éléments de P.

28.3 28.3.1

Les éléments du fichier Notion d'enregistrement logique

Un article ou enregistrement logique est un ensemble structuré de rubriques se rapportant à un même objet ou à un même sujet. L'enregistrement est une suite de caractères dont on connaît la composition, c'est à dire la description ou le format. Les enregistrements sont écrit les uns à la suite des autres et lors des traitements, on lit un enregistrement, puis un autre, etc.

page n° 93

Programmation structurée

Notion sur les fichiers

LE FAIT D'AVOIR LES ENREGISTREMENTS RANGES LES UNS A LA SUITE DES AUTRES ET D'Y ACCEDER DANS LE MEME ORDRE DECRIT L'ORGANISATION SEQUENTIELLE. Ex: Sur une cassette pour que la tête de lecture lise le quatrième morceau il faut avoir déroulé la bande jusqu'à la fin du troisième, ou lu les trois premiers morceaux.

28.3.2

Notion de rubrique ou champ

On appelle RUBRIQUE le nom attribué à chaque zone ou ensemble de positions). Une rubrique est la plus petite unité logique d'un article à laquelle on puisse faire référence dans un programme. Ex: Le fichier des candidats à un examen ( un nom et trois notes) 01PAUL 110914 04JACQUES30217 07PIERRE 190912

/02ANDREE 021216 /05BERTRAND 121011 /09CECILE 091411

/03GERALD /06PATRICIA //

090409/ 100916/

!1 ARTICLE DE 17 CARACTERES! ! RUBRIQUES N° DU CANDIDAT !NOM NOTE 1 NOTE 2 NOTE 3! // = LABEL DE DEBUT OU DE FIN DE FICHIER / = SEPARATEUR ENTRE DEUX ARTICLES La zone contenant le numéro de l'élève sur deux positions pourrait avoir comme nom de rubrique: NO-ELV ou encore NUMELEVE ... En sortie FICHIER IMPRIMANTE (F2) BILAN DES NOTES / NOM DE L'ELEVE / / NOTE 1 / / NOTE 2 / / NOTE 3 / / MOYENNE / NOM DE L'ELEVE / / NOTE 1 / / NOTE 2 / / NOTE 3 / / MOYENNE / NOM DE L'ELEVE / / NOTE 1 / / NOTE 2 / / NOTE 3 / / MOYENNE

page n° 94

Programmation structurée

28.3.3

Notion sur les fichiers

Notion de caractère

Un caractère est le plus petit élément de donnée dans une rubrique. On peut dire que c'est le plus petit groupement de bits contigus significatifs.

28.3.4

Notion d'indicatif

Un indicatif est un groupe de données appartenant à l'article et permettant de l'identifier.

28.4

Les primitives d’accès

OUVRIR (nom du fichier) - Soit en entrée ou en sortie pour un fichier en

ACCES SEQUENTIEL - Soit en entrée et / ou sortie pour un fichier en

ACCES DIRECT Exemples : OUVRIR (FENTRE) en lecture OUVRIR (FIMPRI) en écriture

page n° 95

Programmation structurée

Notion sur les fichiers

LIRE (nom du fichier : zone réceptrice) Exemples : LIRE (FENTRE , ENREG) LIRE (FENTRE , NOM1)

ZONE RECEPTRICE : Copie conforme d’un élément du fichier (taille, description complète correspondante aux différentes rubriques d’un élément du fichier). Il y a transfert de l’information du périphérique vers la mémoire centrale. La zone réceptrice reçoit l’information correspondante à la lecture, et positionnement sur le début de l’élément suivant. On ne peut lire qu’un seul fichier à la fois.

ECRIRE (nom du fichier , nom de la zone) Exemple : ECRIRE (FIMPRI , LIGNE)

L’information est transférée de la mémoire centrale vers le périphérique choisi, il y a écriture de l’information et positionnement sur le début de l’élément suivant.

FERMER (nom du fichier) Exemples : FERMER (FENTRE)

Tout fichier doit être fermé : - Soit dans l’algorithme dès que ce fichier n’est plus utilisé - soit en fin d’algorithme On peut fermer tous les fichiers en même temps quelque soit leur mode d’ouverture. FERMER (FENTRE, FIMPRI)

page n° 96

Programmation structurée

Notion sur les fichiers

29 LE TRANSFERT DES DONNEES Nous avons vu que les informations que le processeur peut avoir à traiter se trouvent soit sur des unités périphériques, soit en mémoire centrale. Seules celles qui sont en mémoire sont directement accessibles à la machine.

Le transfert des données et par voie de conséquence la manipulation des fichiers revêt donc une grande importance.

A notre niveau nous nous contenterons de voir le schéma de principe de transfert des données.

page n° 97

Programmation structurée

Notion sur les fichiers

Fichiers en entrée

ZONE DES ENTREES

Mémoire centrale

ZONE DE TRAVAIL

ZONE DES SORTIES

Fichiers en sortie

SCHEMA DE TRANSFERT DES DONNEES:

page n° 98

Programmation structurée

Notion sur les fichiers

30 CE QU'IL FAUT RETENIR La notion de fichier est fondamentale, c'est sur elle que repose l'ensemble de l'informatique de gestion qui intéresse tous les informaticiens de l'Armée de terre. En effet toutes les informations utilisées sont rangés dans des fichiers sur des unités périphériques. Ces informations ne sont exploitables que lorsqu'elles ont été transférées en mémoire. Il est donc fondamental de comprendre et de savoir manipuler ces fichiers.

UN FICHIER EST UN ENSEMBLE ORGANISE D'ENREGISTREMENTS.

A CHAQUE TYPE DE FICHIER CORRESPOND DES OPERATIONS PARTICULIERES D' ACCES ET DE MANIPULATION DES DONNEES QU'IL EST IMPORTANT DE CONNAITRE.

page n° 99

Programmation structurée

Notion sur les fichiers

31 EXERCICES Enoncé de l’exercice n° 9 Ecrire une fonction qui, dans un fichier séquentiel contenant uniquement des entiers positifs, retourne la plus grande valeur du fichier. On considère que le fichier peut-être vide. Ecriture de l'algorithme Algorithme Principal TYPE Tenreg = ENREGISTREMENT Nb : entier FIN Tfic = fichier de Tenreg FONCTION MAX ( @ FIC: Tfic) Resultat : entier VARIABLES valmax, val : entier DEBUT OUVRIR en lecture (FIC) LIRE (FIC, val) valmax ← 0 SI FIN DE FICHIER (FIC) ALORS ECRIRE("Fichier vide") SINON

TANT QUE NON FIN DE FICHIER (FIC) FAIRE SI valmax < val ALORS valmax ← val FINSI LIRE (FIC, val) FINFAIRE

FINSI Resultat ← valmax FERMER (FIC) FIN DEBUT DCO FIN

UTILISATION DE LA FONCTION MAX

page n° 100

FCO

Programmation structurée

Notion sur les fichiers

Enoncé de l’exercice n° 10 Ecrire un prédicat qui permet la suppression du premier élément de valeur Valref dans un fichier séquentiel. (on obtient dans ce cas un nouveau fichier qu'il faut définir) Lorsque la suppression est effective le prédicat retourne VRAI, et FAUX inversement.

Ecriture de l'algorithme Algorithme Principal TYPE Tenreg = ENREGISTREMENT Nb : entier FIN DCO type : nom logique du fichier FCO Tfic = fichier de Tenreg PREDICAT SUPPVAL ( @ FENTREE Valref @ FNOUV Resultat : booléen

: Tfic, : entier, : Tfic)

VARIABLES Val Trouve

: entier : booléen

DEBUT trouve ← FAUX OUVRIR en lecture (FENTREE) OUVRIR en écriture (FNOUV) LIRE (FENTREE, val) TANT QUE NON FIN DE FICHIER (FENTREE) FAIRE SI val = valref ET NON trouve ALORS trouve ←VRAI SINON ECRIRE (FNOUV, val) FINSI LIRE (FENTREE, val)

page n° 101

Programmation structurée

Notion sur les fichiers

FINFAIRE Resultat ← trouve FERMER (FENTREE, FNOUV) FIN DEBUT DCO UTILISATION DU PREDICAT SUPPVAL FIN

page n° 102

FCO

Programmation structurée

Notion sur les fichiers

Enoncé de l’exercice n° 11 Ecrire une procédure qui permet le chargement des douze mois de l'année en clair dans un vecteur à partir d'un fichier séquentiel. Chaque mois devra occuper le poste qui correspond à son rang dans l'année. Ecriture de l'algorithme

Algorithme Principal CONSTANTE IMAX = 12 TYPE

MM = ENREGISTREMENT Nu_mois : entier Clair_mois : chaîne de caractères FIN Tfic Ttab

= fichier de MM = tableau[ IMAX ] de chaîne de caractères

PROCEDURE CHARG_MOIS

(@ F1 : Tfic, @ Vect : Ttab)

VARIABLES Val : MM DCO variable contenant un enregistrement du fichier FCO DEBUT OUVRIR (F1) en lecture LIRE ( F1 , Val) TANT QUE NON FIN DE FICHIER (F1) FAIRE Vect [Val.Nu_mois]← Val.Clair_mois LIRE ( F1 , Val ) FINFAIRE FERMER (F1) FIN DEBUT DCO FIN

UTILISATION DE LA PROCEDURE CHARG_MOIS FCO

page n° 103

Programmation structurée

ANNALES

page n° 104

Programmation structurée

Annales

32 EXAMEN DE L’EA2/FS DU BSTAT 2000 EA2/FS BSTAT 2000 Session Evaluation Domaine Filière Durée

: Mai 1999 : E5 : MSI : Toutes filières : 3 heures

C- Programmation Structurée

Durée : 1 heure

L’épreuve comporte deux exercices indépendants : C-1 : Exercice 1 (7 points) (Durée conseillée : 15 à 20 minutes maximum) Une manière originale pour calculer le carré d’un nombre entier positif N est d’effectuer la somme des N premiers nombres impairs. Exemples : 4 = 1 + 3 +5 + 7 = 16 5=1+3+5+7+9 = 25 Ecrire un algorithme permettant de calculer le carré d’un nombre entier positif saisi par l’utilisateur en utilisant la méthode ci-dessus.

C-2 : Exercice 2 (13 points) Le Cercle Mixte désire mettre en place un logiciel permettant de gérer la réservation des chambres. Les chambres seront obligatoirement réservées avant utilisation. Pour cela, on utilisera 2 fichiers : Un fichier CHAMBRES.DAT existant contenant les caractéristiques des différentes chambres : NumeroChambre Enservice

Entier Booléen

(3 chiffres) VRAI : FAUX :

La chambre est utilisable La chambre est en travaux

Un fichier RESERVAT.DAT qui n’existe pas actuellement, qui contiendra les renseignements suivants : NumeroChambre DateDebut DateFin Occupant

Entier TypeDate TypeDate Chaîne de caractères

(3 chiffres) Nom de l’occupant (15 caractères max)

Le TypeDate permet la comparaison immédiate entre 2 dates et ne nécessite pas de primitives particulières pour la lecture et l’écriture. Travail demandé : 1. Décrire les différentes variables, structures ou enregistrements nécessaires au traitement. 2. Ecrire l’algorithme d’une procédure permettant de réserver une chambre d’une date de début à une date de fin pour un nouveau client. On n’oubliera pas de vérifier la possibilité de réservation à une date donnée. 3. Ecrire l’algorithme d’une procédure permettant de visualiser les taux d’occupation de toutes les chambres utilisables pour une période donnée. NB : Les questions 2 et 3 sont indépendantes.

page n° 105

Programmation structurée

Annales

CORRIGE : Calcul d’un carré d’un nombre positif Déclaration des variables VARIABLES N I J T

TYPE Entier Entier Entier Entier

Signification Variable de saisie Variable d’indiçage de la boucle Variable pour les nombre impairs Variable pour le cumul des différentes valeurs

Définition des paramètres DONNEES : RESULTATS : PROCEDURE CARRE ( ) DEBUT DCO Saisie d’un nombre entier positif et vérification FCO Efface écran Répéter Ecrire (‘Entrez un nombre positif : ‘) Lire (N) Jusqu’à N >= 0 DCO Initialisation des variables FCO J  1 T  0 DCO Boucle pour la recherche des nombres impairs FCO POUR I variant de 1 à N FAIRE T  T + J J  J + 2 FIN FAIRE DCO Affichage de la valeur du carré FCO Ecrire (‘carré de ‘ , N , ‘ = ‘ , T) FIN

page n° 106

Programmation structurée

Annales

Gestion de la réservation des chambres d’un cercle mixte Déclaration des structures des deux fichiers Description de la structure du fichier (F1) CHAMBRES.DAT Nom de la structure : Chambre Nom du champ num serv

Type Entier Booléen

Signification Numéro de la chambre Vrai : La chambre est utilisable Faux : La chambre est en travaux

Description de la structure du fichier (F2) RESERVAT.DAT Nom de la structure : Réserve Nom du champ num datdeb datefin nom

Type Entier Date Date Chaîne

Signification Numéro de la chambre Date de début de la réservation Date de fin de réservation Nom de l’occupant

Déclaration des variables Variables F1 chambre enreg1 F2 reserve enreg2 a b resa ch trouve rep

Type Signification Fichier(chambre) Nom du fichier contenant la liste des chambres Structure Structure du fichier Chambres.dat Structure chambre Structure de travail pour le fichier F1 Fichier(reserve) Nom du fichier des chambres réservées Structure Structure du fichier Reservat.dat Structure resa Structure de travail pour le fichier F2 Date Variable de saisie pour la date de début de location Date Variable de saisie pour la date de fin de location Entier Variable pour la réservation Entier Numéro de la chambre Entier Variable pour la recherche Car Variable de continuation

Définition des paramètres DONNEES : RESULTATS :

page n° 107

Programmation structurée

Annales

PROCEDURE PRINCIPALE ( ) DEBUT DCO Ouverture des fichiers et boucle pour les réservations FCO Ouvrir en entrée ( F1 ) Ouvrir en sortie ( F2 ) Répéter DCO Saisie des dates de réservation et positionnement en début du fichier F1 FCO Efface écran Ecrire (‘Entrez la date de début de réservation’) Lire (a) Ecrire (‘Entrez la date de fin de la réservation’) Lire (b) Repositionner le fichier (F1) en début Lire (F1, enreg1) DCO Initialisation des variables FCO resa  0 ch  0 trouve  0 DCO Boucle pour réservation d’une chambre FCO TANT QUE non fin de fichier (F1) ET resa = 0 FAIRE DCO Recherche d’une chambre FCO SI NON enreg1.serv ALORS DCO Chambre non louable, voir la suivante FCO Lire (F1, enreg1) SINON DCO Recherche si chambre déjà louée, par appel de s/pgm FCO ch  enreg1.num REC(F2, a, b, ch, trouve) DCO Vérification de la réponse et appel du s/pgm de réservation FCO SI trouve = 1 ALORS resa  1 LOC(F2, a, b, ch) SINON Lire (F1, enreg1) FIN SI FIN SI FIN FAIRE

page n° 108

Programmation structurée

Annales

DCO Vérification de la rupture de la boucle FCO SI resa = 0 ALORS Ecrire (‘Rien à louer’) SINON Ecrire (‘Réservation effectuée’) FIN SI DCO Demande si autre réservation FCO Répéter Ecrire (‘Autre réservation ( O / N ) ‘) Lire (rep) Jusqu’à rep = ‘O’ OU rep = ‘N’ Jusqu’à rep = ‘N’ Fermer (F1, F2) FIN Sous-programme de recherche d’une chambre Déclaration des variables Variables Type F2 Fichier(reserve) reserve enreg2 a b c d ch trouve indic

Structure Structure reserve Date Date Date Date Entier Entier Entier

Signification Nom du fichier contenant la liste des chambres occupées Structure du fichier Reservat.dat Structure de travail pour le fichier F2 Variable pour la date de début de réservation Variable pour la date de fin de réservation Variable de recherche pour enreg2 date de début Variable de recherche pour enreg2 date de fin Numéro de la chambre à rechercher Variable de recherche et aiguillage Variable de recherche

Définition des paramètres DONNEES : F2, a, b, ch RESULTATS : trouve PROCEDURE REC (F2, a, b, ch, trouve) DEBUT DCO Initialisation des variables et positionnement en début du fichier F2 FCO indic  0 trouve  2 Repositionner le fichier (F2) en début Lire (F2, enreg2)

page n° 109

Programmation structurée

Annales

DCO Vérification si fichier vide FCO SI fin de fichier (F2) ALORS Indic  1 DCO Recherche si la chambre est libre FCO SINON TANT QUE non fin de fichier (F2) ET trouve = 2 FAIRE DCO Recherche sur l’égalité de la chambre et si les dates sont différentes FCO SI ch = enreg2.num ALORS c  enreg2.datdeb d  enreg2.datfin SI (a < c ET b < c) OU (a > d ET b > d) ALORS indic  1 SINON indic  0 trouve  0 FIN SI DCO Les chambres n’ont pas le même numéro FCO SINON indic  1 FIN SI Lire (F2, enreg2) FIN FAIRE FIN SI DCO Mise à jour de la variable trouvé pour la suite du traitement FCO SI indic = 1 ALORS trouve  1 SINON trouve  0 FIN SI FIN Sous-programme de réservation d’une chambre Déclaration des variables Variables Type F2 Fichier(reserve) reserve enreg2 a b ch

Structure Structure reserve Date Date Entier

Signification Nom du fichier contenant la liste des chambres occupées Structure du fichier Reservat.dat Structure de travail pour le fichier F2 Variable pour la date de début Variable pour la date de fin Numéro de la chambre à réserver

Définition des paramètres DONNEES : F2, a, b, ch RESULTATS : PROCEDURE LOC (F2, a, b, ch) DEBUT page n° 110

Programmation structurée

Annales

DCO Préparation de l’enregistrement FCO Efface écran enreg2.num  ch enreg2.datdeb  a enreg2.datfin  b Ecrire (‘Entrez le nom de l’occupant : ’) Lire (enreg2.nom) DCO Positionnement du fichier en fin et écriture dans F2 FCO Repositionnement en fin de fichier avant écriture Ecrire (F2, enreg2) FIN Procédure du taux d’occupation des chambres Déclaration des variables Variables F1 Chambre Enreg1 F2

Type Fichier(chambre) Structure Structure chambre Fichier(reserve)

reserve enreg2 s1

Structure Structure reserve Date

s2

Date

dd df cpt nbre

Date Date Entier Entier

Signification Nom du fichier contenant la liste des chambres Structure du fichier Chambres.dat Structure de travail pour le fichier F1 Nom du fichier contenant la liste des chambres occupées Structure du fichier Reservat.dat Structure de travail pour le fichier F2 Variable de saisie pour le début de la période d’occupation Variable de saisie pour la fin de la période d’occupation Date de début de la réservation dans F2 Date de fin de la réservation dans F2 Cumul du nombre de nuitées Nombre de chambre valides dans le fichier F1

Définition des paramètres DONNEES : RESULTATS :

page n° 111

Programmation structurée

Annales

PROCEDURE OCCUPATION ( ) DEBUT DCO Initialisation des variables FCO

cpt  0 nbre  0 DCO Boucle pour la recherche du nombre chambres à louer dans F1 FCO

Ouvrir F1 en entrée Lire (F1, enreg1) TQ non fin de fichier (F1) FAIRE SI enreg1.serv ALORS nbre  nbre + 1 FIN SI Lire (F1, enreg1) FIN FAIRE Fermer (F1) DCO Saisie de la période d’occupation des chambres FCO Efface écran Ecrire (‘Entrez la date de début de période d’occupation’) Lire (s1) Ecrire (‘Entrez la date de fin de période d’occupation’) Lire (s2) DCO Boucle pour la recherche des chambres occupées pour la période donnée FCO Ouvrir F2 en entrée Lire (F2, enreg2) TQ non fin de fichier (F2) FAIRE DCO Chargement des dates de début et fin (F2) pour les chambres occupées FCO dd  enreg2.datdeb df  enreg2.datfin DCO Recherche sur la date d’occupation des chambres FCO Si dd <= s2 ET df => s1 ALORS Si dd < s1 ALORS dd  s1 SINON SI df > s2 ALORS df  s2 FIN SI FIN SI cpt  cpt + (df - dd) FIN SI Lire (F2, enreg2) FIN FAIRE Fermer (F2) DCO Calcul et affichage du résultat FCO Efface écran Ecrire (‘Taux d’occupation pour la période du : ‘ s1 ‘au : ‘ s2, ( cpt * 100) / (nbre * (s2 - s1)), ‘ % ‘) FIN

page n° 112

Programmation structurée

Annales

33 EXAMEN BLANC DE L’EA2/FS DU BSTAT 2001 PREPARATION à L’EA2/FS du BSTAT 2001 SUJET EXAMEN BLANC Evaluation......................................: E5 Domaine.........................................: M.S.I. Filière.............................................: Toutes filières Durée.............................................: 3 heures 30mn C) PROGRAMMATION STRUCTUREE (1 Heure) Le candidat traitera les deux exercices 1 Exercice 1 : Suite de nombres Soit une suite de nombres dont le 1er terme et le 2ème terme sont 1. A partir du troisième terme, les éléments de la suite sont calculés de la manière suivante : Terme suivant = Somme des deux termes précédents. Si on représente les termes de la suite par Un, on obtient U1 = 1 U2 = 1 U3 = 2 U4 = 3 U5 = 5 etc... Ecrire un algorithme permettant à un utilisateur de calculer et d'afficher les NB premiers termes de cette suite. NB est un entier supérieur à 1 qui sera entré par l'utilisateur. 2

Exercice 2 : Le cinéma 2.1 Présentation du problème Le PDG d’une société de distribution de films qui possède environ 2000 salles de cinéma, étudie chaque année leur bilan financier. Pour ce faire, il a besoin d’un programme récapitulant, pour chaque salle, le montant annuel des ventes ainsi que son rendement (le taux de remplissage moyen de la salle au cours de l’année). Et c’est à vous, que le directeur informatique demande de concevoir l’algorithme permettant de répondre au problème. 2.2 Description du fichier en entrée Vous disposez en entrée d’un fichier nommé “ventes” qui liste les ventes de toutes les séances de toutes les salles au cours de l’année passée. Pour chaque séance, le fichier comprend un enregistrement de la forme : Code salle Chaîne de 5 caractères

Nombre de places entier

Date séance tdate

Numéro séance entier

Nombre de places vendues entier

Montant des ventes de la séance réel

Pour une salle donnée, il peut y avoir plusieurs séances le même jour, plusieurs jours dans l’année mais les enregistrements sont triés par salle. Le fichier a été vérifié et ne contient aucune erreur.

page n° 113

Programmation structurée

Annales

2.3 Travail à effectuer Vous devez écrire un algorithme en programmation structurée, qui effectuera les travaux suivants : ♦ Calculer et afficher, pour chaque salle, les informations suivantes : − Son code − Le montant total des ventes sur l’année − Son rendement ♦ Ecrire dans un fichier nommé “ mauvais ” toutes les salles dont le rendement est inférieur à 60 %. Les informations qui devront apparaître sont : − Le code de la salle − Le rendement de la salle Formule permettant de calculer le rendement R : R = (N/M) * 100 N : Nombre total de places vendues dans l’année M : Nombre maximum de places théoriquement vendables ( = nombre de séances de l’année * nombre de places dans la salle)

page n° 114

Programmation structurée

Annales

PREPARATION à L’EA2/FS du BSTAT 2001 CORRIGE EXAMEN BLANC Evaluation............................................: E5 Domaine..............................................: M.S.I. Filière..................................................: Toutes filières Durée...................................................: 3 heures 30mn C) PROGRAMMATION STRUCTUREE 1. Corrigé exercice « Suite de nombres » ALGORITHME SUITE DCO DECLARATION DES DIFFERENTES VARIABLES FCO VARIABLES NB, COMPTEUR, SUIVANT, DERNIER, AVANTDERNIER

: ENTIER

DEBUT DCO SAISIE DU NOMBRE DE TERMES DE LA SUITEFCO ECRIRE(ECRAN;'Entrez le nombre de termes à afficher : ') REPETER LIRE(CLAVIER;NB) JUSQU'A NB > 2 DCO DEBUT DU TRAITEMENT CALCUL ET AFFICHAGE FCO ECRIRE(ECRAN; 'LES ', NB, ' TERMES DE LA SUITE SONT : ') ECRIRE(ECRAN; 'U1 = 1') ECRIRE(ECRAN; 'U2 = 1') AVANTDERNIER  1 DERNIER  1 COMPTEUR  2 DCO DEJA DEUX TERMES SONT AFFICHES FCO TANT QUE COMPTEUR < NB FAIRE COMPTEUR  COMPTEUR + 1 DCO ON CALCULE ET ON AFFICHE LE SUIVANT SUIVANT  DERNIER + AVANTDERNIER ECRIRE(ECRAN; 'U',COMPTEUR,' = ' , SUIVANT) DCO ON PREPARE LE TRAITEMENT SUIVANT AVANTDERNIER  DERNIER DERNIER  SUIVANT FINFAIRE FIN

page n° 115

FCO FCO

Programmation structurée

Annales

2. Corrigé exercice « Cinéma » ALGORITHME BILAN DCO DÉCLARATION DES DIFFÉRENTS TYPES DE DONNÉES TYPE DCO Le type date FCO T_date = ENREGISTREMENT Jour : ENTIER Mois : ENTIER Annee : ENTIER FIN DCO L’ENREGISTREMENT DU FICHIER VENTES FCO T_seance = ENREGISTREMENT Code : CHAINE DE CARACTERES Nb_places : ENTIER Date : T_date Numero : ENTIER Nb_ventes : ENTIER Montant_ventes : REEL FIN DCO L’ENREGISTREMENT DU FICHIER MAUVAIS T_mauvaise_salle = ENREGISTREMENT Code : CHAINE DE CARACTERES Rend : REEL FIN DCO DÉCLARATION DES VARIABLES FCO VARIABLES Ventes : fichier de T_seance Mauvais : fichier de T_mauvaise_salle Seance : T_seance Mauvaise_salle : T_mauvaise_salle Nb_seances : ENTIER Rendement : REEL Montant_ventes_total : REEL Nb_ventes_total : ENTIER Code_salle : CHAINE DE CARACTERES

page n° 116

FCO

FCO

Programmation structurée

Annales

DEBUT DCO

ON COMMENCE PAR OUVRIR LES FICHIERS ET LIRE UN PREMIER ENREGISTREMENTFCO

OUVRIR en lecture (Ventes) OUVRIR en écriture (Mauvais) LIRE (Ventes , Seance) DCO CETTE BOUCLE EST EFFECTUÉE UNE FOIS POUR CHAQUE SALLE TANT QUE NON FIN DE FICHIER (Ventes) FAIRE DCO

INITIALISATION DES VARIABLES, UNE FOIS POUR CHAQUE SALLE

Code_salle Nb_seances Montant_ventes_total Nb_ventes_total DCO

FCO FCO

 Seance.code 0 0 0

ON LIT SUCCCESSIVEMENT TOUS LES ENREGISTREMENTS DE LA SALLE FCO

TANT QUE (Code_salle = Seance.Code) ET NON FIN DE FICHIER(Ventes) FAIRE DCO ON CALCULE LES DIFFERENTS TOTAUX DONT ON A BESOIN FCO

Nb_seances  Nb_seances + 1 Montant_ventes_total  Montant_ventes_total + Seance.Montant_ventes Nb_ventes_total  Nb_ventes_total + Seance.Nb_ventes DCO ON LIT L’ENREGISTREMENT SUIVANT FCO LIRE (Ventes ; Seance) FINFAIRE DCO ON CALCULE LE RENDEMENT ET ON AFFICHE LE BILAN POUR LA SALLE FCO

Rendement  ( Nb_ventes_total / ( Nb_seances * Seance. Nb_places ) ) * 100 ECRIRE (Code_salle, Montant_ventes_total, R) DCO

SI RENDEMENT < 60 %, ON ÉCRIT EN PLUS LA SALLE DANS MAUVAIS FCO

SI Rendement < 60 ALORS Mauvaise_salle.Code = Code_salle Mauvaise_salle.Rend = Rendement ECRIRE (Mauvais , Mauvaise_salle) FINSI FINFAIRE DCO On pense à fermer les fichiers avant de terminer FERMER (Ventes) FERMER (Mauvais) FIN

page n° 117

FCO

Programmation structurée

Annales

34 EXAMEN DE L’EA2/FS DU BSTAT 2001 Evaluation Domaine Filière Durée de l’épreuve

: E5 : MSI : Toutes filières : 3 heures

C) Programmation structurée

durée : 1

Heure 1] présentation générale de l’exercice Votre Directeur qui vient d’organiser un cross de cohésion au niveau de l’entreprise, vous demande de lui éditer, à partir du fichier du Personnel c:\employes.edi et du fichier des résultats du cross c:\resucros.edi, les 6 meilleurs éléments de moins de 25 ans appartenant à la société afin de créer une équipe de compétition. NB : 

Tout le personnel n’a pas participé à l’épreuve, par contre certaines personnes extérieures à l’entreprise ont couru (et se trouvent donc dans le fichier des résultats).



Les fichiers fournis ont été contrôlés : ils ne contiennent aucune erreur (d’aucune sorte).



Les personnes inscrites sur le fichier imprimante doivent l’être dans l’ordre des performances (ordre croissant des temps). Leur nombre peut être < 6 (voire être nul)

2] description des fichiers

M Ou F

Fichier des personnels C:\employes.edi Organisation séquentielle Trié en croissant sur : numéro employé

Numéro Employé

Nom

Prénom

Code grade

divers

Date naissance

divers

code sexe

C célibataire D divorcé V veuf M marié

Situation famille code

Nb enfants

Notation annuelle

divers

{aaaa mm jj}

7 carac. Alphanumériques

Fichier des résultats du cross C:\resucros.edi Organisation séquentielle Trié en croissant sur : Numéro de dossard Si le coureur appartient à l’entreprise son n° de dossard est son n° d’employé

P.S (algorithme en Français)

Temps (en secondes)

Entier sur 5 carac. 7 carac. Alphanumériques

Date du jour

N° Séquentiel

Numéro dossard

Date limite

à Rennes le 21-02-2000

liste des 6 meilleurs coureurs (nés après le 21 02 1975)

1 2 3 4 5

MARCEL HONORE PIERRE SERGE GISELE

98AM106 98AM109 98UA133 98SB113 98SB211

N° employé

SCH ADJ SGT SGT SCH

BURNICHOU CHAVEL MURCHOU-LABOSSE LABRUNE DUPUIS

0H 30min 40sec. 0H 50min 6sec. 0H 53min 34sec. 1H 0min 17sec. 1H 1min 15sec.

Temps en heures, minutes, secondes

grade page n° 118

Programmation structurée

Annales

3] travail Vous devez écrire l’algorithme (présenté sous la forme d’un pseudo code indenté écrit en Français) permettant d’obtenir l’état imprimé décrit ci-dessus à partir des fichiers fournis. Vous pouvez utiliser un tableau de (..) éléments pour stocker les différents résultats intermédiaires. Le type TDATE qui pourrait être utilisé pour manipuler les dates du jour et de naissance est un type enregistrement contenant les champs aaaa, mm, jj représentant les années, mois et jour. On supposera existante une primitive LIREDATESYS(Date_Du_Jour) permettant de récupérer la date du jour du type TDATE.

page n° 119

Programmation structurée

Annales

CORRIGE EA2/FS BSTAT 2001 ALGORITHME CROSS_ENTREPRISE DCO les 2 fichiers sont triés sur le même critère à savoir - Numéro employé pour c:\employes.edi - Numéro dossard pour c:\resucros.edi ces données étant identiques pour un personnel de l’entreprise.FCO DCO Déclaration des constantes FCO CONSTANTE IMAX =6 DCO Définition des différents type de données FCO TYPE DCO le type TDate FCO TDate = ENREGISTREMENT Annee : entier Mois : entier Jour : entier FIN

DCO FORMAT AAAA FCO DCO FORMAT MM FCO DCO FORMAT JJ FCO

DCO le type TPersonnel FCO TPersonnel = ENREGISTREMENT Num_employe : chaîne de caractères Nom : chaîne de caractères Prenom : chaîne de caractères Grade : chaîne de caractères Divers : chaîne de caractères Date_nais : TDate Divers : chaîne de caractères Sexe : caractère Sit_fam : caractère Nb_enf : entier Notation_an : chaîne de caractères Divers : chaîne de caractères FIN DCO le type TResultat FCO TResultat = ENREGISTREMENT Num_dossard : chaîne de caractères Temps : entier FIN

page n° 120

Programmation structurée

Annales

DCO une cellule du tableau FCO Tcellule = ENREGISTREMENT Temps : entier Num_employe : chaîne de caractères Nom : chaîne de caractères Prenom : chaîne de caractères Grade : chaîne de caractères FIN DCO le typeTtab FCO DCO Il est demandé de rechercher les meilleurs coureurs de l’entreprise. Ils seront au maximum IMAX et rangés dans un tableau de IMAX + 1 cellules. L’enregistrement courant est stocké dans la dernière cellule du tableau [IMAX + 1] , puis on fait appel à la procédure de tri qui viendra éventuellement placé ce coureur dans les IMAX premiers. En résumé , on peut dire que la cellule IMAX + 1 sert de zone de manœuvre. L’affichage du tableau s’effectuera sur les IMAX cellules seulement FCO Ttab =

TABLEAU de 1 à IMAX + 1 de Tcellule

DCO Déclaration des constantes typées FCO CONSTANTE AN_25 : TDate

= (Annee :0025 , Mois :00 , Jour :00)

DCO procédure de tri du tableau contenant les personnels ayant participé au cross. le tri se fait en croissant sur le temps mis en secondes. méthode de tri : TRI A BULLES. FCO PROCEDURE trier_tableau

(@ tab :Ttab)

DCO variables locales à la procédure

FCO

VARIABLE borne , i permut tampon

: : :

entier booléen Tcellule

DEBUT DCO initialisation des variables FCO borne  IMAX permut  VRAI

DCO rappel : le tableau a une taille de IMAX + 1 FCO

page n° 121

Programmation structurée

Annales

TANT QUE Permut FAIRE permut  FAUX POUR i variant de 1 à borne FAIRE si tab[i].temps > tab[i+1].temps ALORS DCO Permutation des postes du tableau FCO tampon  tab[i] tab[i]  tab[i+1] tab[i+1]  tampon permut  VRAI fin si FIN FAIRE borne  borne – 1 FIN FAIRE FIN DCO procédure de stockage des info. dans la dernière cellule(n° IMAX + 1) du tableau puis appel de la procédure de tri qui classera la personne parmi les IMAX meilleurs si son temps est meilleur que les précédents déjà stockés FCO PROCEDURE remplir_tableau(@ tab :Ttab, personnel :TPersonnel, DateLimite :TDate) DEBUT SI personnel.Date_nais > DateLimite ALORS tab[IMAX + 1].Num_employe  personnel.Num_employe tab[IMAX + 1].Nom personnel.Nom tab[IMAX + 1].Prenom personnel.Prenom tab[IMAX + 1].Grade personnel.Grade tab[IMAX + 1].temps  dossard.temps trier_tableau(tab) FINSI FIN DCO Variables locales à la partie principale FCO VARIABLE personnel : TPersonnel employe : fichier de TPersonnel dossard : TResultat resucros : fichier de TResultat Date_Du_Jour : TDate DateLimite : TDate h,m,s,i : entier tab : Ttab

page n° 122

Programmation structurée

Annales

DCO PARTIE PRINCIPALE DEBUT

FCO

OUVRIR (employe) en lecture OUVRIR (resucros) en lecture DCO lecture de la date système, du jour FCO LIREDATESYS(Date_Du_Jour) DCO calcul de la date de naissance limite permettant de sélectionner les meilleurs éléments de moins de 25 ans FCO DateLimite.Annee DateLimite.Mois DateLimite.Jour

  

Date_Du_Jour.Annee – AN_25.Annee Date_Du_Jour.Mois Date_Du_Jour.Jour

DCO Initialisation du tableau de IMAX + 1 cellules FCO POUR i VARIANT DE 1 à IMAX + 1 FAIRE tab[i].temps  99999 FINFAIRE DCO lecture des 2 fichiers FCO LIRE(employe , personnel) LIRE(resucros , dossard) DCO Recherche des employés présents dans le fichier resucros. Stockage dans un tableau des IMAX meilleurs scores éventuels. Arrêt du traitement dès qu’un des fichiers est lu entièrement. FCO TANT QUE NON FIN DE FICHIER (employe) ET NON FIN DE FICHIER (resucros) FAIRE SI personnel.Num_employe < dossard.Num_dossard ALORS LIRE ( employe , personnel ) SINON SI personnel.Num_employe > dossard.Num_dossard ALORS LIRE (resucros, dossard) SINON DCO Concordance entre les numéros de dossard et employé FCO remplir_tableau (tab,personnel, DateLimite) LIRE(employe , personnel) LIRE(resucros , dossard) FINSI FINSI FINFAIRE

page n° 123

Programmation structurée

Annales

DCO fermeture des fichiers FCO FERMER (employe) FERMER (resucros) DCO lorsqu’il n’y a pas de coureur stocké dans le tableau (chose normalement impossible) il faut prévoir d’imprimer un message d’avertissement FCO SI tab[1].temps = 99999 ALORS ECRIRE(‘ETAT NEANT’) ; SINON DCO impression du titre de l’état FCO ECRIRE (Imprimante,‘à Rennes le ’, Date_Du_Jour.Jour,’-‘ , Date_Du_Jour.Mois,’-‘, Date_Du_Jour.Annee ,’ liste des ‘ , IMAX , ‘ meilleurs coureurs(nés après le’ , DateLimite.Jour, ‘ ‘ , DateLimite.Mois , ‘ ‘ , DateLimite.Annee,’)’) DCO Affichage des IMAX meilleurs coureurs ou moins FCO i1 TANT QUE (i <= IMAX) ET (tab[i].temps <> 99999) FAIRE DCO Conversion de Tab[i].temps, exprimé en secondes, en heures, minutes et secondes FCO h tab[i].temps DIV 3600 m (tab[i].temps - h*3600) DIV 60 s  tab[i].temps – (h*3600) – (m*60) ECRIRE ( Imprimante, i , ‘ ‘, tab[i].Num_employe , ‘ ‘, tab[i].Grade, ‘ ‘, tab[i].Nom, ‘ ‘, tab[i].Prenom, ‘ ‘, h , ‘H ‘ , m , ‘min ‘ , s , ‘sec.’ ) i  i +1 FINFAIRE FINSI FIN

page n° 124