Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ALGORITHMIQUE II Hajar LAZAR Département d’Informatique Faculté des Sciencede S

ALGORITHMIQUE II Hajar LAZAR Département d’Informatique Faculté des Sciencede Semlalia –Marrakech- 1 PLAN DUCOURS 2 RAPPELS : NOT A TIONS ALGORITHMIQUES T ABLEAUX A PLUSIEURS DIMENSION FONCTIONS ET PROCEDURES RECURSIVITE ALGORITHMES ITERA TIFS DE TRIS COMPLEXITE ET PREUVE D’ ALGORITHMES STRUCTURES /ENREGISTREMENTS FICHIERS Algorithme Un algorithme, traduit dans un langage compréhensible par l’ordinateur (ou langage de programmation, C par ex), donne un programme, qui peut ensuite être exécuté, pour effectuer le traitement souhaité. Notations algorithmiques 3 2 Notations algorithmiques Structure d’un algorithme Un algorithme doit être lisible et compréhensible par plusieurs personnes. Algorithme : Nom d’Algorithme Données : Les entrées de l’algorithme Résultats : Les sorties de l’algorithme Déclarations : Variables, constantes… Début Ensemble d’instructions ; Fin 4 Notations algorithmiques 5 Une variable possède: - unnom - une valeur - untype (la valeur d’une variable peut changer au cours de l’exécution) Déclaration : <variable> : <type> Une expression, pour un type, est soit une constante, soit une variable, soit constituée à l’aide de constantes, de variables, de parenthèses et desopérateurs Exemple Variable A, B : entier d : réel Notations algorithmiques Un type est un ensemble de valeurs sur lesquelles on définit des opérations. • Types de base: ✓Entier : Opérateurs arithmétiques +, -, *, div, mod ✓Réel : Opérateurs arithmétiques +, -, *, / ✓Booléen : Opérateurs logiques et, ou, non ✓Caractère : constante (lettre imprimable) entre apostrophe. - Les opérateurs relationnels permettant de faire des comparaisons: <, , =, >, , Le Résultat de la comparaison est une valeur booléenne. 6 Notations algorithmiques 7 Entrée\Sortie Un algorithme peut avoir des interactions avec l’utilisateur et communiquer avec lui dans les deux sens, les sorties sont des envois de messages a l'utilisateur, les entrées sont des informations fournies par l'utilisateur. Il peut demander à l’utilisateur de saisir une information afin de la stocker dans une variable et peut afficher un résultat (du texte ou le contenu d’une variable) Notations algorithmiques 8 Instruction d'écriture (Sortie) Elle permet la restitution de résultats sur le périphérique de sortie (en général l'écran) Syntaxe : écrire(liste d'expressions) l'affichage des valeurs des Cette instruction réalise simplement expressions décrites dans la liste. Ces instructions peuvent être simplement des variables ayant des valeurs ou même des nombres ou des commentaires écrits sous forme de chaînes de caractères. Exemple : écrire(x, y+2, "bonjour") Notations algorithmiques 9 Instruction lecture (Entrée) L'instruction de prise de données sur le périphérique d'entrée (en général le clavier) Syntaxe : lire(liste de variables) L'exécution de cette instruction consiste à affecter une valeur à la variable en prenant cette valeur sur le périphérique d'entrée Exemple : Lire(x, y,A) Notations algorithmiques 10  Exemple Cet algorithme demande a l'utilisateur de saisir une valeur numérique, ensuite il affiche la valeur saisie, puis la même valeur incrémentée de 1. Algorithme : Affichage incrément variables : a, b : entier DEBUT écrire("Saisissez une valeur numérique") lire(a) b a + 1 écrire("Vous avez saisi la valeur ", a, ". ") écrire(a, "+ 1 = ", b) FIN Notations algorithmiques 11  La structure Si L’instruction si alors sinon permet de conditionner l’exécution d’un algorithme à la valeur d’une expression booléenne. Syntaxe : si <expression booléenne> alors <suite d’instructions exécutées si l’expression est vrai> sinon <suite d’instructions exécutées si l’expression est fausse> finsi La deuxième partie de l’instruction est optionnelle, on peut avoir : si <expression booléenne> alors <suite d’instructions exécutées si l’expression est vrai> finsi Notations algorithmiques 12  Structure Si Exemple Algorithme : ValeurAbsolue Données : La valeur à calculer Résultat : La valeur Absolue début si valeur ≥ 0 alors valeurabsolue ←valeur sinon valeurabsolue ← valeur * -1 finsi fin Notations algorithmiques 13  Structure de choix multiple Lorsque l’on doit comparer une même variable avec plusieurs valeurs, comme par exemple : si abréviation = "M" alors écrire( "Monsieur" ) Sinon si abréviation = "Mme" alors écrire("Madame") sinon si abréviation = "Mlle" alors écrire( "Mademoiselle" ) sinon écrire( "Monsieur, Madame " ) fsi fsi fsi On peut remplacer cette suite de si par l’instruction Selon Notations algorithmiques 14  Structure de choix multiple Syntaxe selon <identificateur : V> faire V1 : instructions 1 V2 : instructions 2 … Vn : instructions n [autres: instructions] finSelon V1,. . . ,Vn sont des constantes de type scalaire (entier, réel, caractère …) instructions i est exécutée si V = Vi (on quitte ensuite le selon) instruction autre est exécutée si quelque soit i, V ≠Vi Notations algorithmiques 15  Structure de choix multiple Exemple selon abréviation faire "M" : écrire( " Monsieur " ) "Mme" : écrire( " Madame " ) "Mlle" : écrire( " Mademoiselle " ) autres: écrire( " Monsieur, Madame " ) finSelon Notations algorithmiques 16  Un algorithme peut répéter le même traitement plusieurs fois, avec éventuellement quelques variantes. Dans certain cas, Il est impossible de savoir à l'avance combien de fois la même instruction doit être décrite. Utilisation des instructions en boucle qui répètent plusieurs fois une même instruction. Deux formes existent : la première, si le nombre de répétitions est connu avant l'exécution de l'instruction de répétition ( Pour ), la seconde s'il n'est pas connu ( Tant que et répéter… jusqu’à). L'exécution de la liste des instructions se nomme itération. Structure itératives Notations algorithmiques 17 Répétition inconditionnelle Il est fréquent que le nombre de répétitions soit connu à l'avance, et que l'on ait besoin d'utiliser le numéro de l'itération afin d'effectuer des calculs ou des tests. Syntaxe de Pour : pour <variable> := <initiale> à <final> faire action Fpour La variable prend successivement toutes les valeurs entières entre valeur initiale et valeur finale. Pour chaque valeur, la liste des instructions est exécutée. Où initiale et finale sont des expressions de même type que celui de la variable contrôlant la boucle, le type peut être entier, caractère ou énuméré) Notations algorithmiques 18 • La valeur utilisée pour énumérer les itérations est appelée valeur d'itération, indice d'itération ou compteur. L'incrémentation par 1 de la variable est implicite. Remarque: la boucle pour affecte la valeur de initiale à variable et compare cette valeur à celle de finale avant d’exécuter action. Notations algorithmiques 19 Exemple: calcul de 1+2+…+n (n entier1 fixé) Programme somme_des_n_premiersT ermes // partie déclaration n : entier; s : entier; i : entier; (ou n, i, s : entier) Début // Lecture des données Écrire (" n = " ); lire(n); // calcul de la somme s:= 0; pour i := 1 à n faire s := s + i; fpour; // affichage du résultat écrire("1+ 2 + … + n = ", s); fin Notations algorithmiques 20 Répétition conditionnelle Dans beaucoup de cas, on souhaite répéter une instruction tant qu'une certaine condition est remplie, alors qu'il est à priori impossible de savoir à l'avance au bout de combien d'itérations cette condition cessera d'être satisfaite. Dans ce cas, on a deux possibilités : la boucle Tant que la boucle Répéter jusqu'à Notations algorithmiques 21 Boucle Tant que Syntaxe : tant que condition faire liste d'instructions FinTantQue Cette instruction a une condition de poursuite dont la valeur est de type booléen et une liste d'instructions qui est répétée si la valeur de la condition de poursuite est vraie : la liste d'instructions est répétée autant de fois que la condition de poursuite a la valeur est vraie. Etant donné que la condition est évaluée avant l'exécution des instructions à répéter, il est possible que celles-ci ne soient jamais exécutées. Il faut que la liste des instructions ait une incidence sur la condition afin qu'elle puisse être évaluée à faux et que la boucle se termine (Il faut toujours s'assurer que la condition devient fausse au bout d'un temps fini.) 39 Notations algorithmiques 22 Boucle Tant que Contrôle de saisie d'une lettre alphabétique jusqu’à ce que le caractère entré soit valable … Variable C : caractère Debut Écrire (" Entrez une lettre majuscule "); Lire (C); TantQue ((C < 'A‘) ou (C > 'Z')) faire Ecrire ("Saisie erronée. Recommencez"); Lire (C); FinTantQue Ecrire ("La saisie est valable "); Fin Notations algorithmiques 23 Boucle Répéter jusqu'à Syntaxe : Répéter liste d'instructions jusqu'à condition La séquence d'instructions est exécutée au moins une fois et jusqu'à ce que l'expression soit vraie. Dès que la condition est vrai, la répétitivité s'arrête. Notations algorithmiques 24 Boucle Répéter jusqu'à Exemple Algorithme : saisirLargeurRectangle Variable : largeur : entier début répéter écrire ("indiquez la largeur du rectangle :") lire(largeur) si largeur < 1 alors écrire ("erreur : indiquez une valeur > 0") finSi jusqu'à largeur >=1 fin Notations algorithmiques 25 Les boucles Tant que et Répéter jusqu’à • Différences entre les boucles TantQue et Répéter jusqu’à : - La séquence d'instructions est exécutée au moins une fois dans la boucle Répéter jusqu’à , alors qu'elle peut ne pas être exécutée dans le cas du Tant que. - Dans les deux cas, la séquence d'instructions est exécutée si la condition est vraie. - Dans les deux cas, la séquence d'instructions doit nécessairement faire évoluer la condition, faute de quoi on obtient une boucle infinie. Notations algorithmiques uploads/Ingenierie_Lourd/ cours-complet-algorithmique-ii.pdf