Algorithmiques .docx

Algorithmiques de programmation : Première partie : L'algorithmique : I : Méthode de programmation : Introduction : 30 % du coût d'un logiciel est consacré à sa maintenance (sécurité qui consiste à maintenir le produit en bon fonctionnement + développement qui consiste à adapter le produit aux changements (organisationnels, réglementaires, techniques). Les défauts d'un logiciel sont : non sûreté ; non souplesse ; non compatibilité ; non adaptabilité ; non portabilité ; non garantie. La majorité de ces problèmes sont dus à la méthode d'analyse de conception (avant la production du logiciel, c'est-à-dire des besoins qui vont être remplis par le logiciels). Ces résultats montent la nécessité de maîtriser la conception et l'écriture du logiciel. Cette maîtrise passe par l'apport de méthodes dans le processus de production du logiciel. Les différentes étapes du développement du programme sont : analyse et conception ; réalisation (codage) ; rédaction de la documentation. 1 : De l'analyse à la programmation : problème ; détermination des différents besoin du futur logiciel ; codage avec le langage approprié ; observation des résultats ; possibilité de modifier soit la partir algorithmique soit la partie logicielle. center7620000 1.1 : L'énoncé informatique d'un problème : définir les résultats à obtenir ; définir les sources d'information ; définir les traitements à réaliser. 1.2 : Méthode descendante itérative : découpage du problème en fonctions (sous problèmes) ; découpage des fonctions en sous-fonctions (phase d'affinement) ; description de chaque module avec le langage algorithmique. center7620000 L'analyse est terminée lorsque tous les modules ont été substitués par des algorithmes. À chaque découpage, vérification de cohérence par rapport à ce qui est demandé. Si une impossibilité se révèle au niveau i, il faut remonter au niveau i-1 pour reprendre l'analyse. Une erreur d'analyse DOIT être décelée bien avant avant que l'algorithme ne soit tradui dans le langage choisi. 1.3 : Algorithme et organigramme : L'algorithme est donc la phase terminale dé découpage fonctionnel et exprime dans un langage plus ou moins formel une succession d'actions supposées réalisables par un ordinateur. Le langage algorithmique s'appuie sur notre langue naturelle, mais aussi sur les structures de contrôle classiques telles que les tests, les boucles, … À cette phase de l'analyse, on s'inquiète de l'implémentation des données en machine (au niveau du volume, mais pas au niveau du matériel). Exemple : détermination de la parité d'un nombre. Algorithme : la suite des instructions que l'ordinateur doit exécuter peut s'exprimer ainsi : demander à l'utilisateur de taper un nombre entier (clavier) ; lire le nombre (mémoriser) ; si le nombre est pair, afficher « nombre pair », sinon, afficher « nombre impair » (test et actions). Organigramme : une expression graphique de l'algorithme : 3 types d'éléments : 1 - suite d'instructions qui s'exécutent séquentiellement : Une instruction => Une instruction => … 2 – Les conditions ou tests qui orientent la marche du programme dans un des directions : => Condition : vrai faux. 3 – L'ordre dans lequel le programme avance est indiqué par une ligne fléchée joignant les rectangles et les losanges. center7620000 2 : La réalisation : center7620000 3 : la documentation : Deux types de documentations : Documentation externe ou utilisateurs : c'est un guide d'exploitation destiné aux utilisateurs de l'application. Il doit être clair et pédagogique. Documentation interne ou technique : elle est destinée à ceux qui vont compléter et maintenir l'application. Elle doit contenir les phases d'analyse, les découpages, les algorithmes, les structures de données, les programmes, les astuces d'optimisation, … II : Algorithmique : 1 : Introduction : Un algorithme est composé d'une suite d'opérations dont le but est de transformer les données en résultats. Ceci implique l'existence : d'objets manipulés (informations) ; d'opérations : calculs élémentaires ; d'enchaînements : séquencements des opérations. Structure de l'algorithme : En tête. Déclaration. Corps de l'algorithme. Fin de l'algorithme. 2 : Les objets : Toute information doit posséder : un nom ; un type : catégorie à laquelle il appartient caractérisée par : un domaine de valeur, des propriétés et des opérations attachées à ce type ; une valeur qui donne l'état de l'objet et qui peut être : créée : résultat nouveau ; conservée ; modifiée : transformation dynamique dans le temps ; variable ; une représentation physique. 2.1 : Les valeurs et les types : Valeur : le but d'un programme est de calculer les valeurs. L'ordinateur, lui, manipule des représentations de ces valeurs : octets ou mots mémoire. Types : Caractères : représenté entre des guillemets ; l'alphabet usuel en majuscules et minuscules ; les chiffres de « 0 » à « 9 » ; quelques symboles spéciaux ($, @, <, >, etc... Chaînes de caractères : une suite de caractères. Exemple : « Bonjour ». Logique ou booléen : valeur dans l'ensemble {Vrai ; Faux}. Entier : ensemble des nombres entiers relatifs, une variable de type entier supporte les opérations : +, -, *, /. Exemple : 249 ; 1859. Réel (ou fractionnaire) : désigne les nombres ayant une partie fractionnaire. Exemple : 123,15. 2.2 : Les objets de base : Constante : a un nom fixe et une valeur fixe. Exemple : Prix=30,50 Euros. Variable : a un nom fixe, un type fixe et une valeur variable selon le moment où on l'observe pendant le déroulement du programme. Tableau : a un nom fixe, un type fixe et plusieurs valeurs variables. Chaque valeur du tableau est différenciée des autres par son indice (rang où elle se trouve). Un tableau recoupe donc plusieurs éléments de même type, chacun des éléments est référencé par le nom du tableau et son indice. EXEMPLE : Soit un tableau « TABNOTE » contenant les notes d'un étudiant. TABNOTE center7620000 Les expressions : une expression désigne des calculs de valeurs à partir d'autres valeurs et opérations. Ces valeurs peuvent être des constantes, des valeurs de variables, d'éléments de tableaux ou des expressions. Exemples : 3+1 X+3 X : le nom d'une variable entière. T(2)+7 T : le nom d'un tableau, T(2) : deuxième élément du tableau T. A+B*C A, B, C : les noms de variables. L'ordre des opérations est déterminé par les priorités : * avant +... Il vaut mieux utiliser des parenthèses : (A+B)*C =/= A+(B*C) 3 : Les actions élémentaires : Elles portent sur des objets (caractère, entier, réel) et traitent l'information proprement dite. 3.1 : Déclaration : Il est nécessaire de déclarer tout objet utilisé dans un algorithme et de préciser son type. Une constante ou une variable est désignée par un nom : c'est l'identificateur. Celui-ci est une suite de caractères alphanumériques dont le premier est une lettre. Notation : Var liste des identificateurs :type Exemple : Var TOTO, TITI :Booléen Var NOM :Chaîne de caractères 3.2 : Affectation : Notation : Variable <== Valeur Exemple : A <== B ranger dans l'emplacement de A la valeur de B A <== 3 ranger dans l'emplacement de A la valeur de 3 A <== (A+B)*3 ranger dans l'emplacement de A le résultat de (A+B)*3 Remarque : l'expression à droite du signe d'affectation peut contenir une fonction. 3.3 : Lecture : C'est le transfert de l'extérieur (périphérique) vers la mémoire : Notation : Lire (variable) Exemple : Lire (nombre) Il est également possible de lire des informations, d'autres périphériques (fichiers, disques, bandes, …). 3.4 : Ecriture : C'est le transfert de la mémoire vers l'extérieur (périphérique) : Notation : Ecrire (variable) Exemple : Ecrire (nombre) Exemple 1 : Ecrire un algorithme qui permet d'additionner deux nombres. En tête ==> Algorithme Calcul Jeu d'essai Déclaration ==> Var A, B, C :entier Début Corps de l'algorithme ==> lire (A, B) lire les valeurs de A et B A=7 ; B=3 C <== A+B mettre dans C la valeur de A+B C=10 écrire ( C ) écrire la valeur de C (résultat) Fin de l'algorithme ==> FIN Exemple 2 : Ecrire un algorithme qui permet de calculer la carré des nombres compris entre 15 et 20. Algorithme calculcar Var nb, nbcar :entier Début Jeu d'essai Nombre 15 nb <== 15 nbcar <== nb*nb nbcar = 15*15 écrire (nbcar) nbcar=256 Nombre 16 ... FIN 4 : Les éléments structurants : Ces types d'instructions vont commander le déroulement du programme dans le temps. 3 catégories de structures de contrôle : l'enchaînement ; le choix ; la répétition. 4.1 : L'enchaînement ou séquence : Les actions sont exécutées les unes à à la suite des autres dans l'ordre où elles se présentent. Action 1 Action 2 … Suite d'instruction ou bloc … Action n Exemple : 1 – faire le café : 2 : lire prendre un filtre lire (A,B) prendre le café C <== A+B mettre le café dans le filtre écrire (C) mettre l'eau de la cafetière brancher la cafetière mettre en route... 4.2 : Les choix : Ils permettent de prendre une décision en fonction de certaines conditions basées sur l'action élémentaire de comparaison. Notation : A) Algorithme : SI ALORS action ou bloc FINSI B) Organigramme : (voir Annexe 5) Exemples : 1 – Prendre le café : SI le paquet est vide ALORS prendre un nouveau paquet FINSI ouvrir le paquet 2 – Ecrire un algorithme qui affiche le plus grand des deux nombres : Algorithme plusgrand Var a,b,pgrand :entier Jeux d'essai : début lire (a,b) 1) a=120, b=200 2) a=14, b=10 pgrand <== a pgrand=120 pgrand=14 Si b > a Alors Vrai Faux pgrand <== b pgrand=200 instruction non exécutée FINSI écrire pgrand affiche : 200 affiche : 14 FIN 4.2.1 : Alternative : Algorithme : SI Alors action 1 ou bloc 1 SINON action 2 ou bloc 2 FINSI Organigramme : center7620000 Algorithme plusgrand Var a,b,pgrand :entier Jeux d'essai : début 431165140970003416309144000 lire (a,b) 1) a=120, b=200 2) a=14, b=10 pgrand <== a pgrand=120 pgrand=14 Si b > a Alors Vrai Faux pgrand <== b pgrand=200 instruction non exécutée SINON Vrai pgrand <== a instruction non exécutée pgrand = 14 FINSI écrire pgrand affiche : 200 affiche : 14 FIN 4.2.2 : Le choix multiple : Cette structure sera utilisée lorsqu'il n'y a plus deux alternatives possibles, mais plusieurs possibilités. Notation : Selon la valeur d'une variable faire valeur 1 : action 1 ou bloc 1 valeur 2 : action 2 ou bloc 2 valeur 3 : action 3 ou bloc 3 … valeur n : action n ou bloc n autrement action n+1 ou blocv n+1 FIN Selon Organigramme : center7620000 SI variable =valeur 1 Alors exécution l'action 1 Sinon SI variable =valeur 2 Alors exécuter l'action 2 Sinon SI variable =valeur3 Alors exécuter l'action 3 … SI variable =valeur n Alors exécuter l'action n Sinon exécuter l'action n+1 FINSI FINSI FINSI FINSI Exemple : VAR Opérateur :caractère Selon Opérateur Faire '+' : Additionner '-' Soustraire '*' Multiplier '/' Diviser autrement sortir du programme FINSELON 4.2.3 : Outil table de décision : Elles sont utiles lorsque l'on est en présence de conditions qui sont combinées entre elles. La table est composée de deux parties : les conditions et leurs valeurs ; les actions à réaliser en fonction des valeurs des conditions. Conditions Demande 1ère classe Oui Non 1ère classe disponible Oui Non Oui Non 2ème classe disponible Oui Non Oui Non Oui Non Oui Non Actions Réservation 1ère classe X X Réservation 2ème classe X X X Liste d'attente X X X Si (demande 1er classe = 'oui') et (1er classe dispo ='oui') et (2eme classe dispo ='oui') Alors Réservation 1er classe Si non Si (Demande 1er classe = 'oui') et (1er classe dispo = 'non') et (2eme classe dispo = 'oui') Alors (2eme classe dispos ='oui') alors réservation 2eme classe Si non Si (demande 1er classe = 'non') et (1er classe disponible ='non') et....... 4.3 : La répétition : Elle consiste à répéter plusieurs fois la même séquence d'actions. center7620000 4.3.1 : La répétition à l'infini : Notation : Algorithme Répéter (à l'infini) Action ou bloc d'actions Fin répéter Organigramme 4.3.2 Répétition soumise à une condition La répétition de l'action ou du bloc d'actions est effectué si la condition est vrai. Il existe 2 formes possibles : a) Notation : Algorithme Tant que faire Action ou bloc d'action Fin Tant que Organigramme 1156970-3429000Sous cette forme, la condition est vérifiée AVANT la première exécution de l'action ou du bloc d'action. Si lors du premier passage la condition est fausse, l'action peut ne pas du tout être exécuté (0 fois). Exemple: Ecrire un algorithme qui permet de calculer le carré des nombres compris entre 15 et 18. Algorithme Calculcar Var nb, nbcar :entier Début nb <== 15 Tant que nb ? 18 faire nbcar <== nb*nb écrire (nbcar) nb <== nb+1 Fin tant que FIN 1er passage nb=15 Vrai nbcar=225 affiche 225 nb=15+1=16 2ième passage nb=16 Vrai nbcar=256 affiche 256 nb=16+1=17 3ième passage nb=17 Vrai nbcar=289 affiche 289 nb=17+1=18 4ième passage nb=18 Vrai nbcar=324 affiche 324 nb=18+1=19 5ième passage nb=19 FAUX FIN b) Notation Algorithme Répéter Action ou bloc d'action jusqu'à Organigramme center000Sous cette forme, la condition est vérifié APRÈS la première exécution de l'action ou du bloc d'action. Ainsi l'action ou le bloc d'action sera exécuté 1 fois. Algorithme calculcar var nb,nbcar :entier Début nb <== 15 Répéter nbcar <== nb*nb écrire (nbcar) nb <== nb+1 jusqu'à nb?18 FIN Passage 1 nb=15 nbcar=225 affiche 225 nb=15+1=16 Vrai Passage 2 nb=16 nbcar=256 affiche 256 nb=16+1=17 Vrai Passage 3 nb=17 nbcar=289 affiche 289 nb=17+1=18 Vrai Passage 4 nb=18 nbcar=324 affiche 324 nb=18+1=19 FAUX FIN 4.3.3 : La répétition avec indice : Dans les cas précédents, le nombre d'exécutions des actions ou bloc était indéterminé. Ici, on connaît exactement le nombre d'exécution de l'action. Notation : Algorithme Pour variable (i) Allant de n1 à n2 pas p Faire action ou bloc d'actions Fin pour Organigramme center000 Algorithme calculcar var nb,nbcar :entier Début nb <== 15 Pour i allant de 1 à 4 Faire nbcar <== nb*nb écrire (nbcar) nb <== nb+1 Fin pour FIN Passage 1 : nb=15 i = 1 nbcar=225 affiche 225 nb=15+1=16 Passage 2 : nb=16 i=2 nbcar=256 affiche 256 nb=16+1=17 Passage 3 : nb=17 i=3 nbcar=256 affiche 256 nb=17+1=18 Passage 4 : nb=18 i=4 nbcar=324 affiche 324 nb=18+1=19 FIN 5 : Exemple de synthèse : Distributeur de tickets de métro. L'appareil ne rend pas la monnaie. 1 ticket plein tarif : 1,40 euros ; 1 ticket à 20% : 1,12 euros ; 10 ticket plein tarif : 11,20 euros ; 10 ticket à 20% : 8,96 euros. Les tickets sont imprimés 'plein tarif' ou '20 %' selon le cas. 1 : énoncé informatique : Sources d'information : touches quantités, touche réduction, pièces introduites. Résultats : affichage de la somme à payer, impressions des tickets avec tarifs. 2 : Premier découpage : Début Lire touche quantité QTE Lire touche réduction REDUC Déterminer le prix PRIX Afficher le prix PRIX Répéter lire (pièce, valeur) PRIX <== PRIX – valeur Afficher le prix PRIX Jusqu'à PRIX = 0 Imprimer les tickets REDUC FIN 3 : Algorithme : Tickets <== En tête Var QTE :entier (quantité de tickets demandés : 1 ou 10) REDUC :entier (O : sans réduction, 1 : avec réduction) PRIX :réel (somme introduite) VALEUR :réel (valeur de la pièce introduite) i :entier Partie déclaration Début lire (QTE) lire (REDUC) Si QTE=1 alors (* Calcul du prix *) Si REDUC=0 Alors PRIX <== 1,40 Sinon PRIX <== 1,12 Finsi Sinon (* QTE = 10 *) Si REDUC=0 Alors PRIX <== 11,20 Sinon PRIX <== 8,96 Finsi Finsi écrire (PRIX) Calcul Prix OU : SI (QTE = 1) et (REDUC = 0) Alors PRIX <=== 1,40 Finsi SI (QTE = 1) et (REDUC = 1) Alors PRIX <== 1,12 Finsi SI (QTE = 10) et (REDUC = 0) Alors PRIX <== 1,20 Finsi SI (QTE = 10)et (REDUC = 1) Alors PRIX <== 8,96 Finsi Répéter (* Prise en compte des pièces *) lire (valeur) PRIX <== PRIX – valeur écrire (PRIX) jusqu'à PRIX = 0 Pour i allant de 1 à QTE Faire (* Imprimer les tickets *) SI REDUC = 0 Alors écrire ('plein tarif') Sinon écrire ('20 %') Finsi Fin Pour. FIN 6 : Les autres types de données : Certaines données peuvent avoir un nombre limité de valeurs. Leurs types sont définis à partir d'autres types élémentaires. 6.1 : Les types construits : 6.1.1 : Le type énuméré : On définit en extension toutes les valeurs que peuvent prendre les variables de ce type. Les valeurs doivent être ordonnées. Elles sont en nombre infini. Exemple : Jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche) On peut écrire : Var j1, j2 :jour ; j1 <= mardi ; j2 <= dimanche ; Les opérateurs relationnels (>, <, =, <>) s'appliquent sur les différentes valeurs de ce type. Exemple : lundi < mardi < mercredi < jeudi < vendredi < samedi < dimanche 6.1.2 : Le type intervalle : On définit en compréhension toutes les valeurs que peuvent prendre les variables de ce type. Les valeurs doivent être ordonnées et on ne précisera que le minimum et le maximum. Exemple : Chiffre = 0 .. 9 Lettre = A .. Z Jour_ouvré = lundi .. vendredi Remarque : Les valeurs appartenant à un intervalle sont nécessairement de type déjà défini. Bien que les types énuméré et intervalle sont peu utilisés, ils permettent néanmoins d'accroître la lisibilité des algorithmes et facilitent les contrôles. 6.2 : Les types structurés : Il peut y avoir à traiter des lots de données qui peuvent être toutes de même type ou de types différents. Elles sont alors stockées dans une variable multiple à laquelle on donne : un nom (identificateur) qui désignera l'ensemble des données ; une autre information qui permettra de désigner individuellement chacune d'elles. Lorsque leur type est le même, les données sont rangées : dans un tableau, sinon ; elles sont représentées dans un enregistrement. 6.2.1 : Les tableaux : C'est un type structuré constitué d'un nombre fini d'éléments obligatoirement de même type. Celui-ci peut être simple ou structuré. Exemple : Supposons que l'on dispose des chiffres d'inflation pour chaque mois. Pour calculer l'inflation annuelle, il suffit de calculer la somme des données mensuelles. On stockera alors les données dans un tableau de 12 éléments : Tab_Inflation. 0,05 0,1 0,6 0,7 -0,4 -0,2 0,2 0,8 0,6 0,4 0,3 -0,2 1 2 3 4 5 6 7 8 9 10 11 12 Pour définir un tableau, il faut préciser un nom commun pour toutes ces données (ici Tab_Inflation) et un indice : variable entière pouvant prendre des valeurs entre 1 et le nombre d'éléments du tableau (par exemple, i entre 1 et 12). Cet indice indiquera le rang de l'élément dans le tableau. Exemple : Tab_inflation(1) : « le chiffre de l'inflation du mois de janvier. » Tab-Inflation(6) : « le chiffre de l'inflation du mois de juin. » Tab-Inflation(10) : « le chiffre de l'inflation du mois d'octobre. » Pour déclarer un tableau il faut : déclarer le type commun aux éléments du tableau ; le type de l'indice, généralement un intervalle. Exemple : Type TAB = TABLEAU (1 .. 12) de réel ; Var Tab_Inflation : Tab ; ou alors : Var Tab_Inflation = TABLEAU (1 .. 12) de réel. Si on utilise une variable entière i comme indice, celle-ci est de type 1 .. 12 (intervalle). Un tableau es caractérisé par sa taille (nombre d'éléments qu'il peut contenir). En général, lorsque ce nombre d'éléments n'est pas connu, on prévoir une taille suffisamment grande pour contenir tous les éléments (même si ceux-là sont en nombre inférieur à la taille déclarée). Exemple : 3 24 3 .. .. .. .. 342 1 2 3 .. .. .. .. 24 Ajout d'un point à la note Pour i allant de 1 à 24 Lire Tabnote (i) Si tabnote (i) <10 Alors tabnote(i) <== tabnote(i) +1 Finsi Ecrire Tabnote (i) Fin pour Exemple : Déclaration : VAR Tabnote : tableau (1 .. 24) réels Lecture : Pour i allant 1 à 24 faire lire Tabnote (i) ecrire Tabnote (i) FinPour i =1 lire Tabnote 1 (1) i = 2 lire Tabnote 2 (2) … i=24 lire Tabnote 24 (24) Exercice : écrire l'instruction qui permet d'ajouter un point aux notes inférieures à 10. Faire un test :  « si élément inférieur à 10, alors faire Tab(i) + 1 ». Pour i allant de 1 à 24 faire : Si Tabnote (i) < 10 alors Tabnote (i) <== Tabnote (i) + 1 Fin Si FinPour Pour i allant de 1 à 24 faire Ecrire Tabnote (i) Fin Pour Si le tableau contient une seule série de données, on dira que sa dimension est égale à 1 (il s'agit d'un vecteur ou tableau-colonne ou tableau ligne). S'il contient deux séries, sa dimension est égale à deux, c'est une matrice. Exemple : Considérons les chiffres mensuels de l'inflation, du chômage et des prix à la consommation. Nous stockerons ces 3 séries de données dans une matrice (tableau à 2 dimensions) : 1 0,05 0,03 0,1 2 0,1 0,2 0,01 3 0,6 0,5 0,03 4 0,7 0,3 0,2 5 -0,4 0,2 0,1 6 -0,2 0,1 0,07 7 0,2 -0,3 0,03 8 0,8 0,1 0,3 9 0,6 0,1 0,2 10 0,4 0,2 0,4 11 0,3 0,1 0,3 12 -0,2 0,3 0,3 1 2 3 Pour exploiter ce besoin, on aura besoin : d'un premier indice i pour parcourir les lignes ; d'un second indice j pour les colonnes. Soit le taleau ci-dessu : Type Tablo = TABLEAU (1..3, 1..12) de réels ; Var Tab_chiffres : Tablo . ou Var Tab_chiffres : tableau (1..3, 1..12) de réels. On écrira : Tab_Chiffres (1,9)' pour le taux d'inflation du mois de septembre ; Tab_Chiffres (2,9)' pour le taux de chômage du mois de septembre ; Tab_chiffres (3;9)' pour le taux à la hausse des prix à la consommation du mois de septembre. Exemples : 1 : lecture d'un tableau de 12 éléments. Algorithme lecture Voir Tab : tableau (1..12) du réel i : entier Début Pour i allant de 1 à 12 faire lire Tab (i) Fin Pour Fin 2 : lecture d'une matrice : Algorithme lecture.matrice Var Mat : tableau (1..3, 1..12) de réel i, j : entier Début Pour i allant de 1 à 12 faire Pour j allant de 1 à 12 faire lire Mat (i,j) FinPour FinPour Fin 6.2.2 : les enregistrements : Contrairement aux tableaux, ce type structuré permet de regrouper des données de types différents. Exemple : On identifie un ouvrage par un code, un titre, un ou plusieurs auteurs, un éditeur et éventuellement la date de parution. Ouvrage : Code Titre Auteur Editeur Date Ouvrage est une variable de type enregistrement. Chacune de ses 5 données est un champ pouvant être simple ou structuré. Syntaxe : Type Nom_Enreg = Enregistrement Champ 1: type ; Champ 2: type ; Champ 3: type ; … Champ n : type Fin. La variable Ouvrage se déclare ainsi : Type Livre = Enregistrement Code : entier ; Titre : Chaîne (20) ; Auteur : Chaîne (40) ; 1 auteur.Si 3: Auteurs = tableau (1..3) de chaîne (40) Editeur : Chaîne (25) Date = Enregistrement Mois = 1..12 Année = 1900,2011 Fin Fin Var Ouvrage : Livre Remarque : le champ Date est lui-même un enregistrement. Exemple : Pour exprimer un date sous la forme suivante : « lundi 23 septembre 1996 », on déclare la structure d'enregistrement suivante : Type Date = Enregistrement Jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche) ; Quantième = 1..31 ; Mois : janvier, février, mars, avril, mai, juin, juillet, août, septembre, octobre, novembre, décembre ; Année : 1990,2011 fin. Pour référencer un champ, on préfixe le nom de celui-ci avec le nom de l'enregistrement auquel il appartient : Var Dat1 : Date Dat1.jour <== lundi Dat1.quantième <== 23 Dat1.mois <== septembre Dat1.Année <== 1996 Autre exemple : Var Ouvrage : Livre Ouvrage.Auteur <== V.HUGO Si saisie du 3ème auteur : Ouvrage.Auteur(3) <== V.HUGO Ouvrage.Date.mois <== 10 Dans « Ouvrage », Rubrique « Date » et sous- rubrique « année » Ouvrage.Date.Année <== 1995 Code Titre Auteur Editeur Date Ouvrage.Titre Ouvrage.Auteur(2) Mois Année Ouvrage.Date.Année Exemple : Numéro Nom Prénom Discipline Année 1 2 3 12000 Type : Étudiant : enregistrement Numéro : Entier Nom : Chaîne (15) Prénom : Chaîne (15) Discipline : Chaîne (15) Année inscription. : Entiers ou (2005..2011) Type Intervalle Fin Var ETU : tableau (1..12 000) de étudiants i : entier Début Pour i allant de 1 à 12000 faire lire (ETU(i).Numéro) lire (ETU(i).Nom) lire (ETU(i).Prénom) lire (ETU(i).Discipline) lire (ETU(i).AnnéeInscription) Fin Pour Fin Var Compteur : entier Début compteur <== 0 Pour i allant de 1 à 12000 faire lire (ETI(i).AnnéeInscription) Si (ETU(i).AnnéeInscription) = 2005 alors Compteur <== Compteur + 1 FinSi Fin Pour Ecrire (« le nombre d'étudiants inscrit en 2005 est : », Compteur) Fin ATTENTION : EXAMEN ! 6.3 : Les fichiers : Un fichier est un ensemble de données. Il peut servir soit à la lecture, pour rentrer des informations dans un programme, soit à l'écriture pour sauvegarder les résultats obtenus. Les fichiers sont caractérisés par deux notions : le mode d'organisation : comment sont organisés les données dans le fichier (séquentiel, indexé, …) ; le mode d'accès : comment sont accédés les données dans le fichier (séquentiel, direct, binaire, …). Ces caractéristiques sont étroitement liées aux langages de programmation utilisés. Chacun de ces derniers offre différents types de fichiers. En algorithmique, nous nous limiterons par souci de facilité aux fichiers textes et aux fichiers d'enregistrement. L'utilisation d'un fichier se fait selon les phases suivantes : ouverture du fichier ; traitement du fichier ; fermeture du fichier. 6.3.1 : Les fichiers texte : Les fichiers de type Texte sont des fichiers séquentiels (mode d'organisation séquentielle). Les informations sont disposées de façon séquentielle, les unes à la suite des autres. Elles ne sont nu en ligne ni en colonne ! Elles sont repérées par un pointeur. Leur organisation est séquentielle et leur accès ne peut être que séquentiel. 6.3.2 : Les fichiers d'enregistrement : C'est un ensemble d'enregistrements (ou d'articles) de type structuré que l'on a déjà défini. Exemple : Type Étudiant = Enregistrements Numéro : entier ; NomPrénom : Chaîne(30) ; Discipline : Chaîne(25) ; Année_Inscrip : (1950..2011) Fin. Var E1 : Étudiant Fich_Étudiant : FICHIER de l'Étudiant ; niveau de fonction type E1.Numéro <== 123456 ; E1.NomPrénom <== « Dupont Lionel » ; E1.Discipline <== « Sciences Économiques » ; E1.Année_Inscrip <== 1996 Afficher (fich_Étudiantt, E1). On peut traiter un fichier d'enregistrements de manière séquentielle, mais son intérêt est de permettre un accès direct aux données. Lors de l'ouverture d'un tel fichier, le pointeur est positionné sur le premier enregistrement. On peut se déplacer directement sur n'importe quel enregistrement avant une opération de lecture ou d'écriture à l'aide de l'action. Positionner(Fichier, N°enregistrement) Remarques : Contrairement aux fichiers séquentiels, un fichier d'enregistrement peut être ouvert en lecture et en écriture. La taille d'un fichier de ce type est le nombre de ses enregistrements. 7 : La notion de sous-programmes : Dans la résolution d'un problème, on peut constater qu'une suite d'actions revient plusieurs fois. Dans ce cas, il serait judicieux de l'écrire une seule fois, et de l'utiliser autant de fois que c'est nécessaire, en effectuant des calculs avec des données différentes. Cette suite d'actions sera définie dans un sous-programme, qui peut prendre soit la forme d'une procédure, soit la forme d'une fonction. On perçoit alors un programme comme un ensemble de procédures/fonctions. La structuration d'un programme par morceaux (modules) est la base de la programme structurée et modulaire. 7.1 : La procédure : Une procédure est un sous-programme qui peut retourner 0, 1 ou plusieurs résultats. Déclaration, par ordre : constante ; type ; procédure ; variable ; type. Définition de la procédure : Procédure nom (liste d'arguments : type) : début corps de la procédure fin ; La première ligne s'appelle l'en-tête (ou la signature) de la procédure. La liste d'arguments est une suite de données à échanger avec d'autres programmes. Appel de la procédure : nom-de-la-procédure (liste d'arguments) ; Remarques : Si une liste d'arguments apparaît dans la définition d'un sous-programme, lors de l'appel de ce dernier, elle doit également apparaître dans l'action d'appel. Les listes d'arguments dans la définition d'un sous-programme et dans son appel doivent se correspondre. C'est-à-dire qu'il doit y avoir le même nombre d'arguments dans les deux listes. L'ordre d'apparition des arguments dans les deux listes doit être le même. Chaque argument d'une liste doit être de même type que son homologue de l'autre liste. La liste d'arguments dans la définition d'un sous-programme contient le type de chaque argument. Ce n'est pas le cas de celle de l'appel. Exemple : On veut écrire un algorithme qui calcule le salaire des commerciaux d'une entreprise. Celui-ci est composé d'un fixe différent d'un employé à un autre et d'une prime d'intéressement de 10% du chiffre d'affaire réalisé si celui-ci dépasse les 5000 Euros, de 3% sinon. On isolera la suite d'actions qui permet de rentrer les salaires fixes de chacun ainsi que leur chiffre d'affaire. Procédure Saisie(Var Sal, CA : entier) ; début Lire (« Entrer le salaire du commerciale : », Sal) ; Lire (« Entrer son chiffre d'affaire : », CA) ; fin. 7.2 : La fonction : Une fonction est un sous-programme qui retourne obligatoirement une valeur. Cette dernière sera stockée dans une variable qui porte le même nom que la fonction. Définition de la fonction : Fonction nom (liste d'arguments : type) : type ; début corps de la fonction fin ; Le nom de la fonction est utilisé comme identificateur d'une variable, on déclare alors le type de cette dernière. Appel de la fonction : var <== expression ( … fonction(liste d'arguments.) …) Exemple (suite) : De la même manière, on isole les actions permettant de calculer la commission de chaque commercial. Fonction Commission (Montant : réel) : réel ; Const plafond = 5000 Var taux : réel ; début Si Montant >= plafond Alors taux <== 0,1 Sinon taux <== 0,03 Fin Si ; Commission <== Montant * taux ; fin. On peut construire un troisième sous-programme qui calculera le salaire de chacun. Procédure Calcul_salaire ; Var Salaire, Sal_fixe, Chif_fixe, Chif_aff : réel ; début Saisie (Sal_Fixe, Chif_Aff) ; Salaire <== Sal_fixe + Commission(Chif_aff) Ecrire (Le salaire est de : ; Salaire) ; fin. Commentaires : les listes d'arguments sont optionnelles. La procédure Calcul_Salaire est le programme appelant. La procédure Saisie et la fonction Commission sont les programmes appelés. N'importe quel sous-programme peut être appelant ou appelé (il faut éviter les appels circulaires). Les arguments des Procédures/Fonctions appelées sont les paramètres formels (ou fictifs). Ils peuvent porter les mêmes noms (ou des noms différents) que leurs correspondants des programmes appelant qualifiés de paramètres réels (ou effectifs). Dans la procédure Calcul_Salaire, à l'appel de la procédure Saisie, les paramètres réels Sal_Fixe, Chif_Aff sont vides (ou contiennent plutôt n'importe quoi). Au retour du sous-programme, ils posséderont respectivement le salaire et le chiffre d'affaire réalisé. Dans l'appel à la fonction Commission (action qui calcule le salaire), le paramètre réel Chif_Aff possède déjà la valeur du chiffre d'affaire retournée par Saisie. Au retour de cette fonction, la variable Commission contiendra la valeur de la prime. 7.3 : La portée des données : Les sous-programmes communiquent entre eux par des paramètres. Une Procédure/Fonction peut avoir des variables internes qui ne sons pas visibles par les autres sous-programmes. Il s'agit de variables locales. Elles ne sont accessibles que par le sous-programme où elle sont définies. Par conséquent, différents sous-programmes peuvent avoir des variables locales portant le même nom éventuellement. Celles-ci n'auront pas la même signification pour chacun d'eux. On dira également que la portée dune variable locale est le sous-programme où elle a été définie. Exemple : Sal_Fixe et Chif_Aff sont des variables locales à Calcul_Salaire. Si une variable doit être accessible par tous les sous-programmes, il faut la définir comme une variable globale. Ceci veut dire qu'elle est lisible par tout sous-programme, et que sa valeur peut être utilisée ou modifiée n'importe où. La portée d'une variable globale est l'ensemble des sous-programmes pouvant l'utiliser. Exemple : Partie entête Algorithme Nom Variables Const VARIABLES TYPE VAR GLOBALES Procédure (A(----, -----) ; types) Partie déclaration début Var A, exemple <== Variables locales fin. Fonction B ( … : Type) : type Var ... fin. Appel du A Début ; lire si fin si A (….) W <== B (….) Résultat de l'exécution de la fonction B. Fin. 7.4 : Le passage par paramètre entre sous-programme : Il existe deux modes de passage de paramètres : le passage par valeur : Dans les sous-programmes appelés, les valeurs des paramètres transmis sont utilisées sans qu'il soit possible de les modifier. Les paramètres formels contiennent une copie des valeurs des paramètres réels. Exemple : Dans la fonction Commission, la valeur initiale du paramètre montant est conservée. le passage par adresse : Les sous-programmes appelés peuvent modifier les valeurs des paramètres réels transmis. Les paramètres formels contiennent l'adresse des paramètres réels. Les modifications de valeurs effectuées dans le programme appelé seront effectives au retour dans le programme appelant. Exemple : Dans la procédure Saisie, les valeurs affectées aux paramètres formels Sal et CA seront disponibles dans le programme appelant Calcul_Salaire. Partie 2 : Introduction au Visual Basic : 1 : Généralités : Pour la suite du cours, aller sur le Groupe « AES 4 ALGO-TD » ! Exercice : Écrire un algorithme qui permet d'obtenir les solutions d'une équation du second degré : Ax²+Bx+C Algorithme : Résolution_Équation2ndDegré Var A, B, C, D, X1, X2 Début Lire (A, B, C) ; Si A = 0 alors Écrire (« voir exercice numéro 6 ») Sinon D <== B*B-4*AC D < 0 alors Écrire (« Racines de type complexe ») FinSi Si D = 0 alors Écrire (« La solution est double », -B/2*A) FinSi Si D > 0 alors Écrire (« Les deux racines distinctes sont », -B-?D/-2A*C, -B+?D/-2A*C) FinSi FinSi Fin Exercice : Un vendeur perçoit chaque mois un salaire composé d'une partie fixe et d'une partie variable. La partie fixe est de 1000 euros et la partie variable est constituée d'une commission de 10 % sur le chiffre d'affaire. Déterminez les salaires mensuel et annuel d'un vendeur. Ajoutez les instructions qui permettent de faire les mêmes calculs pour plusieurs salariés. Algorithme : Salaire Constante (Sal_fixe = 1000), (taux = 0,1) = réel Var Sal_M, Sal_Com, Sal_An, CA, mois = réel Var Rep = chaîne de caractères Début ; Rep <== « Oui » Répéter. Sal_An <== 0 Pour i allant de 1 à 12 faire : Lire (« CA », CA) ; Commission <== CA*Taux ; Sal_M <== Sal_fixe + Sal_Com ; Écrire (« Salaire mensuel », Sal_M) ; Sal_An <== Sal_An + Sal_M ; Fin Pour Écrire (« Le salaire annuel est... », Sal_An) ; Ecrire (« Voulez-vous continuer ? », Rep) ; Lire (« Voulez-vous calculer les salaires pour un autre vendeur ? Oui/Non », Rep) ; Jusqu'à Rep = Non ; Fin. Exercice : Soit A et B deux variables de type réel séparées par une donnée du type caractère représentant l'opération à effectuer. Il permet de simuler une machine à calculer de poche. Algorithme : Calculatrice. Var : A, B, Res : réels Var : Op : caractère. Début ; Écrire (« Saisir l'opération ») ; lire (« A, Op, B) ; Selon Op Faire « + » : Res <== A+B  Écrire (« Le résultat est : » A+B); « - » : Res <== A-B ; Écrire (« Le résultat est : » A-B); « * » : Res <== A*B ; Écrire (« Le résultat est : » A*B); « / » : Res <== A/B » ; Écrire (« Le résultat est : » A/B); Fin Selon Écrire (Res) ; Fin. Exercice : Écrire un algorithme permettant la lecture ainsi que la recherche du maximum et du minimum dans un tableau à une dimension contenant 10 éléments. Algorithme : Minimax i : entier x : Tableau (1 .. 10) de réels MIN, MAX : réels Début Écrire (« Entrez les nombres du tableau SVP ») ; Lire (X(1)) ; MIN <== X(1) ; MAX <== X(1) ; Pour i = 2 à 10 Faire Lire (X(i)) ; SI (x(i)) > MAX Alors MAX <== (i) ; SINON SI (x(i)) < MIN Alors MIN <== (i) ; Fin Si ; Fin Si ; Fin Pour ; Écrire (« Minimum = » MIN, « Maximum = », MAX) ; Fin. Exercice : Écrire un algorithme qui permet de chercher la position d'un élément dans un tableau contenant 30 éléments. L'élément se trouve une seule fois dans le tableau. Algorithme : Élément. Var I : entier : entiers X tableau (1 .. 30) de réels n : réel (« élément recherché) Début Écrire (« Merci de donner l'élément que vous recherchez ») ; Lire (n) ; Pour i allant de 1 à 30 Faire Lire (« Entrez les éléments du tableau », X(i) ; Si (X(i)) = n Alors Écrire (« La position de n est », i) ; Fin Si; Fin Pour Fin. OU Début Pour i allant de 1 à 30 Faire Lire (« Entrez les éléments du tableau », X(i) ; Fin Pour Lire (« Quel est l'élément recherché ? », n) ; Pour i allant de 1 à 30 Si X(i) = n Alors écrire (« L'élément se trouve », i) ; Fin Si Fin. Exercice : Faire la même chose avec une matrice de 30 lignes et 20 colonnes. Algorithme : Élément. Var I : entier : entiers X tableau (1 .. 30, 1 .. 20) de réels n : réel (« élément recherché) Début Écrire (« Merci de donner l'élément que vous recherchez ») ; Lire (n) ; Pour i allant de 1 à 30 Faire Pour j allant de 1 à 20 faire Lire (« Entrez les éléments du tableau », X(i, j) ; Si (X(i, j)) = n Alors Écrire (« La position de n est », i, j) ; Fin Si; Fin Pour Fin Pour Fin. Exercice : Faire l'exercice Min Man précédent pour une matrice.