Algorithmique - Notes de Cours PDF

Algorithmique Première Année DUT ID-RCIA EST El Kelaa des Sraghnas Pr. EL MASSARI Hakim Année Universitaire: 2024/2025 Algorithmique [email protected] Algorithmique: Outils de base...

Algorithmique Première Année DUT ID-RCIA EST El Kelaa des Sraghnas Pr. EL MASSARI Hakim Année Universitaire: 2024/2025 Algorithmique [email protected] Algorithmique: Outils de base Outils de base d’un algorithme (Suite) Un algorithme informatique se ramène toujours à la combinaison de 4 briques de base :  Affectation de variables  Lecture / écriture  Les tests  Les boucles Algorithmique 2 Algorithmique: Outils de base Tests: instructions conditionnelles  Les instructions d’affectation, de lecture et d’écriture sont des instructions séquentielles.  Les tests sont des instructions conditionnelles qui permettentt d’exécuter ou non un bloc d’instructions selon le résultat d’un test (choix binaire).  Les instructions conditionnelles n'exécutent une instruction ou une séquence d'instructions que si une condition est vérifiée. Algorithmique 3 Algorithmique: Outils de base Tests: instructions conditionnelles Si condition alors instruction ou suite d'instructions 1 Conditionnelle Sinon complète instruction ou suite d'instructions 2 (Si… alors… Sinon) FinSi  Interprétation: Si la condition est vérifiée, alors on exécute (instruction ou suite d’instructions 1), sinon on exécute (instruction ou suite d’instructions 2). Algorithmique 4  Algorithmique: Outils de base Tests: instructions conditionnelles Si condition alors Conditionnelle instruction ou suite d'instructions 1 incomplète FinSi (Si… alors)  Interprétation: Si la condition est vérifiée, alors on exécute (instruction ou suite d'instructions 1), sinon on ne fait rien. Algorithmique 5 Algorithmique: Outils de base Tests: instructions conditionnelles  Exemple : (Si…Sinon…FinSi) Algorithme ValeurAbsolue Variable x : réel Début Ecrire (" Entrez un réel : ") Lire (x) Si x < 0 alors Ecrire ("la valeur absolue de ", x, "est:",-x) Sinon Ecrire ("la valeur absolue de ", x, "est:",x) FinSi Fin Algorithmique 6 Algorithmique: Outils de base Tests: instructions conditionnelles  Exemple : (Si…FinSi) Algorithme ValeurAbsolue Variables x, y : réel Début Ecrire (" Entrez un réel : " ) Lire (x) y← x Si x < 0 alors y ← -x Finsi Ecrire ("la valeur absolue de ", x, "est:", y) Fin Algorithmique 7 Algorithmique: Outils de base Tests: instructions conditionnelles  Exercice d’application: Écrire un algorithme qui demande un nombre entier à l'utilisateur, puis qui teste et affiche s'il est divisible par 7 ou non. Algorithmique 8 Algorithmique: Outils de base Tests: instructions conditionnelles  Exercice d’application: Corrigé Algorithme divisiblePar7 Variable n : entier Début Ecrire ("Entrez un entier : ") Lire (n) Si (n mod 7=0) alors Ecrire (n," est divisible par 7") Sinon Ecrire (n," n'est pas divisible par 7") FinSi Fin Algorithmique 9 Algorithmique: Outils de base Tests: instructions conditionnelles La condition:  Elle ne peut être que vraie ou fausse.  Une condition peut être une expression booléenne simple ou une suite composée d’expressions booléennes.  Une condition composée est une condition formée de plusieurs conditions simples reliées par des opérateurs logiques: ET, OU, OU exclusif (XOR) et NON. Algorithmique 10 Algorithmique: Outils de base Tests: instructions conditionnelles La condition (suite): Exemple: 1. x compris entre 2 et 6 : (x >= 2) ET (x < =6) 2. n divisible par 3 ou par 2 : (n mod 3=0) OU (n mod 2=0) Algorithmique 11 Algorithmique: Outils de base Tests: instructions conditionnelles Tests imbriqués Si condition1 alors Si condition2 alors Les tests peuvent avoir instructionsA Sinon un degré quelconque instructionsB d'imbrications. Finsi Sinon Si condition3 alors instructionsC Finsi Finsi Algorithmique 12  Algorithmique: Outils de base Tests: instructions conditionnelles Algorithme TesterPosNegNull Variable n : réel => Tests imbriqués Début Ecrire ("entrez un nombre : ") Exemple1 Lire (n) Si n < 0 alors Tester si un nombre est Ecrire ("Ce nombre est négatif") Sinon positif, négatif ou nul. Si n = 0 alors Ecrire ("Ce nombre est nul") Sinon Ecrire ("Ce nombre est positif") Finsi Finsi Fin Algorithmique 13  Algorithmique: Outils de base Tests: instructions conditionnelles Exercice d’application Le prix de disques compacts (CDs) dans un espace de vente varie selon le nombre à acheter: 5 DH par unité si le nombre de CDs à acheter est inférieur à 10; 4 DH par unité si le nombre de CDS à acheter est compris entre 10 et 20; 3 DH par unité si le nombre de CDs à acheter est au-delà de 20. Écrivez un algorithme qui demande à l’utilisateur le nombre de CDs à acheter, qui calcule et affiche le prix à payer. Algorithmique 14  Algorithmique: Outils de base Algorithme Prix_CDs Tests: instructions Variables unites : entier conditionnelles prix : réel Début Ecrire ("Nombre d’unités : ") Exercice d’application Lire (unites) Si unites < 10 alors Corrigé prix ← unites*5 Sinon Si unites < 20 alors prix ← unites*4 Sinon prix ← unites*3 Finsi Finsi Ecrire (“Le prix à payer est : ”, prix) Fin Algorithmique 15 Algorithmique: Outils de base Tests: instructions conditionnelles  Instruction « cas » Lorsqu' on doit comparer une même variable avec plusieurs valeurs on utilise l’instruction cas: Si a=1 alors instruction1 Sinon si a=2 alors On peut remplacer cette instruction2 suite de si par l’instruction Sinon si a=4 alors instruction4 cas Sinon... Finsi Algorithmique 16 Algorithmique: Outils de base Tests: instructions conditionnelles Instruction « cas » Sa syntaxe en pseudo-code est :  v1,... ,vn sont des constantes cas où v vaut de type scalaire (entier, naturel, v1 : action 1 énuméré, ou caractère). v2 : action 2  Action i est exécutée si v = vi... (on quitte ensuite l’instruction vn : action n cas). autre : action autre fincas  Action autre est exécutée si quelque soit i, v ≠ vi Algorithmique 17 Algorithmique: Outils de base Tests: instructions conditionnelles Instruction « cas »: Exercice d’application Ecrire un algorithme calculatrice permettant la saisie du premier entier (a) de l'opération ( + ou – ou * ou / : sont des caractères) et du deuxième entier (b) et qui affiche le résultat. Algorithmique 18 Algorithmique: Outils de base ALGORITHME calculatrice Variables a, b : ENTIER; op : CARACTERE DEBUT ECRIRE (" saisissez le premier entier ") LIRE (a) ECRIRE (" saisissez l’opération ") LIRE (op) ECRIRE (" saisissez le deuxième entier") LIRE (b) Cas où op vaut ‘+’ : ECRIRE ("la somme de ",a, "et de ",b, "est égale",a+b) ‘-‘ : ECRIRE ("la soustraction de ",a, "et de ",b, "est égale", a-b) ‘*’ : ECRIRE ("le produit de ",a, "et de ",b, "est égale",a*b) ‘/’ : Si (b= 0) Alors ECRIRE (" division impossible ") Sinon ECRIRE ("la division de ",a, "par ",b, "est égale", a/b) FinSi autre: ECRIRE((" Opération invalide ") FinCas FIN Algorithmique 19 Algorithmique: Outils de base Outils de base d’un algorithme (Suite) Un algorithme informatique se ramène toujours à la combinaison de 4 briques de base :  Affectation de variables  Lecture / écriture  Les tests  Les boucles Algorithmique 20 Algorithmique: Outils de base Les boucles: Instructions itératives  Les boucles servent à répéter l'exécution d'un groupe d'instructions un certain nombre de fois.  On distingue trois sortes de boucles: 1. Les boucles tant que : on y répète des instructions tant qu'une certaine condition est réalisée. 2. Les boucles répéter…jusqu'à : on y répète des instructions jusqu'à ce qu'une certaine condition soit réalisée. 3. Les boucles pour ou avec compteur : on y répète des instructions en faisant évoluer un compteur (variable particulière) entre une valeur initiale et une valeur finale. Algorithmique 21 Algorithmique: Outils de base La boucle « Tant que » TantQue (condition) faire instructions (corps de la boucle) FinTantQue  La condition est évaluée avant chaque itération.  Si la condition est vraie, on exécute les instructions, puis, on retourne tester la condition. Si elle est encore vraie, on répète l'exécution, …  Si la condition est fausse, on sort de la boucle et on exécute l'instruction qui est après FinTantQue. Algorithmique 22 Algorithmique: Outils de base La boucle « Tant que » Remarque:  Le nombre d'itérations dans une boucle TantQue n'est pas connu au moment d'entrée dans la boucle. Il dépend de l'évolution de la valeur de la condition.  Une des instructions du corps de la boucle doit absolument changer la valeur de la condition de vrai à faux (après un certain nombre d'itérations), sinon le programme va tourner indéfiniment. Algorithmique 23 Algorithmique: Outils de base La boucle « Tant que » Attention au boucle infinie: Algorithmique 24  Algorithmique: Outils de base La boucle « Tant que » Exemple: Algorithme Somme_inferieur_a_100 Variables som, n : entier Un algorithme qui détermine Debut le premier nombre entier N n←1 tel que la somme de 1 à N som ← 0 dépasse strictement 100. TantQue (som = à finale pour un Pas négatif), instructions seront exécutées. Algorithmique 31 Algorithmique: Outils de base La boucle « Pour » Déroulement des boucles Pour (suite)  Ensuite, la valeur du compteur est incrémentée de la valeur du Pas si pas est positif (ou décrémenté si pas est négatif).  On recommence l'étape 2 : La comparaison entre compteur et finale est de nouveau effectuée, et ainsi de suite … Algorithmique 32 Algorithmique: Outils de base La boucle « Pour » Exemple 1: Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul Variables x, puiss : réel n, i : entier Debut Ecrire (" Entrez respectivement les valeurs de x et n ") Lire (x, n) puiss ← 1 Pour i ← 1 à n faire puiss← puiss*x FinPour Ecrire (x, " à la puissance ", n, " est égal à ", puiss) Fin Algorithmique 33 Algorithmique: Outils de base La boucle « Pour » Exemple 2: Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul (forme 2 avec un pas négatif) Variables x, puiss : réel n, i : entier Début Ecrire (" Entrez respectivement les valeurs de x et n ") Lire (x, n) puiss ← 1 Pour i ← n à 1 pas -1 faire puiss← puiss*x FinPour Ecrire (x, " à la puissance ", n, " est égal à ", puiss) Fin Algorithmique 34 Algorithmique: Outils de base La boucle « Pour » Remarque : Il faut éviter de modifier la valeur du compteur à l'intérieur de la boucle. En effet, une telle action : 1. Perturbe le nombre d'itérations prévu par la boucle Pour. 2. Rend difficile la lecture de l'algorithme. 3. Présente le risque d'aboutir à une boucle infinie. Exemple : Pour i ← 0 à 5 faire i←i-1 Ecrire (“ i=”, i) Finpour Algorithmique 35 Algorithmique: Outils de base La boucle Pour vs. TantQue La boucle Pour est un cas particulier de Tant Que (le cas où le nombre d'itérations est connu et fixé). Pour Compteur ← Initiale à Finale pas ValeurDuPas faire instructions FinPour peut être remplacé par : (un cas d'un pas positif) ( ) Algorithmique 36 Algorithmique: Outils de base La boucle Pour vs. TantQue Exemple de la puissance (forme avec TantQue) Variables x, puiss : réel n, i : entier Debut Ecrire (" Entrez respectivement les valeurs de x et n ") Lire (x, n) puiss ← 1 i←1 TantQue (i