<style> .slides h1, .slides h2, .slides h3, .slides h4, .slides h5, .slides h6, h1, h2, h3, h4, h5, h6{ color: #d35400; } .slides { font-size: 3.3rem; box-shadow: 0 0 80px #d35400; } .slides strong, .slides em{ color: #FF926B; } .slides pre code { width: auto; max-height: initial; } .slides code{ color: #FFBD96; font-style: italic; } .slides ul li { margin: 0.5em 0; } .slides .graph pre { height: 700px; width: 400px; } .slides .flex, .slides .table-flex { display: flex; justify-content: center; align-items: center; } .slides .flex h1 { width: 50%; } .slides .table-flex { flex-wrap: wrap; } .slides .table-flex h1 { width: 100%; } .slides .table-flex table { width: 40%; } .slides .none { display: none; } /* Dark theme book */ html, body, .ui-content { background-color: #333; color: #ddd; } .markdown-body h1, .markdown-body h2, .markdown-body h3, .markdown-body h4, .markdown-body h5, .markdown-body h6 { color: #ddd; } .markdown-body h1, .markdown-body h2 { border-bottom-color: #ffffff69; } .markdown-body h1 .octicon-link, .markdown-body h2 .octicon-link, .markdown-body h3 .octicon-link, .markdown-body h4 .octicon-link, .markdown-body h5 .octicon-link, .markdown-body h6 .octicon-link { color: #fff; } .markdown-body img { background-color: transparent; } .ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a { color: white; border-left: 2px solid white; } .expand-toggle:hover, .expand-toggle:focus, .back-to-top:hover, .back-to-top:focus, .go-to-bottom:hover, .go-to-bottom:focus { color: white; } .ui-toc-dropdown { background-color: #333; } .ui-toc-label.btn { background-color: #191919; color: white; } .ui-toc-dropdown .nav>li>a:focus, .ui-toc-dropdown .nav>li>a:hover { color: white; border-left: 1px solid white; } .markdown-body blockquote { color: #bcbcbc; } .markdown-body table tr { background-color: #5f5f5f; } .markdown-body table tr:nth-child(2n) { background-color: #4f4f4f; } .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(230, 230, 230, 0.36); } a, .open-files-container li.selected a { color: #5EB7E0; } </style> # Algorithmique --- # Objectif et plan du cours - Objectif: - Apprendre les concepts de base de l'algorithmique et de la programmation - Etre capable de mettre en œuvre ces concepts pour analyser des problèmes simples et écrire les programmes correspondants - Plan: - Généralités (matériel d’un ordinateur, systèmes d’exploitation, langages de programmation, …) - Algorithmique (affectation, instructions conditionnelles, instructions itératives, fonctions, procédures, …) --- # Informatique ? - Techniques du traitement automatique de l’information au moyen des ordinateurs - Eléments d’un système informatique | | |:-----------------------------------------------:| | Applications (Word, Excel, Jeux, Maple, etc.) | | Langages (Java,C/C++, Fortran,etc.) | | Système d’exploitation(DOS,Windows, Unix, etc.) | | Matériel (PC, Macintosh, station SUN, etc.) | --- # Matériel: Principaux éléments d’un PC - Unité centrale (le boîtier) - Processeur ou CPU (Central Processing Unit) - Mémoire centrale - Disque dur, lecteur disquettes, lecteur CD-ROM - Cartes spécialisées (cartes vidéo, réseau, ...) - Interfaces d'entrée-sortie (Ports série/parallèle, …) ---- - Périphériques - Moniteur (l'écran), clavier, souris - Modem, imprimante, scanner, … --- # Qu’est ce qu’un système d’exploitation? - Ensemble de programmes qui gère le matériel et contrôle les applications - Gestion des périphériques (affichage à l'écran, lecture du clavier, pilotage d’une imprimante, …) - Gestion des utilisateurs et de leurs données (comptes, partage des ressources, gestion des fichiers et répertoires, …) - Interface avec l’utilisateur (textuelle ou graphique): Interprétation des commandes - Contrôle des programmes (découpage en taches, partage du temps processeur, …) --- # Langages informatiques - Un langage informatique est un outil permettant de donner des ordres (instructions) à la machine - A chaque instruction correspond une action du processeur - Intérêt : écrire des programmes (suite consécutive d’instructions) destinés à effectuer une tâche donnée - Exemple: un programme de gestion de comptes bancaires - Contrainte: être compréhensible par la machine --- # Langage machine - Langage **binaire**: l’information est exprimée et manipulée sous forme d’une suite de bits - Un **bit** (*binary digit*) = 0 ou 1 (2 états électrique) - Une combinaison de 8 bits = 1 **Octet** -> 2⁸ = 256 possibilités qui permettent de coder tous les caractères alphabétiques, numériques, et symboles tels que ?, *, &, … - Le code **ASCII** (*American Standard Code for Information Interchange*) donne les correspondances entre les caractères alphanumériques et leurs représentation binaire, Ex. A=01000001, ?=00111111 - Les opérations logiques et arithmétiques de base (addition, multiplication, … ) sont effectuées en binaire --- # L'assembleur - **Problème**: le langage machine est difficile à comprendre par l'humain - **Idée**: trouver un langage compréhensible par l'homme qui sera ensuite converti en langage machine - Assembleur (1er langage): exprimer les instructions élémentaires de façon symbolique ``` ADD A,4 traducteur LOAD B ----------------> Langage Machine MOV A, OUT ``` - **+**: déjà plus accessible que le langage machine - **-**: dépend du type de la machine (n’est pas ***portable***) - **-**: pas assez efficace pour développer des applications complexes ### ➡ Apparition des langages évolués --- # Langages haut niveau - Intérêts multiples pour le haut niveau: - proche du langage humain «anglais» (compréhensible) - permet une plus grande portabilité (indépendant du matériel) - Manipulation de données et d’expressions complexes (réels, objets, a*b/c, …) - Nécessité d’un traducteur (compilateur/interpréteur), exécution plus ou moins lente selon le traducteur ```graphviz digraph G{ /* set direction of graph to be left-->right */ rankdir="LR"; splines=ortho; /* make boxes instead of ellipses */ node [shape=box]; /* should enforce nodes to be horizontally aligned */ /* is not working, though... */ rank=same; T [label="Code source en langage évolué", fontsize=24, margin="0.5,0.5"] // node T P [label="Langage Machine", fontsize=24, margin="0.5,0.5"] // node P T->P [label="Compilateur ou interpréteur", fontsize=24] // edge T->P } ``` --- # Compilateur/interpréteur ---- ### Compilateur: traduire le programme entier une fois pour toutes ```graphviz digraph dfd{ /* set direction of graph to be left-->right */ rankdir="LR"; /* make boxes instead of ellipses */ node [shape=record]; /* should enforce nodes to be horizontally aligned */ /* is not working, though... */ rank=same; source [label="<f0>main.go|fichier source", fontsize=20] exe [label="<f1>main|fichier exécutable", fontsize=20] P [label="", shape=plaintext] source:f0->exe:f1 [label="Compilateur", fontsize=20] exe:f1->P [label="Exécution", fontsize=20] } ``` - **+** plus rapide à l’exécution - **+** sécurité du code source - **-** il faut recompiler à chaque modification ---- ### Interpréteur: traduire au fur et à mesure les instructions du programme à chaque exécution ```graphviz digraph dfd{ rankdir="LR"; node [shape=record]; rank=same; source [label="<f0>main.bas|fichier source(Basic)", fontsize=20] P [label="", shape=plaintext] source:f0->P [label="Interprétation+exécution", fontsize=20] } ``` - **+** exécution instantanée appréciable pour les débutants - **-** exécution lente par rapport à la compilation --- # Langages de programmation - Deux types de langages - Langages procéduraux - Langages orientés objets - Exemples de langages: - Fortran, Cobol, Pascal, C, … - C++, Java, … - Choix d’un langage? --- <!-- .element: class="graph flex" --> # Etapes de réalisation d’un programme ```graphviz digraph G{ node [shape=record]; nodesep=1; rank=same; a1 [label="Enoncé du problème"] a2 [label="Cahier des charges"] a3 [label="Algorithme"] a4 [label="Programme source"] a5 [label="Programme exécutable"] a6 [label="Version finale et résultats"] a1->a2 [label="Spécification", len=f] a2->a3 [label="Analyse"] a3->a4 [label="Traduction en langage"] a4->a5 [label="Compilation"] a5->a6 [label="Tests et modifications"] } ``` ---- ## La réalisation de programmes passe par l'écriture d'algorithmes => D'où l'intérêt de l'Algorithmique. --- # Algorithmique - Le terme **algorithme** vient du nom du mathématicien arabe **Al-Khawarizmi** (820 après J.C.) - Un algorithme est une description complète et détaillée des actions à effectuer et de leur séquencement pour arriver à un résultat donné - *Intérêt*: séparation analyse/codage (pas de préoccupation de syntaxe) - *Qualités*: **exact** (fournit le résultat souhaité), **efficace** (temps d’exécution, mémoire occupée), **clair** (compréhensible), **général** (traite le plus grand nombre de cas possibles), ... - ***L’algorithmique*** désigne aussi la discipline qui étudie les algorithmes et leurs applications en Informatique - Une bonne connaissance de l’algorithmique permet d’écrire des algorithmes exacts et efficaces --- # Représentation d'un algorithme Historiquement, deux façons pour représenter un algorithme: - **L’Organigramme**: représentation graphique avec des symboles (carrés, losanges, etc.) - offre une vue d’ensemble de l’algorithme - représentation quasiment abandonnée aujourd’hui - **Le pseudo-code**: représentation textuelle avec une série de conventions ressemblant à un langage de programmation (sans les problèmes de syntaxe) - plus pratique pour écrire un algorithme - représentation largement utilisée --- # Algorithmique ## Notion et instructions de base --- ## Notion de variable - Dans les langages de programmation une *variable* sert à *stocker* la valeur d'une donnée - Une *variable* désigne en fait un *emplacement mémoire* dont le contenu peut changer au cours d'un programme (d'où le nom *variable*) - **Règle**: Les variables doivent être déclarées avant d'être utilisées, elle doivent être caractérisées par : - un nom (*identificateur*) - un *type* (entier, réel, caractère, chaîne de caractères, ...) --- ## Choix des identificateurs *Le choix des noms de variables est soumis à quelques règles qui varient selon le langage, mais en général:* - Un nom doit commencer par une **lettre alphabétique** : - exemple valide: *a1* exemple => invalide: *1a*. - doit être constitué *uniquement* de lettres, de chiffres et du soulignement (Eviter les caractères de ponctuation et les espaces) valides: - *cdi2022, cdi_2022* => invalides: *cdi 2022, cdi-2022, cdi;2022*. - doit être différent des mots réservés du langage (par exemple en Java: *int, float, else, switch, case, default, for, main, return, ...*) - La longueur du nom doit être *inférieure à la taille maximale* spécifiée par le langage utilisé ---- ## Choix des identificateurs - **Conseil**: pour la *lisibilité* du code, choisir des *noms significatifs* qui décrivent les données manipulées - exemples: *totalVentes2022, prix_ttc, prix_ht*. - **Remarque**: en pseudo-code algorithmique, on va *respecter les règles citées*, même si on est libre dans la syntaxe --- ## Types des variables Le type d'une variable détermine l'ensemble des valeurs qu'elle peut prendre, les types offerts par la plupart des langages sont: - *Type numérique* (entier ou réel) - *Byte* (codé sur 1 octet): de 0 à 255 - *Entier court* (codé sur 2 octets) : -32 768 à 32 767 - *Entier long* (codé sur 4 ou 8 octets) - *Réel simple précision* (codé sur 4 octets) - *Réel double précision* (codé sur 8 octets) ---- - *Type logique* ou *booléen*: deux valeurs VRAI ou FAUX - *Type caractère*: lettres majuscules, minuscules, chiffres, symboles,... - exemples: `'A', 'a', '1', '?'`,... - *Type chaîne de caractères*: suites de caractères, - exemples: `"Nom, Prénom", "code postal: 1000"`,... --- # Déclaration des variables - **Rappel**: toutes variables utilisées dans un programme doit avoir fait l'objet d'une déclaration préalable - En pseudo-code, on va adopter la forme suivante pour la déclaration de variables `Variables liste d’identificateurs : type` - Exemple: ``` Variables i, j, k : entier x, y : réel ok: booléen chl, ch2 : chaîne de caractères ``` - **Remarque**: pour le type *numérique* on va se limiter aux entiers et réels sans considérer les sous types. ---- # L'instruction d'affectation **L'affectation** consiste à **attribuer une valeur** à une variable (ça consiste en fait, à remplir où à modifier le contenu d’une zone mémoire) - En pseudo-code, l'affectation se note avec le signe *←*. - `Var ← e: attribue la valeur de e à la variable Var`. - *e* peut être une valeur, une autre variable ou une expression. - *Var* et *e* doivent être de *même type* ou de *types compatibles*. - *l'affectation* ne modifie que ce qui est à *gauche* de la flèche. ---- - *Ex valides*: `i ← 1` `x ← 10.3` `ch2 ← ch1` `j ← i` `ok ← FAUX` `x ← 4` `k ← i+j` `ch1 ← "SMI"` `x ← j` (voir la déclaration des variables dans le transparent précédent) - *non valides*: - `i ← 10.3` - `ok ← "SMI"` ---- # Quelques remarques - Beaucoup de langages de programmation (C/C++, Java,...) utilisent le *signe égal =* pour l'affectation et pas *←*. Attention aux confusions: - l'affectation n'est pas *commutative* : *a = b* est différente de *b = a*. - l'affectation est différente d'une équation mathématique : - *a = a + 1* => a un sens en langage de programmation - *a + 1 = 2* => n'est pas possible en langage de programmation et n'est pas équivalente à *a = 1*. - Certains langages donnent des valeurs par défaut aux variables déclarées. Pour éviter tout problème il est préférable *d'initialiser les variables* déclarées. --- # Exercices simples sur l'affectation ---- ## Exercice 1 Donnez les valeurs des variables *a*, *b* et *c* après exécution des instructions suivantes ? ```javascript= Variables a, b, c: Entier Debut a ← 3 b ← 7 a ← b b ← a + 5 c ← a + b c ← b - a Fin ``` Note: a = 7 b = 12 c = 5 ---- ## Exercice 2 Donnez les valeurs des variables *a* et *b* après exécution des instructions suivantes ? ```javascript= Variables a, b : Entier Debut a ← 1 b ← 2 a ← b b ← a Fin ``` Les deux dernières instructions permettent-elles d’échanger les valeurs de *a* et *b* ? ---- ## Exercice 3 Ecrire un Algo permettant d'échanger les valeurs de deux variables *a* et *b*. ```javascript= Variables a, b, c : Entier Debut a ← 1 b ← 2 c ← a a ← b b ← c Fin ``` ```javascript= Variables a, b : Entier Debut a ← 1 b ← 2 b ← a + b a ← b - a b ← b - a Fin ``` ---- ## Résultat ### Exercice 1 ```javascript= a = 7 b = 12 c = 5 ``` ### Exercice 2 ```javascript= a = 2 b = 2 ``` --- # Expressions et opérateurs - Une *expression* peut être une valeur, une variable ou une opération constituée de variables reliées par des opérateurs - exemples: `1, b, a * 2, a + 3 * b - c`, ... - L'évaluation de l'expression fournit une valeur unique qui est le résultat de l'opération - Les *opérateurs* dépendent du type de l'opération, ils peuvent être : - des opérateurs arithmétiques: `+, -, *, /, % (modulo), ^ (puissance)`. - des opérateurs logiques: `NON`, `OU`, `ET`. - des opérateurs relationnels: `=`, `!=(<>)`, `<`, `>`, `<=`, `>=`. - des opérateurs sur les chaînes: `& (concaténation)`. - Une *expression* est évaluée de gauche à droite mais en tenant compte des *priorités*. ---- # Priorité des opérateurs - Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de priorité est le suivant (du *plus prioritaire au moins prioritaire*) : - `-` changement de signe - `^` élévation à la puissance - `* , /` multiplication, division - `%` modulo - `+, -` addition, soustraction - exemple: `2 + 3 * 7 vaut 23`. - En cas de besoin (ou de doute), on utilise les parenthèses pour indiquer les opérations à effectuer en priorité - exemple: `(2 + 3) * 7 vaut 35`. --- # Les instructions d'entrées-sorties ---- ## Lecture - Les instructions de *lecture et d'écriture* permettent à la machine de *communiquer* avec l'utilisateur - La *lecture* permet d'entrer des données à partir du clavier - En pseudo-code, on note: `lire(var)`. - la machine met la *valeur entrée au clavier* dans la zone mémoire nommée `var`. - **Remarque**: Le *programme s'arrête* lorsqu'il rencontre une *instruction Lire* et ne se poursuit qu'après la frappe d'une valeur au clavier et de la *touche Entrée*. ---- ## Ecriture - *L'écriture* permet d'afficher des résultats à l'écran (ou de les écrire dans un fichier) - En pseudo-code, on note: `ecrire(var)`. - la machine affiche le contenu de la zone mémoire `var`. - **Conseil**: Avant de *lire une variable*, il est fortement *conseillé d'écrire des messages* à l'écran, afin de prévenir l'utilisateur de ce qu'il doit frapper. ---- ## Exemple Ecrire un algorithme qui *demande* un nombre entier à l'utilisateur, puis qui *calcule* et *affiche* le *double* de ce nombre. ```javascript= Algorithme CalculDouble Variables a, b : entier Debut ecrire("Entrez un nombre ") lire(a) b ← 2 * a ecrire("le double de " & a & " est : " & b) Fin ``` ---- ## Exercice Ecrire un *algorithme* qui vous *demande* de saisir votre *nom* puis votre *prénom* et qui *affiche* ensuite votre *nom complet*. ---- ```javascript= Algorithme AffichageNomComplet Variables nom, prenom, nomComplet : chaîne de caractères Debut ecrire("entrez votre nom") lire(nom) ecrire("entrez votre prénom") lire(prenom) nomComplet ← nom & " " & prenom ecrire("Votre nom complet est : " & nomComplet) Fin ``` ---- ## Exercice Demander à l'utilisateur 2 nombres puis afficher - la somme - la différence - le produit - le quotient - le reste ---- ## Une solution ```javascript= Algorithme Calculatrice Variables nbr1, nbr2 : entier Debut ecrire("Entrez un premier nombre : ") lire(nbr1) ecrire("Entrez un second nombre : ") lire(nbr2) ecrire("La somme de " & nbr1 & " et de " & nbr2 & " est de " & (nbr1 + nbr2)) ecrire("La différence de " & nbr1 & " et de " & nbr2 & " est de " & (nbr1 - nbr2)) ecrire("Le produit de " & nbr1 & " et de " & nbr2 & " est de " & (nbr1 * nbr2)) ecrire("Le quotient de " & nbr1 & " et de " & nbr2 & " est de " & (nbr1 / nbr2)) ecrire("Le reste de " & nbr1 & " et de " & nbr2 & " est de " & (nbr1 % nbr2)) Fin ``` ---- ## Exercice Demander à l'utilisateur les éléments nécéssaires afin de calculer le volume d'une pièce et lui afficher le résultat. ---- ## Solution ```javascript= Algo Volume Variables largeur, longueur, hauteur : reel Debut ecrire("Entrez la largeur : ") lire(largeur) ecrire("Entrez la longueur : ") lire(longueur) ecrire("Entrez la hauteur : ") lire(hauteur) ecrire("le volume de la pièce est de : " & (longueur * largeur * hauteur) & " m3." ) Fin ``` --- # Tests: instructions conditionnelles ---- - **Les instructions conditionnelles** servent à n'exécuter une *instruction* ou une *séquence d'instructions* que *si* une *condition* est *vérifiée* - On utilisera la forme suivante: ``` Si (condition) alors instruction ou suite d'instructionsl Sinon instruction ou suite d'instructions2 FinSi ``` - - *la condition ne peut être que **vraie** ou **fausse***. - si la *condition est vraie*, se sont les instructions 1 qui seront exécutées - si la *condition est fausse*, se sont les instructions 2 qui seront exécutées - la condition peut être une *condition simple* ou une *condition composée* de plusieurs conditions ---- - La partie `Sinon` n'est *pas obligatoire*, quand elle n'existe pas et que la condition est fausse, *aucun traitement* n'est réalisé - On utilisera dans ce cas la *forme simplifiée* suivante: ``` Si (condition) alors instruction ou suite d'instructionsl Finsi ``` ---- ## Exemple (Si...Alors...Sinon) - Version 1 : ```javascript= Algorithme AffichageValeurAbsolue Variables x : reel Debut ecrire("Entrez un reel : ") 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 ``` ---- ## Exemple (Si...Alors) - Version 2 : ```javascript= Algorithme AffichageValeurAbsolue Variables x, y : reel Debut ecrire("Entrez un reel : ") lire(x) y ← x Si (x < 0) alors y ← -x Finsi ecrire("la valeur absolue de " & x & " est: " & y) Fin ``` ---- ## Exercice Ecrire un algorithme qui *demande* un *nombre entier* à l'utilisateur, puis qui *teste* et *affiche* s'il est *divisible par 3*. ---- ## Solution ```javascript= Algorithme DivsiblePar3 Variables n : entier Début ecrire("Entrez un entier : ") lire(n) Si (n % 3 = 0) alors ecrire(n & " est divisible par 3") Sinon ecrire(n & " n'est pas divisible par 3") Finsi Fin ``` --- <!-- .element: class="table-flex" --> # Tables de vérité | a | b | a *ET* b | |:----:|:----:|:------:| | vrai | vrai | vrai | | vrai | *faux* | *faux* | | *faux* | vrai | *faux* | | *faux* | *faux* | *faux* | | a | b | a *OU* b | |:----:|:----:|:------:| | vrai | vrai | vrai | | vrai | *faux* | vrai | | *faux* | vrai | vrai | | *faux* | *faux* | *faux* | | a | b | a *XOR* b | |:----:|:----:|:-------:| | vrai | vrai | *faux* | | vrai | *faux* | vrai | | *faux* | vrai | vrai | | *faux* | *faux* | *faux* | | a | NON a | |:----:|:-----:| | vrai | *faux* | | *faux* | vrai | ---- # Conditions composées - 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`. - Exemples : - *x* compris entre 2 et 6: `(x>2)ET(x<6)`. - *n* divisible par 3 ou par 2 : `(n % 3 = 0) OU (n % 2 = 0)`. - deux valeurs et deux seulement sont identiques parmi a, b et c : `(a=b) XOR (a=c) XOR (b=c)`. - L'évaluation d'une condition composée se fait selon des règles présentées généralement dans ce qu'on appelle tables de vérité --- # Tests imbriqués - Les tests peuvent avoir un degré quelconque d'imbrications ``` Si condition1 alors Si condition2 alors instructionsA Sinon instructionsB Finsi Sinon Si condition3 alors instructionsC Finsi Finsi ``` ---- ## Exemple - Version 1 #### Déterminer si un nombre est négatif, nul ou positif. ```javascript= Variables n : entier Debut ecrire("entrez un nombre : ") lire(n) Si (n < 0) alors ecrire("Ce nombre est négatif.") Sinon Si (n = 0) alors ecrire("Ce nombre est nul.") Sinon ecrire("Ce nombre est positif.") Finsi Finsi Fin ``` ---- ## Exemple - version 2 ```javascript= Variables n : entier Debut ecrire("entrez un nombre : ") lire(n) Si (n < 0) alors ecrire("Ce nombre est négatif.") Finsi Si (n = 0) alors ecrire("Ce nombre est nul.") Finsi Si (n > 0) alors ecrire("Ce nombre est positif.") Finsi Fin ```` - **Remarque** : dans la version 2, on fait trois tests systématiquement. Alors que dans la version 1, si le nombre est négatif on ne fait qu'un seul test. - **Conseil** : utiliser les tests imbriqués pour limiter le nombre de tests et placer d'abord les conditions les plus probables. ---- ## Exercice - Le prix de photocopies dans une reprographie varie selon le nombre demandé : - *0,5 euros* la copie pour un nombre de copies *inférieur à 10*. - *0,4 euros* pour un nombre ***compris** entre 10 et 20*. - et *0,3 euros* *au-delà*. - Ecrivez un algorithme qui *demande* à l'utilisateur le *nombre de photocopies*, qui *calcule* et *affiche* le *prix à payer*. ---- ## Correction ```javascript= Variables copies : entier prix : réel Debut ecrire("Nombre de photocopies : ") lire(copies) Si (copies < 10) Alors prix ← copies*0.5 Sinon Si (copies < 20) Alors prix ← copies*0.4 Sinon prix ← copies*0.3 Finsi Finsi ecrire("Le prix à payer est : " & prix) Fin ``` ---- ## Exercice 2 Demander à l'utilisateur une taille en octet et affichez lui combien cela fait en ko ou Mo ou Go ou au pire en octet. - Exemple: - 35455455 => 35.45 Mo - 14654 => 14.65Ko - 4567987465 => 4.57 Go ---- ## Correction 1 ```javascript= Variables octet: entier Début ecrire("Donnez une taille en octet : ") lire(octet) Si (octet < 1000) alors ecrire("Cela donne le même résultat car c'est inférieur au ko : " & octet & "o.") Sinon Si (octet < 1_000_000) alors ecrire("Cela donne " & octet / 1_000 & "ko.") Sinon Si (octet < 1_000_000_000) alors ecrire("Cela donne " & octet / 1_000_000 & "Mo.") Sinon ecrire("Cela donne " & octet / 1_000_000_000 & "Go.") Finsi Fin ``` ---- ## Correction 2 ```javascript= Variables octet : entier début écrireEcran("Entrez une taille en octet : "); lireClavier(octet); si (octet < 1000) alors écrireEcran("Cela donne le même résulat car ta taille est inférieur à 1000 : " & octet); sinon si (octet < 1_000_000) alors écrireEcran("Cela donne : " & octet / 1_000 & "ko."); sinon si (octet < 1_000_000_000) alors écrireEcran("Cela donne : " & octet / 1_000_000 & "Mo."); sinon si (octet < 1_000_000_000_000) alors écrireEcran("Cela donne : " & octet / 1_000_000_000 & "Go."); sinon écrireEcran("La taille est au-delà du Go et je ne connais pas l'unité."); finsi finsi finsi finsi fin ```` ---- ## Correction 3 ```javascript= Variables octet : entier début écrireEcran("Entrez une taille en octet : "); lireClavier(octet); si (octet < 10^3) alors écrireEcran("Cela donne le même résulat car ta taille est inférieur à 1000 : " & octet); sinon si (octet < 10^6) alors écrireEcran("Cela donne : " & octet / 10^3 & "ko."); sinon si (octet < 10^9) alors écrireEcran("Cela donne : " & octet / 10^6 & "Mo."); sinon si (octet < 10^12) alors écrireEcran("Cela donne : " & octet / 10^9 & "Go."); sinon écrireEcran("La taille est au-delà du Go et je ne connais pas l'unité."); finsi finsi finsi finsi fin ```` ---- ## Correction 4 ```javascript= Variables octet : entier début écrireEcran("Entrez une taille en octet : "); lireClavier(octet); si (octet < 10^3) alors écrireEcran("Cela donne le même résulat car ta taille est inférieur à 1000 : " & octet); sinon si (octet < 10^6) alors écrireEcran("Cela donne : " & octet / 10^3 & "ko."); sinon si (octet < 10^9) alors écrireEcran("Cela donne : " & octet / 10^6 & "Mo."); sinon si (octet < 10^12) alors écrireEcran("Cela donne : " & octet / 10^9 & "Go."); sinon écrireEcran("La taille est au-delà du Go et je ne connais pas l'unité."); finsi fin ``` --- # Instruction Cas - Lorsque l’on doit *comparer* une même variable *avec plusieurs valeurs*, on peut remplacer cette suite de si par l’instruction Cas. ```javascript= Cas où maVariable vaut valeur1 : action1 valeur2 : action2 ... valeurn : actionn autre : action autre FinCas ``` ---- # Exemple 1 ```javascript= Variables saison : chaine Debut ecrire("Entrez une saison : ") lire(saison) Cas où saison vaut "Hiver": Ecrire("il fait froid") "Ete" : Ecrire("il fait chaud") autre : Ecrire("je ne sais pas") FinCas Fin ``` ---- # Exemple 2 ```javascript= Variables c : caractère Debut ecrire("Entrer un caractère : ") lire(c) Si( (c >= 'A') et ( c <= 'Z') ) alors Cas où c vaut 'A','E', 'I', 'O', 'U', 'Y' : Ecrire("c’est une voyelle majuscule") autre : Ecrire("c’est une consonne majuscule") Fincas Sinon Ecrire("ce n’est pas une lettre majuscule") Finsi Fin ``` --- # Instructions itératives: les boucles ---- - 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* en langages de programmation : - Les **boucles tant que** : on y *répète* des instructions tant qu'une certaine condition est réalisée - Les **boucles jusqu'à** : on y *répète* des instructions jusqu'à ce qu'une certaine condition soit réalisée - 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 (Dans ce cours, on va s'intéresser essentiellement aux boucles Tant que et boucles Pour qui sont plus utilisées.) --- ## La boucle Tant Que ```javascript= TantQue (condition) instructions FinTantQue ``` - la condition (dite condition de contrôle de la boucle) est évaluée avant chaque itération - si la condition est *vraie*, on exécute les instructions (corps de la boucle), 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*. ----  ---- ## Exemple 1 Contrôle de saisie d'une lettre majuscule jusqu’à ce que le caractère entré soit valable ```javascript= Variable c : caractère Debut ecrire("Entrez une lettre majuscule : ") lire(c) TantQue(c < 'A' ou c > 'Z') ecrire("Saisie erronée. Recommencez : ") lire(c) FinTantQue ecrire("Saisie valable") Fin ``` ---- ## Exemple 2 - Version 1 Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100 ```javascript= Variables som, i : entier Debut i ← 0 som ← 0 TantQue(som <= 100) i ← i + 1 som ← som + i FinTantQue ecrire ("La valeur cherchée est N = ", i) Fin ``` ---- ## Exemple 2 - Version 2 Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100 :::danger ⚠️ Attention à l'ordre des instructions et aux valeurs initiales ::: ```javascript= Variables som, i : entier Debut som ← 0 i ← 1 TantQue(som <= 100) som ← som + i i ← i + 1 FinTantQue ecrire ("La valeur cherchée est N = ", i - 1) Fin ``` ---- ## Exercice Ecrire l'algorithme permettant d'afficher la table de multiplication par 9. - Exemple : - 9 x 1 = 9 - 9 x 2 = 18 - 9 x 3 = 27 - ... - 9 x 10 = 90 ---- ## Correction ```javascript= Variables i : entier Debut i ← 1 TantQue(i <= 10) ecrire("9 x " & i & " = " & (9 * i)) i ← i + 1 FinTantQue Fin ``` --- ## La boucle Pour ```javascript= Pour 'compteur' allant de 'initiale' à 'finale' par pas 'valeur du pas' instructions FinPour ```  ---- - *Remarque* : le nombre d'itérations dans une boucle *Pour* est connu avant le début de la boucle - **Compteur** est une variable de type entier (ou caractère). Elle doit être déclarée - **Pas** est un entier qui peut être positif ou négatif. **Pas** peut ne pas être mentionné, car par défaut sa valeur est égal à 1. Dans ce cas, le nombre d'itérations est égal à `finale - initiale+ 1`. - **Initiale et finale** peuvent être des valeurs, des variables définies avant le début de la boucle ou des expressions de même type que compteur. ---- ## Déroulement des boucles Pour - La valeur *initiale* est *affectée* à la variable *compteur*. - On *compare* la valeur du *compteur* et la valeur *finale* : - Si la valeur du compteur est *>* à la valeur *finale* dans le cas d'un *pas positif* (ou si compteur est *<* à *finale* pour un *pas négatif*), on sort de la boucle et on continue avec l'instruction qui suit *FinPour*. - Si compteur est *<=* à *finale* dans le cas d'un *pas positif* (ou si compteur est *>=* à *finale* pour un *pas négatif*), les instructions seront exécutées - Ensuite, la valeur de 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 ... ---- ## Exemple 1 - Version 1 Calcul de *x* à la puissance *n* où *x* est un réel *non nul* et *n* un entier *positif* ou *nul* ```javascript= Variables x, puiss : réel n, i : entier Debut ecrire("Entrez la valeur de x ") lire(x) ecrire("Entrez la valeur de n ") lire(n) puiss ← 1 Pour i allant de 1 à n puiss ← puiss * x FinPour ecrire(x & " à la puissance " & n & " est égal à " & puiss) Fin ``` ---- ## Exemple 1 - Version 2 Calcul de *x* à la puissance *n* où *x* est un réel *non nul* et *n* un entier *positif* ou *nul*(version avec pas *négatif*) ```javascript= Variables x, puiss : réel n, i : entier Debut ecrire("Entrez la valeur de x") lire(x) ecrire("Entrez la valeur de n") lire(n) puiss ← 1 Pour i allant de n à 1 par pas -1 puiss ← puiss*x FinPour ecrire(x & " à la puissance " & n & " est égal à " & puiss) Fin ``` ---- ## Remarque - Il faut *éviter* de **modifier la valeur du compteur** (et de finale) à l'intérieur de la boucle. En effet, une telle action : - perturbe le nombre d'itérations prévu par la boucle `Pour`. - rend *difficile* la lecture de l'algorithme. - présente le risque d'aboutir à une boucle *infinie*. *Exemple*: ```javascript= Variables i: entier Debut Pour i allant de 1 à 5 i ← i - 1 ecrire("i = " & i) FinPour Fin ``` ---- ## Exemple 2 ```javascript= Variables i: entier Debut Pour i allant de 0 à 10 ecrire(i) FinPour Fin ``` Cette boucle affichera successivement les nombres 0, 1, ..., 10, on effectue donc 11 itérations. ---- ## Exercice 1 Ecrire l'algorithme permettant d'afficher la table de multiplication par 9. ---- ## Correction ```javascript= Variables i: entier Debut Pour i allant de 1 à 10 ecrire("9 x " & i & " = " & (9 * i)) FinPour Fin ``` ---- ## Exercice 2 Ecrire un algorithme qui demande successivement 20 nombres à l’utilisateur, et qui lui dit ensuite quel était le plus grand parmi ces 20 nombres. ---- ## Correction 1 ```javascript= Variables i: entier nbr, max: réel Debut ecrire("Entrez un nombre : ") lire(max) Pour i allant de 0 à 18 ecrire("Entrez un nombre : ") lire(nbr) Si (nbr > max) alors max ← nbr Finsi FinPour ecrire("Le nombre max est : " & max) Fin ``` ---- ## Correction 2 ```javascript= Variables i: entier nbr, max: réel Debut max <- 0 Pour i allant de 0 à 19 ecrire("Entrez un nombre : ") lire(nbr) Si (i = 0) alors max <- nbr sinon Si (nbr > max) alors max ← nbr Finsi FinSi FinPour ecrire("Le nombre max est : " & max) Fin ``` ---- ## Correction 3 ```javascript= Variables i: entier nbr, max: réel Debut max <- 0 Pour i allant de 0 à 19 ecrire("Entrez un nombre : ") lire(nbr) Si (i = 0 OU nbr > max) alors max <- nbr FinSi FinPour ecrire("Le nombre max est : " & max) Fin ``` ---- ## Exercice 3 Ecrire un algorithme qui demande un nombre de départ, et qui calcule la somme des entiers jusqu’à ce nombre. Par exemple, si l’on entre 4, le programme doit calculer et afficher : 1 + 2 + 3 + 4 = 10 ---- ## Correction 1 ```javascript= Variables nbr, somme, i: entier Debut ecrire("Entrez un nombre entier : ") lire(nbr) somme ← 0 Pour i allant de 1 à nbr somme ← somme + i Si (i = nbr) alors ecrire(i & " = " & somme) Sinon ecrire(i & " + ") Finsi FinPour Fin ``` ---- ## Correction 2 ```javascript= Variables nbr, somme, i: entier str : chaine de caractère Debut ecrire("Entrez un nombre entier : ") lire(nbr) somme ← 0 str <- "" Pour i allant de 1 à nbr somme ← somme + i Si (i = 1) alors str ← i Sinon str ← str & " + " & i Finsi FinPour ecrire(str & " = " & somme) Fin ``` ---- ## Exercice 4 Même chose que l'exercice 3. La seule différence sera d'inverser l'affichage : 4 + 3 + 2 + 1 = 10 ---- ## Correction ```javascript= Variables nbr, somme, i: entier str : chaine de caractère Debut ecrire("Entrez un nombre entier : ") lire(nbr) somme ← 0 Pour i allant de nbr à 1 par pas -1 somme ← somme + i Si (i = 1) alors str ← i Sinon str ← str & " + " & i Finsi FinPour ecrire(str & " = " & somme) Fin ``` --- # Lien entre Pour et TantQue La boucle *Pour* est un cas *particulier* de *Tant Que* (cas où le nombre d'itérations est connu et fixé). Tout ce que l'on peut écrire avec *Pour* peut être *remplacé* avec *TantQue* (la *réciproque est fausse*). ```javascript= Pour compteur allant de initiale à finale par pas valeur du pas instructions FinPour ``` Peut-être remplacé par : ```javascript= compteur ← initiale TantQue compteur <= finale instructions compteur ← compteur + pas FinTantQue ``` ---- ## Exemple - Tant Que Calcul de *x* à la puissance *n* où *x* est un *réel* non nul et *n* un entier positif ou nul ```javascript= Variables x, puiss : réel n, i : entier Debut ecrire(" Entrez la valeur de x ") lire(x) ecrire(" Entrez la valeur de n ") lire(n) puiss ← 1 i ← 1 TantQue(i <= n) puiss ← puiss * x i ← i + 1 FinTantQue ecrire(x & " à la puissance " & n & " est égal à " & puiss) Fin ``` ---- ## Exemple - Pour (Ce trouve dans la section : Pour) ```javascript= Variables x, puiss : réel n, i : entier Debut ecrire("Entrez la valeur de x ") lire(x) ecrire("Entrez la valeur de n ") lire(n) puiss ← 1 Pour i allant de 1 à n puiss ← puiss * x ecrire(x & " à la puissance " & n & " est égal à " & puiss) FinPour Fin ``` --- # Boucles imbriquées ### Les instructions d'une boucle peuvent être des instructions itératives. Dans ce cas, on aboutit à des boucles imbriquées. ---- ## Exemple ```javascript= Pour i allant de 1 à 5 Pour j allant de 1 à i ecrire("O") FinPour ecrire("X\n") FinPour ``` | Itération | | | | | | | | --------- |:---:|:---:|:---:|:---:|:---:|:---:| | 1 | 0 | X | | | | | | 2 | 0 | 0 | X | | | | | 3 | 0 | 0 | 0 | X | | | | 4 | 0 | 0 | 0 | 0 | X | | | 5 | 0 | 0 | 0 | 0 | 0 | X | --- ## La boucle Répéter ... jusqu'à ... ```javascript Répéter instructions jusqu'à (condition); ``` - *Condition* est évaluée après chaque itération - Les instructions entre *Répéter* et *jusqu’à* sont exécutées au moins *une fois* et leur exécution est répétée jusqu’à ce que *condition soit vrai* (tant qu'elle est fausse) ----  ---- ## Exemple Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100. ```javascript Variables som, i : entier Debut som ← 0 i←0 Répéter i ← i+1 som ← som + i Jusqu'à( som > 100) ecrire("La valeur cherchée est N= " & i) Fin ``` ---- # Exercice Ecrire un algorithme qui demande à l’utilisateur un nombre compris entre 1 et 3 jusqu’à ce que la réponse convienne. ---- # Correction ```javascript= Variable nbr : entier Debut Repeter ecrire("Entrez un nombre entre 1 et 3") lire(nbr) Jusqu'à(nbr >= 1 ET nbr <= 3) ecrire("Good job") Fin ``` --- # Choix d'un type de boucle - Si on peut *déterminer* le nombre *d'itérations* avant l'exécution de la boucle, il est plus naturel d'utiliser la boucle *Pour*. - S'il n'est *pas possible de connaître* le nombre *d'itérations* avant l'exécution de la boucle, on fera appel à l'une des boucles *TantQue* ou *répéter jusqu'à*. - Pour le *choix* entre *TantQue* et *jusqu'à* : - Si on doit *tester* la condition de contrôle *avant* de commencer les instructions de la boucle, on utilisera *TantQue*. - Si la valeur de la condition de contrôle *dépend d'une première exécution* des instructions de la boucle, on utilisera *répéter jusqu'à*. --- # Fonctions et procédures ---- - Certains problèmes conduisent à des *programmes longs*, *difficiles* à *écrire* et à *comprendre*. On les découpe en des parties appelées *sous-programmes* ou *modules*. - Les *fonctions* et les *procédures* sont des modules (groupe d'instructions) indépendants désignés par un nom. Elles ont plusieurs intérêts : - permettent de *"factoriser" les programmes*, càd de mettre en commun les parties qui se répètent - permettent une *structuration* et une *meilleure lisibilité* des programmes - *facilitent la maintenance* du code(il suffit de modifier une seule fois) - ces procédures et fonctions peuvent éventuellement être *réutilisées* dans d'autres programmes --- # Fonctions - Le *rôle* d'une fonction en programmation est similaire à celui d'une fonction en mathématique : elle *retourne un résultat à partir des valeurs des paramètres*. - Une fonction s'écrit en dehors du programme principal sous la forme : ```javascript= Fonction nom_fonction(paramètres et leurs types) : type_fonction Instructions constituant le corps de la fonction retourne... FinFonction ``` - Pour le choix d'un *nom de fonction* il faut respecter les *mêmes règles* que celles pour les *noms de variables*. - type_fonction est le type du résultat retourné - L'instruction *retourne* sert à retourner la valeur du résultat ---- ## Exemples - La fonction *SommeCarre* suivante calcule la somme des carrées de deux réels x et y : ```javascript= Fonction sommeCarre(x : réel, y: réel) : réel Variable z : réel z ← x^2 + y^2 retourne(z) FinFonction ``` - La fonction *Pair* suivante détermine si un nombre est pair : ```javascript= Fonction pair(n : entier) : booléen retourne(n % 2 = 0) FinFonction ``` ---- ## Utilisation des fonctions - L'utilisation d'une *fonction* se fera par simple écriture de son nom dans le programme principal. Le *résultat* étant une *valeur*, elle devra *être affectée* ou *être utilisée* dans une expression, une écriture,... - Exemple : ```javascript= Algorithme ExempleAppelFonction Variables z : réel, b : booléen Debut b ← pair(3) z ← 5 * sommeCarre(7, 2) + 1 ecrire("SommeCarre(3,5) = " & sommeCarre(3, 5) ) Fin ``` - Lors de l'appel `pair(3)`, le *paramètre formel* n est remplacé par le *paramètre effectif* 3. ---- ## Exercice - Définir une *fonction* qui renvoie le *plus grand* de *deux nombres différents*. - *Ecrire* un programme qui *demande deux nombres* à l’utilisateur et qui *affiche* le plus grand des deux nombres en appelant la fonction précédemment créée. ---- ## Correction ```javascript= Fonction plusGrand(x: entier, y: entier) : entier Si x > y alors retourne x Sinon retourne y Finsi FinFonction Algorithme main Variables a, b : entier Debut ecrire("Donnez la valeur de a : ") lire(a) ecrire("Donnez la valeur de b : ") lire(b) ecrire("Le plus grand de ces deux nombres est : " & plusGrand(a, b)) Fin ``` --- # Procédures - Dans certains cas, on peut avoir besoin de répéter une tache dans *plusieurs endroits du programme*, mais que dans cette tâche on ne calcule *pas de résultats* ou qu'on calcule *plusieurs résultats à la fois*. - Dans ces cas on ne peut pas utiliser une fonction, on utilise une *procédure*. - Une *procédure* est un sous-programme semblable à une fonction mais qui *ne retourne rien*. - Une procédure s'écrit en dehors du programme principal sous la forme : ```javascript Procédure nom_procédure (paramètres et leurs types) Instructions constituant le corps de la procédure FinProcédure ``` - ***Remarque*** : une procédure peut ne pas avoir de paramètres ---- ## Appel d'une procédure - *L'appel d'une procédure*, se fait dans le programme principale ou dans une autre procédure par une instruction indiquant le nom de la procédure : ```javascript= Procédure exempleProc(...) ... FinProcédure Algorithme exempleAppelProcédure Debut exempleProc(...) Fin ``` - **Remarque** : contrairement à l'appel d'une fonction, on ne peut pas affecter la procédure appelée ou l'utiliser dans une expression. L'appel d'une procédure est une *instruction autonome*. ---- ## Paramètres d'une procédure - Les paramètres servent à *échanger des données* entre le programme principal (ou la procédure appelante) et la procédure appelée. - Les *paramètres placés* dans la *déclaration* d'une procédure sont appelés *paramètres formels*. Ces paramètres peuvent prendre toutes les valeurs possibles mais ils sont *abstraits* (*n'existent pas réellement*) - Les *paramètres placés* dans *l'appel* d'une procédure sont appelés *paramètres effectifs*. Ils contiennent les valeurs pour effectuer le traitement. - Le **nombre de paramètres effectifs** doit **être égal** au **nombre de paramètres formels**. *L'ordre et le type des paramètres doivent correspondre*. --- # Transmission des paramètres Il existe *deux modes* de *transmission de paramètres* dans les langages de programmation : - **La transmission par valeur** : les valeurs des *paramètres effectifs* sont *affectées* aux paramètres formels correspondants au moment de l'appel de la procédure. Dans ce mode le paramètre effectif ne subit *aucune modification*. - **La transmission par adresse** (ou par *référence*) : les adresses des paramètres effectifs sont *transmises* à la procédure appelante. Dans ce mode, le paramètre effectif *subit les mêmes modifications que le paramètre formel* lors de l'exécution de la procédure. - **Remarque** : le *paramètre effectif* doit être une *variable* (et non une valeur) lorsqu'il s'agit d'une *transmission par adresse*. En pseudo-code, on va préciser explicitement le mode de transmission dans la déclaration de la procédure. ---- # Exemple 1 ```javascript= Procedure incrementer1(x: entier par valeur, y: entier par adresse) x ← x + 1 y ← y + 1 FinProcedure Algorithme TestIncrementer1 Variables n, m : entier Debut n ← 3 m ← 3 incrementer1(n, m) écrire ("n= ", n, " et m= ", m) Fin ``` #### Résultat : n = 3 et m = 4 **Remarque** : l'instruction `x ← x + 1` n'a pas de sens avec un passage par valeur. ---- # Exemple 2 Procédure qui calcule la somme et le produit de deux entiers : ```javascript= Procedure sommeProduit(x, y: entier par valeur, som, prod : entier par adresse) som ← x + y prod ← x * y FinProcedure ``` Procédure qui échange le contenu de deux variables : ```javascript= Procedure echange(x: réel par adresse, y: réel par adresse) Variables z: réel z ← x x ← y y ← z FinProcedure ``` --- # Portée des variables - locales / Globales - On peut manipuler *2 types de variables* dans un module (procédure ou fonction) : des variables *locales* et des variables *globales*. Elles se distinguent par ce qu'on appelle leur *portée* (leur "champ de définition", leur "durée de vie") - Une **variable locale** n'est connue qu'à *l'intérieur du module où elle a été définie*. Elle est créée à l'appel du module et *détruite* à la fin de son *exécution*. - Une **variable globale** est connue par *l'ensemble des modules* et le *programme principal*. Elle est définie durant *toute l'application* et peut être utilisée et modifiée par les différents modules du programme. ---- - La *manière* de *distinguer* la déclaration des variables locales et globales diffère *selon* le *langage*. - En général, les *variables* déclarées à *l'intérieur* d'une fonction ou procédure sont considérées comme *variables locales*. - En *pseudo-code*, on va *adopter* cette *règle* pour les variables *locales* et on *déclarera* les variables *globales* dans le programme *principal*. - **Conseil** : Il faut *utiliser autant que possible* des variables *locales* plutôt que des variables globales. Ceci permet *d'économiser la mémoire* et d'assurer *l'indépendance* de la procédure ou de la fonction. --- # Récursivité - Un *module* (fonction ou procédure) peut *s'appeler lui-même*: on dit que c'est un *module récursif*. - Tout module *récursif* doit posséder un *cas limite* (cas trivial) qui *arrête* la *récursivité* - Exemple : Calcul du factorielle ```javascript= Fonction fact (n : entier ) : entier Si(n = 0) alors retourne (1) Sinon retourne (n * fact(n-1)) Finsi FinFonction ``` ---- ## Exercice Ecrivez une fonction récursive(puis itérative) qui calcule le terme n de la *suite de Fibonacci* définie par : - U(0) = U(1)=1 - U(n) = U(n-1) + U(n-2) ---- ## Correction Récursive ```javascript= Fonction Fib (n : entier ) : entier Variables res : entier Si (n = 1 OU n = 0) alors res ← 1 Sinon res ← Fib(n-1) + Fib(n-2) Finsi retourne(res) FinFonction ``` ---- ## Correction Itérative - Une fonction itérative pour le calcul de la *suite de Fibonacci* : ```javascript= Fonction Fib (n : entier) : entier Variables i, avantDernier, dernier, nouveau : entier Si (n = 1 OU n = 0) alors retourne(1) Finsi avantDernier ← 1 dernier ← 1 Pour i allant de 2 à n nouveau ← dernier + avantDernier avantDernier ← dernier dernier ← nouveau FinPour retourne(nouveau) FinFonction ``` **Remarque**: la solution récursive est plus facile à écrire. ---- ## Procédures récursives : exemple - Une procédure récursive qui permet d'afficher la valeur *binaire* d'un entier *n* ```javascript= Procédure binaire (n : entier ) Si (n<>0) alors binaire(n / 2) ecrire(n % 2) Finsi FinProcédure ``` --- # Les Tableaux --- ## Problématique ```javascript= Algorithme Note Variables n1, n2, n3, n4, n5 : Réel Debut ecrire("Entrez la valeur de la 1er note : ") lire(n1) ecrire("Entrez la valeur de la 2eme note : ") lire(n2) ecrire("Entrez la valeur de la 3eme note : ") lire(n3) ecrire("Entrez la valeur de la 4eme note : ") lire(n4) ecrire("Entrez la valeur de la 5eme note : ") lire(n5) ecrire("La note 1 multipliée par 3 est : " & n1 * 3) ecrire("La note 2 multipliée par 3 est : " & n2 * 3) ecrire("La note 3 multipliée par 3 est : " & n3 * 3) ecrire("La note 4 multipliée par 3 est : " & n4 * 3) ecrire("La note 5 multipliée par 3 est : " & n5 * 3) Fin ``` --- ## Définition d'un tableau - Un *tableau* est une *suite d'éléments* de *même type*. - Il utilise *plusieurs cases mémoire* à l'aide d'un *seul nom*. - Comme toutes les cases *portent le même nom*, elles se *différencient* par un *numéro* ou un *indice*. ---- ## Syntaxe d'un tableau ```javascript= Variable identifiant : tableau[taille] de type ``` - La taille du tableau doit être un nombre entier. - Les éléments d'un tableau sont des variables qui s'utilisent exactement comme n'importe quelles autres variables classiques. ---- ## Utilisation d'un tableau - Soit le tableau suivant : `Variable notes : tableau[30] de réels`. - L'*utilisation* de ces *éléments* se fait via le *nom du tableau* et son *indice*. Cet indice peut être soit une valeur (exemple : `notes[3]`), soit une variable (exemple : `notes[i]`) ou encore une expression (exemple : `notes[i+1]`). - Le *premier élément* d'un *tableau* porte l'indice **zéro**. ---- ## Exemples - *Exemple 1* : L'instruction suivante affecte à la variable *x* la valeur du *premier* élément du tableau *Note* : <br>&emsp;&emsp;`x ← notes[0]`. - *Exemple 2* : L'instruction suivante affiche le contenu de l’élément en *quatrième* position du tableau *notes* : <br>&emsp;&emsp;`ecrire(notes[4])`. - *Exemple 3* : L'instruction suivante *affecte* une valeur introduite par l'utilisateur à la *position trois* du tableau *Note* : <br>&emsp;&emsp;`lire(notes[3])`. ---- ## Exercice 1 Ecrire un algorithme qui *déclare* et *stocke* dans un *tableau* les *six voyelles de l’alphabet*. ---- ## Correction ```javascript= Algorithme tableau_voyelles Variables voyelles : tableau[6] de Caractères Début voyelles[0] ← 'a' voyelles[1] ← 'e' voyelles[2] ← 'i' voyelles[3] ← 'o' voyelles[4] ← 'u' voyelles[5] ← 'y' Fin ``` ---- ## Exercice 2 Écrire un algorithme permettant de *saisir 30 notes* et de *les afficher*. ---- ## Correction 1 ```javascript= Algorithme tableau_note Variables notes : tableau[30] de réels, i : entier Début //Remplissage du tableau notes Pour i allant de 0 à 29 ecrire("Entrer la valeur de la note n " & i + 1) lire(notes[i]) FinPour //Affichage des notes Pour i allant de 0 à 29 ecrire("La note " & i + 1 & " vaut " & notes[i]) FinPour Fin ``` :::info Il existe une technique qui permet de récupérer la longueur d'un tableau : `longueur(notes)` ::: ---- ## Correction 2 ```javascript= Algorithme tableau_note Variables notes : tableau[30] de réels, i : entier Début //Remplissage du tableau notes Pour i allant de 0 à longueur(notes) - 1 ecrire("Entrer la valeur de la note n°" & i + 1) lire(notes[i]) FinPour //Affichage des notes Pour i Allant de 0 à longueur(notes) - 1 ecrire("La note " & i + 1 & " vaut " & notes[i]) FinPour Fin ``` --- # Tableau à 2 dimensions (matrice) - Les *tableaux à deux dimensions* se représentent comme une *matrice* ayant un certain nombre de *lignes* (*première dimension*) et un certain nombre de *colonnes* (*seconde dimension*). - Reprenons l'exemple des notes en considérant cette fois qu'un *étudiant a plusieurs notes* (une *note pour chaque matière*). Pour *quatre étudiants*, nous aurions le *tableau de relevés des notes* suivant : | Matière | Etudiant 1 | Etudiant 2 | Etudiant 3 | Etudiant 4 | | ------------- |:----------:|:----------:|:----------:|:----------:| | Informatique | 12 | 13 | 9 | 10 | | Comptabilité | 12.5 | 14 | 12 | 11 | | Mathématiques | 15 | 12 | 10 | 13 | ---- ## Syntaxe d'un tableau à 2 dimensions `Variable identificateur : tableau[nb_lignes][nb_colonnes] de type` L'instruction suivante déclare un tableau *notes* de type réel à deux dimensions composé de 3 lignes et de 4 colonnes : `Variable notes : tableau[3][4] de réels` ---- ## Utilisation d'un tableau à 2 dimensions - Pour accéder à un élément de la *matrice* (tableau à deux dimensions), il suffit de préciser, *entre crochets*, les *indices* de la *case* contenant cet élément. - **Exemple** : L'instruction suivante *affecte* à la variable `x` la valeur de l’élément du tableau `notes` positionné sur la *première ligne* et la *première colonne* : <br>&emsp;&emsp;`x ← notes[0][0]`. ---- ## Parcours d'un tableau à 2 dimensions - Pour *parcourir* une *matrice* nous avons besoin de *deux boucles*, l'une au sein de l'autre, c'est ce qu'on appelle les *boucles imbriquées*. - La *première* boucle est conçue pour *parcourir les lignes*. - Tandis que la *deuxième* est utilisée pour *parcourir les colonnes* de la *ligne précisée* par la *boucle* principale (la première boucle). ---- ## Exercice Écrire un *algorithme* permettant la *saisie* des *notes* d'une classe de *15 étudiants* pour *3 matières*. ---- ## Correction 1 ```javascript= Algo NotesEleve Variables notes : Tableau[3][15] de reel i, j : entier Debut /* note = [ [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], ] */ // notes[0] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] // notes[1] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] // notes[2] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Pour i allant de 0 à longueur(notes) - 1 Pour j allant de 0 à longueur(notes[i]) - 1 ecrire("Rentrez la note : ") lire(note[i][j]) FinPour FinPour Fin ``` ---- ## Correction 2 ```javascript= Algorithme Notes Constantes n = 15, m = 3 : entier Variables note : tableau[n][m] de réels i, j : entier Debut //Remplissage du tableau note Pour i allant de 0 à n - 1 Pour j Allant de 0 à m - 1 ecrire("Entrez la note de l'étudiant" & i + 1 & " dans la matière " & j + 1) lire(note[i][j]) FinPour FinPour Fin ``` --- # Problématique On veut *représenter* dans un programme les *données* de *20 personnes* avec pour chacune *un nom, un prénom et un âge*. ``` nom1, prenom1: chaine age1: entier ... nom20, prenom20 : chaine age20 : entier ... nom1 ← "Dupont"; prenom1 ← "Jean"; age1 ← 34; ... ``` --- # Enregistrement (classe / structure) - Jusqu’à présent, nous n’avons utilisé que des **types primitifs** (caractères, entiers, réels, chaînes) et des tableaux de types primitifs. - Mais il est possible de créer nos **propres types**, puis de déclarer des variables ou des tableaux d’éléments de ce type. - Pour ce faire, il faut *déclarer* un nouveau type. Après l’avoir défini, on peut dès lors utiliser ce type structuré comme tout autre type normal en déclarant une ou plusieurs variables de ce type. - Les variables de type **structuré** sont appelées ***enregistrements***. - La déclaration des types structurés se fait *avant* la section des *variables* (et *après* la section des *constantes*). - Si l’algorithme comporte des **sous-programmes**, les **types** et les **constantes** sont déclarées en **dehors du programme**. ---- ## Déclaration d'un enregistrement ```javascript= Enregistrement identificateur cle1: type, cle2: type, ... FinEnregistrement ``` ---- ## Exemple ```javascript= Enregistrement Personne nom: chaine, prenom: chaine, age: entier FinEnregistrement ``` ---- ## Initialisation d'un enregistrement - Il faut *créer* une *instance* de l’enregistrement *Personne* pour pouvoir *l’utiliser*. - On peut créer *autant* d’instance que *nécessaire*. - *Fonctionne* comme une *variable classique*, *l’identificateur* de l’enregistrement devient un *nouveau type* de variable. `Variable p1: Personne`. ---- ## Remplissage d'un enregistrement *Deux possibilités* pour remplir une instance d’un *enregistrement* ```javascript= p1.nom ← "Dupont" p1.prenom ← "Jean" p1.age ← 34 // ou p1 ← { nom: "Dupont", prenom: "Jean", age: 34 } ``` ---- ## Exercice 1 *Écrire* un *enregistrement* permettant de *stocker* les *informations* sur un *véhicule* chez un *concessionnaire*. ---- ## Correction ```javascript= Enregistrement Voiture modele: chaine, marque: chaine, annee: entier, kilometrage: entier FinEnregistrement ``` ---- ## Exercice 2 *Stocker* le *véhicule* de votre choix dans une *instance* de l’enregistrement précédemment créé. ---- ## Correction ```javascript= Variable v1: Voiture v1.modele ← "Mégane" v1.marque ← "Renault" v1.annee ← 2017 v1.kilometrage ← 55000 ``` ```javascript= // 2ème possibilité v1 ← { modele: "Mégane", marque: "Renault", annee: 2017, kilometrage: 55000 } ``` ---- # Encore une problématique On veut toujours *stocker* dans un *programme* les *données* de *20 personnes* avec pour *chacune un nom, un prénom et un âge*. ```javascript= Enregistrement Personne nom: chaine, prenom: chaine, age: entier FinEnregistrement Variables p1, p2, p3, ..., p20: Personne ``` ---- ## Tableau d'enregistrement - Vous *connaissez les tableaux*. Ils permettent de *mémoriser* des *informations* et d'y accéder par leur *index*. - Nous avons *vu jusqu’à maintenant* que dans un *tableau* on pouvait mettre des *entiers*, des *chaines*, etc... - Nous avons vu via la *déclaration d’un enregistrement* que cela permettait d’avoir *un « nouveau » type* à disposition. - Donc nous pouvons créer des *tableaux stockant* des *enregistrements* d’un certain *type prédéfinie*. ---- ## Déclaration d'un tableau d'enregistrements `Variable personnes: tableau[20] de Personne` ---- ## Initialisation d'un tableau d'enregistrements ```javascript= personnes[0].nom ← "Dupont" personnes[0].prenom ← "Jean" personnes[0].age ← 34 ... personnes[19].nom ← "Dupond" personnes[19].prenom ← "Julien" personnes[19].age ← 26 ``` ```javascript= personnes[0] ← { nom: "Dupont", prenom: "Jean", age: 34 } ... personnes[19] ← { nom: "Dupond", prenom: "Julien", age: 26 } ``` ---- ## Exercice 1. *Créer* un *tableau d’enregistrements* pouvant contenir *10 instances de Voiture*. 2. *Utiliser une boucle* pour *parcourir* ce tableau et le *remplir* par les *données saisies* par *l’utilisateur*. Mémo: ```javascript Enregistrement Voiture modele: chaine, marque: chaine, annee: entier, kilometrage: entier FinEnregistrement ``` ---- ## Correction ```javascript= Variables voitures: tableau[10] de Voiture, i: entier Debut Pour i allant de 0 à longueur(voitures) - 1 ecrire("Saisir la marque de la voiture n°" & i + 1) lire(voitures[i].marque) ecrire("Saisir le modèle de la voiture n°" & i + 1) lire(voitures[i].modele) ecrire("Saisir l’année de la voiture n°" & i + 1) lire(voitures[i].annee) ecrire("Saisir le kilométrage de la voiture n°" & i + 1) lire(voitures[i].kilometrage) FinPour Fin ``` --- # Exercices complémentaires --- ## Priorité des Opérateurs Donner les valeurs des variables a, b, c et d. ```javascript= a <— 4 * 2 + 5 b <— 5 + 3 * 2 - 6 c <— (a > b) ET (b > 2) d <— (a < b) OU (b > 2) ``` ---- ## Correction Solution : a = 13, b = 5, c = Vrai et d = Vrai. --- ## Triangle d'étoiles Ecrire un algorithme qui affiche à l’écran le triangle d’étoiles suivant : ```javascript * * * * * * * * * * * * * * * ``` ---- ## Correction ```javascript= Algorithme TriangleEtoiles Variables i, j : entiers Debut Pour i allant de 1 à 5 Pour j allant de 1 à i ecrire("*") FinPour //Retour à la ligne ecrire("\n") FinPour Fin ``` --- ## Devinette *Ecrire* un *programme* mettant en oeuvre le *jeu* suivant : - Le *premier utilisateur saisi* un entier que le *second doit deviner*. Pour cela, il a le droit à *autant* de *tentatives* qu’il *souhaite*. - A chaque *échec*, le *programme* lui *indique* si *l’entier cherché* est *plus grand* ou *plus petit* que sa proposition. - Un *score* indiquant le *nombre de coups joués* est mis à jour et *affiché* lorsque *l’entier est trouvé*. ---- # Correction ```javascript= Algo Devinette Variables nb, reponse, score : entier Debut ecrire("Joueur 1 saisi un nombre à faire deviner") lire(nb) score ← 0 Répéter ecrire("Joueur 2 tente ta chance") lire(reponse) Si (reponse > nb) alors ecrire("Le nombre recherché est plus petit") Sinon Si (reponse < nb) alors ecrire("Le nombre recherché est plus grand") FinSi FinSi score ← score + 1 Jusqu’à (nb = reponse) ecrire("Bonne réponse, chapeau l’artiste") ecrire(score & " tentatives pour trouver la réponse") Fin ``` --- ## Trier un Tableau *Écrire* un *algorithme* permettant de *trier un tableau* | &nbsp;9&nbsp; | &nbsp;5&nbsp; | &nbsp;4&nbsp; | &nbsp;1&nbsp; | &nbsp;6 | exemple ⬇ 1er tour | &nbsp;1&nbsp; | &nbsp;9&nbsp; | &nbsp;5&nbsp; | &nbsp;4&nbsp; | &nbsp;6 | ⬇ | &nbsp;1&nbsp; | &nbsp;4&nbsp; | &nbsp;5&nbsp; | &nbsp;6&nbsp; | &nbsp;9&nbsp; | *Indices* : - on *cherche* l’élément de la *plus petite valeur* dans le *tableau* - on le *place* en *tête du tableau* - *recommencer* avec le tableau *moins* la *première case* ---- ## Correction ```javascript= Algorithme TriTableau Variables tab : tableau[5] d’entiers i, j, indice, min : entier Debut // Remplissage du tableau tab[0] ← [9, 5, 4, 1, 6] // Tri du tableau Pour i allant de 0 à Longueur(tab) - 2 min ← tab[i] Pour j allant de i + 1 à Longueur(tab) - 1 Si (tab[j] < tab[i]) alors min ← tab[j] indice ← j FinSi FinPour tab[indice] ← tab[i] tab[i] ← min FinPour Fin ``` ---- ## Autre Correction ```javascript= Algorithme TriTableau Variables tab : tableau[5] d’entiers i, j, tmp : entier Debut // Remplissage du tableau tab[0] ← [9, 5, 4, 1, 6] // Tri du tableau Pour i allant de 0 à Longueur(tab) - 2 Pour j allant de i + 1 à Longueur(tab) - 1 Si (tab[j] < tab[i]) alors tmp ← tab[i] tab[i] ← tab[j] tab[j] ← tmp FinSi FinPour FinPour Fin ``` --- # The end --- # Niveau supérieur → un Langage de Programmation. ### Bon courage.