1-briques-de-base-1.pdf

Algorithmique et programmation 1 Préambule Bienvenue dans le cours Algorithmique et Programmation 1 ! Pour qui ? Pour quoi ? Ce cours est destiné en particulier aux étudiant.e.s ayant peu d'expérience en programmation. Il va couvrir les bases de la programmation impérative, à travers le langage de programmation Python (3), ainsi que constituer une introduction à la discipline (et à la pensée) algorithmique. Ces notes sont pensées pour accompagner, enrichir et détailler les transparents présentés en cours magistral (CM). Les transparents sont aussi disponibles en consultation en ligne ou au téléchargement. Elles sont en grande partie basées sur les notebooks des années précédentes, rédigées principalement par Antoine Meyer. Bonne découverte et bon semestre ! Marie et Léo Trouver des informations Contacts (à chercher dans l'annuaire) : ▪ Responsable de formation : Antoine Meyer ▪ Secrétaire de formation : Ramatoulaye Barry [email protected] (absence, pb admin,...) ▪ Responsables de l'UE : Marie van den Bogaard et Léo Exibard Page web : ▪ https://elearning.univ-eiffel.fr/course/view.php?id=9175 ▪ Ressources diverses (ouvrages, liens, annonces) ▪ Sujets des TD, des TP, liens vers les supports de cours Communication : ▪ Discord : https://discord.gg/6jrfmUwcSp ▪ Mail : exclusivement sur votre adresse ▪ Webmail : http://partage.univ-eiffel.fr Programme et références Ce cours recouvre très largement la partie Langages et programmation du programme de l'option de spécialité NSI de première générale proposée par les (des) lycées français. Certaines notions des parties Algorithmique, Représentation des données et Histoire de l'informatique seront aussi abordées. (cf. https://www.education.gouv.fr/media/23690/download) Beaucoup de ressources sont disponibles pour apprendre et approfondir les concepts présentés dans ce cours. Nous recommandons notamment le livre Informatique :Inf, collection Fluoresciences, éditions Dunod, partie 1 Mathématiques pour l'Informatique et partie 2 Algorithmique et Programmation, disponible à la bibliothèque universitaire Georges Pérec. Le livre pdf gratuit de G. Swinnen, Apprendre à programmer avec Python 3, dont le lien se trouve sur la page e-learning du cours, peut aussi s'avérer pertinent pour le lecteur curieux. En (très) résumé, voici les notions abordées dans la suite de ces notes et pendant les séances de CMs, TDs et TPs: Notion d'algorithme : déﬁnition, intérêt, exemples, mise en oeuvre Briques de base de la programmation impérative : variables, assignation, expressions, opérations, structure de contrôle, représentation des données (types simples, types construits, structures de données), fonctions Outils mathématiques et de raisonnement : bases de numération, arithmétique "euclidienne" (division entière, reste, modulo, ppcm, pgcd), booléens et valeurs de vérités Machinerie Python : syntaxe, fonctionnement de la mémoire, méthodes utiles, listes, dictionnaires Bonnes pratiques de programmation : Règles de style, Prototypage, Découpage en sous-tâches, Documentation, Tests (en bonus, si le temps le permet : une introduction au concept de récursivité) Navigation dans les notes Voici quelques liens internes pour vous aider à naviguer dans ces notes de cours (une sorte de table des matières). Introduction Briques de base de l'algorithmique A) Connaissances techniques de base sur Python : Types de valeurs Opérations Variables et affectations Modèle de mémoire en Python Saisie et afﬁchage B) Contrôle du ﬂot d'exécution : Structures de contrôle Expressions boolénnes Opérateurs booléens et tables de vérité Instructions conditionnelles ▪ Conditionnelles enchaînées Boucles tant que / while ▪ Boucles imbriquées C) Groupes de données et d'instructions : bases Introduction aux listes Introduction aux fonctions Introduction Une histoire de zéros et de uns... ou du binaire aux langages de programmation ou comment en est-on arrivé là ? Dans cette section, nous allons essayer d'éclairer l'écart entre le monde des bits et le monde des langages de programmation haut niveau, comme le Python. La majorité des gens ont en effet une vague idée du fait que l'informatique, ou même l'ordinateur, "ça marche avec des zéros et des uns". Ce petit morceau de vulgarisation scientiﬁque dans la culture générale, bien que raisonnable, est parcellaire et très éloigné de la réalité de nos interactions avec l'informatique. Réalité quotidienne d'une grande partie de l'humanité : utilisation d'applications sur nos ordinateurs, téléphones et montres pour réaliser tout un tas de tâches (communication, divertissement, administratif, apprentissage, graphisme...), mais aussi réalité quotidienne pour une partie beaucoup plus restreinte de l'humanité: les informaticien.ne.s ! Concrètement, depuis très longtemps (à l'échelle de l'histoire de l'informatique), les informaticien.ne.s ne manipulent pas de 0 et de 1 (de bits) "à la main" (ou alors très rarement, on verra cela). En particulier, en programmation, on utilise en pratique des langages qu'on appelle de haut niveau : des langages qui sont relativement compréhensibles à la lecture par un être humain initié. On comprend donc mieux les programmes, et on les écrit aussi plus facilement. D'accord, mais on nous avait donc menti avec ces histoires de zéros et de uns? Non ! Ils sont toujours là, mais entre eux et ce que nous programmons, il y a plusieurs couches, ou strates, de traductions (et un peu d'électronique). Nous ne rentrerons pas dans les détails dans ce cours (les UE d'architecture et de compilation le feront en partie), mais voici une ﬁgure qui représente ces différentes strates. Nous allons donc nous intéresser à la couche supérieure de ce schéma, celle des langages de programmation de haut niveau. Vous savez déjà probablement qu'il en existe plusieurs, et en fait, une multitude (dont le Python). Disons-en un peu plus sur cette multitude avant de passer au contenu algorithmique et technique. De l'universel au particulier On a vu superﬁciellement qu'à partir de la strate "langage machine", tout s'exprimait effectivement en binaire. C'est vrai pour les données, mais aussi pour les programmes ! Or, il est impossible pour le cerveau humain de lire/comprendre/écrire une telle diversité de signiﬁants encodés avec un alphabet aussi petit (on le rappelle, seulement deux lettres, 0 et 1 ). Surtout quand on sait qu'un des objectifs de l'informatique, c'est de traiter beaucoup d'information, ou effectuer beaucoup de calculs, de manière automatique et rapide. Très vite, les langages de programmation ont vu le jour : en 1954, le bal commence avec Fortran. C'est un an avant le choix du mot ordinateur pour parler de computer en français. Puis la création de nouveaux langages s'accelère, chacun ayant ses propres spéciﬁcités qui le rendent plus ou moins adapté à telle ou telle application. Par exemple, le COBOL, créé en 1959, est particulièrement robuste et ﬁable pour manipuler des grandes quantités de données structurées, et il est donc encore utilisé à ce jour dans les banques, les assurances et certaines administrations. Le langage C, quant à lui, permet de contrôler de manière assez ﬁne l'utilisation de la mémoire, et ainsi d'être très performant et économe en ressources. Cette liberté d'usage de la mémoire le rend peut-être moins accessible aux débutants, et même un peu dangereux si l'on est pas prudent ! En revanche, il permet justement d'apprendre la rigueur et d'approfondir certains concepts fondamentaux de programmation : c'est pourquoi vous vous plongerez dedans dès la L2, si vous choisissez le cursus informatique à l'issue de la L1. Enﬁn, le Python : né en 1991, il est beaucoup utilisé pour mettre en place des programmes rapidement. Il est (relativement) simple et peu verbeux, ce qui le rend particulièrement adapté à l'apprentissage de la programmation et à l'écriture de scripts (programme simple souvent conçu pour automatiser des tâches élémentaires). C'est lui qui est notre langage de référence dans ce cours, et que l'on va s'employer à maîtriser de plus en plus. La ﬁgure ci-dessous montre un échantillon de la généalogie des langages de programmation : Un mot sur les paradigmes de programmation À votre avis, pourquoi est-ce que le Caml est tout seul dans son coin ? La réponse vague : à cause des paradigmes de programmation. Cette expression un peu terriﬁante veut simplement dire qu'il existe plusieurs style de programmation, différentes manières de concevoir les programmes. Ainsi, dans la programmation impérative, on va indiquer une série d'instructions à exécuter étape par étape. Intuitivement, on explique quoi faire et comment en donnant des instructions précises. Les premiers langages de programmation sont dans ce style, mais pas seulement! Le C et le Python sont des exemples de langages qui peuvent mettre en oeuvre ce paradigme. En fait, la plupart des langages contiennent ce qu'il faut pour programmer de manière impérative, et on peut voir ce paradigme comme l'ensemble des briques de bases de l'algorithmique et de la programmation. C'est d'ailleurs pour cette raison que nous allons explorer cette façon de programmer dans ce cours. On peut aussi citer la programmation orientée objet, dans laquelle on est centré sur le concept d'objet qui a des propriétés et des méthodes pour agir et interagir avec l'extérieur et avec lui-même. Le Java (que vous verrez en L3) et le C++ (que vous pourrez voir en master) sont des langages de ce type. On peut aussi programmer en orienté objet avec Python, mais cela ne sera pas abordé dans ce cours. Enﬁn, la programmation fonctionnelle est elle centrée sur le concept de fonction : très proche des mathématiques, cette façon de penser peut être pertinente pour écrire des programmes très élégants. Le Caml fait partie de cette famille de langages, tout comme le Haskell que vous pourrez aborder en L3. ( vers la navigation ) Briques de base d'algorithmique Voici un aperçu des briques de base, qui vont nous occuper pour tout le semestre : Un programme informatique traite des données pour en extraire de l'information. Elles peuvent être déjà stockées quelque part, ou bien fournies par l'utilisateur auquel cas on parle d'entrées (avec le clavier, la souris, etc). Le programme peut également interagir avec l'utilisateur, par exemple en afﬁchant quelque chose à l'écran ou en commandant l'impression d'un document (les sorties). Penchons-nous maintenant sur la manière dont le programme traite les données : essentiellement, un programme consiste en une suite d'instructions, qui peuvent être répétées ou encore exécutées en fonction de certaines conditions, conformément aux structures de contrôle du programme (instructions conditionnelles, boucles for et while ). Enﬁn, certaines parties du programme peuvent être isolées dans des fonctions pour être réutilisées et améliorer la lisibilité du code. À quoi ça correspond en Python ? Tout cela est peut-être un peu abstrait. Nous approfondirons chaque notion au ﬁl de l'année, mais voici quelques indications pour vous donner une idée, à la lumière de ce que vous avez vu et verrez en TD et en TP (et éventuellement de ce que vous savez déjà de Python) : Données : c'est l'entrée du programme, par exemple les variables globales et les informations stockées dans des ﬁchiers Entrées-sorties : vous pouvez demander une entrée à l'utilisateur via la fonction input() , et afﬁcher des éléments à l'écran avec print(). Nous verrons des méthodes plus élaborées (par exemple via des interfaces graphiques) avec fltk. Opérations : les opérations arithmétiques + , - , * , / , etc ; logiques and , or , not ; la concaténation + ; et tout un tas d'opérations plus compliquées que nous verrons au ﬁl de l'année. Fonctions : vous avez déjà pu manipuler input et print pour les entrées-sorties, ainsi que int et str pour convertir en entier et en chaîne de caractère, nous en verrons de nombreuses autres ! Structures de contrôle : il s'agit des instructions conditionnelles if:... else:... , des boucles for... in... et des boucles while...:. Mais pas de panique, nous allons voir tout cela en détail en CM ! ( vers la navigation ) Un peu plus sur Python C'est parti pour expliciter les premières briques dans le langage Python. La suite est un catalogue présentant les outils et notions pratiques à connaître pour comprendre et écrire de premiers programmes en Python. Types de valeurs Toutes les valeurs en Python possèdent un type. Le type d'une valeur déﬁnit les opérations possibles. Les types de base sont : les nombres entiers ( int ) ou décimaux ( float ) les booléens ( bool ) les chaines de caractères ( str ) un type de valeur indéﬁnie ( NoneType ) Nombres entiers ( int ) In : 6 Out: 6 In : 12345 Out: 12345 In : -4 # un entier négatif Out: -4 In : 2 ** 1000 # un très très grand entier Out: 1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858 1275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954 1821530464749835819412673987675591655439460770629145711964776865421676604298316526243868372056680693 76 In : 0b101010 # un entier en binaire Out: 42 In : 0x2a # un entier en hexadécimal Out: 42 Nombres décimaux ( float ) In : 3.14 Out: 3.14 In : -1.5 Out: -1.5 In : 3 *.1 # un nombre décimal qui ne "tombe pas juste" Out: 0.30000000000000004 In : 12. Out: 12.0 In : 4.56e3 # notation scientifique Out: 4560.0 Booléens ( bool ) Ce type permet de représenter les deux valeurs de vérité « vrai » et « faux ». In : True # vrai Out: True In : False # faux Out: False Attention : Les majuscules/minuscules sont importantes : In : true # provoque une exception (une erreur) --------------------------------------------------------------------------- NameError Traceback (most recent call last) Cell In, line 1 ----> 1 true # provoque une exception (une erreur) NameError: name 'true' is not defined Chaînes de caractères ( str ) Une chaine de caractères est une succession de symboles (lettres, chiffres, ou autres) entre guillemet In [ ]: 'bonjour' # guillemets simples In [ ]: "hello !" # guillemets doubles In [ ]: "." # caractères non-latin In [ ]: # Chaînes longues """Ce plat est supposé être dégusté au petit-déjeuner mais convient aussi comme dessert. Les pancakes sont traditionnellement accommodés avec du sirop d'érable et une noix de beurre mais rien n'empêche de les dévorer au sucre, au jus de citron ou avec de la pâte à tartiner.""" Il faut faire un peu attention pour écrire une chaîne de caractères contenant des apostrophes ou des guillemets : In [ ]: "King's Landing" In [ ]: 'Mon nom est "Personne".' Caractères spéciaux : \n, \t, \', \", \\ In [ ]: "sauts\nde\nligne" In [ ]: print("sauts\nde\nligne") In [ ]: # tabulation, touche ⇥ print("Du\tsur\ntexte\t2 colonnes") In [ ]: print("D'autres symboles spéciaux : \' \" \\") Valeur indéﬁnie ( NoneType ) In [ ]: None # ça a l'air inutile mais en fait c'est bien pratique ( vers la navigation ) Opérations Le type d'un objet détermine les opérations qu'on peut lui appliquer. C'est un principe très important en Python. Opérations sur les nombres Addition ( a + b ), soustraction ( a - b ), multiplication ( a * b ), puissance ( a ** b ) sur deux int et produisant un int ou sur deux float et produisant un float ou sur un int et un float et produisant un float In [ ]: 4 + 5 In [ ]: 4 - 5.5 In [ ]: 4. * 5. In [ ]: 4 ** 2 In [ ]: 4 ** 0.5 Division "réelle" ( a / b ) : produit toujours un float In [ ]: 1 / 3 # valeur approchée ! In [ ]: 4 / 2 # ne donne pas un entier ! Division euclidienne : quotient : a // b reste, ou modulo : a % b les deux en même temps : divmod(a, b) si a et b de type int , produisent un int , sinon un float In [ ]: 7 // 2 In [ ]: 7 % 2 In [ ]: divmod(7, 2) In [ ]: 4 // 2 # cette fois c'est un entier... In [ ]: 4 % 2 # le reste est nul car 4 est pair (divisible par 2) In [ ]: 4.0 // 1.75 # donne un float ! In [ ]: 4.0 % 1.75 Les opérations suivent les règles de priorité usuelles : In [ ]: 4 + 2 * 1.5 On peut aussi utiliser des parenthèses : In [ ]: (4 + 2) * 1.5 Opérations sur les chaînes de caractères Concaténation : s + t In [ ]: 'Gustave' + 'Eiffel' In [ ]: 'Gustave' + ' ' + 'Eiffel' Répétition : s * a In [ ]: 'Hip ' * 3 + 'Hourra !' In [ ]: ('Hip ' * 3 + 'Hourra ! ') * 2 Beaucoup d'autres opérations (sur les chaînes, les nombres...) : on verra ça plus tard Le sens de * et + n'est pas le même sur les chaînes et sur les nombres ! Conversions / transformations de type On a parfois besoin de convertir une valeur d'un type à l'autre N'importe quel objet en chaîne avec la fonction str In [ ]: "J'ai " + 10 + ' ans.' In [ ]: "J'ai " + str(10) + ' ans.' Un float , ou parfois un str en int In [ ]: int(3.5) # float vers int In [ ]: int('14') # str vers int In [ ]: int('3.5') # impossible : deux conversions (str -> float -> int) In [ ]: int('deux') # impossible : ne représente pas un nombre Un int , ou parfois un str en float In [ ]: float(3) # int vers float In [ ]: float('14.2') # str vers float In [ ]: float('3,5') # impossible : virgule au lieu de point In [ ]: float('bonjour') # impossible : ne représente pas un nombre Déterminer le type d'une expression Grâce à la fonction prédéﬁnie type In [ ]: type("salut") In [ ]: type(4 / 2) In [ ]: type(2 * 4.8) Exercice : valeur et type d'une opération Pour chacune des instructions suivantes :. donner le type et le résultat de l'expression donnée ;. vériﬁer le résultat. On pourra utiliser la fonction type si nécessaire pour vériﬁer le type du résultat. In [ ]: 2 * 5 In [ ]: 2 + 1.5 In [ ]: 2.0 * 4 In [ ]: '2.0' * 4 In [ ]: '2.0' * 4.0 In [ ]: 4 / 2 In [ ]: 4.0 / 2 In [ ]: 5 / 2 In [ ]: 5 % 2 In [ ]: 5 // 2 In [ ]: int(4.0) / 2 In [ ]: str(4) / 2 In [ ]: 'toto' + str(4) In [ ]: float(4) * 2 In [ ]: int(str(4) * 2) In [ ]: 'toto' + 'titi' In [ ]: int('toto') + 'titi' In [ ]: int(2.0) * 4 In [ ]: 'toto' * str(4) In [ ]: int('1.25') ( vers la navigation ) Variables et affectations Une variable est un nom servant à désigner une valeur Une variable est remplacée par sa valeur dans les calculs Seules les opérations du type de la valeur sont permises L'affectation est le fait de lier une valeur à une variable Syntaxe : nom = une expression Attention : Ce n'est pas du tout le = des mathématiques, il faut le lire comme "prend la valeur" In [ ]: x = 3 y ='UGE' z = x + 2 x, y, z On peut réaffecter une variable (même avec une valeur d'un type différent) In [ ]: x In [ ]: x = 'UGE' In [ ]: x On ne peut utiliser une variable que si elle a été préalablement déﬁnie ! In [ ]: foo ( vers la navigation ) Modèle de mémoire de Python Modèle de mémoire : une image simpliﬁée de la manière dont fonctionne la mémoire de l'interpréteur Python Deux zones principales : la zone des données (le « tas », en anglais heap) la zone des espaces de noms (la « pile », en anglais stack) Dans Python Tutor : pile à gauche, tas à droite Le tas Le tas est comme un très gros cahier dans lequel sont décrits les objets manipulés par un programme Chaque objet décrit dans le cahier commence à un certain numéro de page, qu'on appelle son adresse Certaines pages sont blanches, d'autres sont remplies La pile La pile est comme l'index du cahier À chaque variable est associé le numéro de page d'un objet Un groupe de variables et les numéros de page correspondants est appelé espace de noms La pile contient l'espace de noms global, contenant les noms déﬁnis par nos programmes (en réalité la pile contient aussi d'autres espaces de noms, on en reparlera) In [ ]: %%nbtutor -r -f x = 3 y ='UGE' z = x + 2 La notion d'état L'état de l'interpréteur pendant l'exécution c'est le numéro de la ligne suivante à exécuter dans le programme le contenu de diverses variables internes de l'interpréteur le contenu de la pile (donc tous les espaces de noms) le contenu du tas (donc toutes les données du programme) à un moment donné. Les instructions modiﬁent généralement l'état. Étapes d'une affectation Affectation simple In [ ]: x = 40 + 2. Évaluation de l'expression à droite du = (ici 42 ) La valeur 42 de type int est stockée dans le tas (écrite sur une page du cahier). Création du nom x dans l'espace de noms (sauf s'il existe déjà) On ajoute x à la pile (on ajoute une ligne pour x à l'index du cahier). Création du lien entre variable et valeur L'adresse de l'objet 42 est associée à la variable x (on écrit dans l'index le numéro de la page contenant l'objet 42 à x ) Deuxième exemple In [ ]: y = x Dans cet exemple le x en partie droite de l'affectation désigne la valeur actuellement associée à la variable x !. Calcul du membre droit après remplacement de chaque variable par la valeur associée (ici x remplacé par 42 ). Création du nom y (sauf si déjà créé). Création du lien entre y et 42 Troisième exemple In [ ]: x = x + 1 Dans cet exemple, le x de gauche désigne le nom x lui-même, mais celui de droite désigne la valeur actuellement associée à x. Calcul du membre droit après remplacement de chaque variable par la valeur associée (ici x remplacé par 42 , résultat : 43 ). Nom x déjà existant, création du lien entre x et 43 Piège ! Que vaut maintenant y ? In [ ]: y Même si x et y désignaient avant le même objet (la même adresse, le même numéro de page), changer la page que désigne x n'a aucun effet sur y ! On n'a pas modiﬁé l'objet 42, qui est toujours là ! In [ ]: %%nbtutor -r -f x = 40 + 2 y = x x = x + 1 Remarque : L'instruction x = x + 1 peut aussi s'écrire x += 1. On appelle cela une incrémentation de x. In [ ]: x += 1 De même, x *= 2 est une version plus concise de x = x * 2. Dernier exemple In [ ]: x = -6.5 Quelques points de détail On peut réaffecter une valeur de type différent à une variable (comme dans le dernier exemple) En cas de réaffectation, le lien précédent est oublié Quand aucun lien n'existe vers un objet, il est "détruit" par le ramasse-miettes ou garbage collector (la page est effacée !) Exercice : état de la mémoire après une suite d'affectations Dessiner l'état de la mémoire à l'issue des instructions suivantes : In [ ]: x = 2 y = 3 x += y y *= 2 Nommage des variables Règles de nommage des variables : Commencent par une lettre, suivie de lettres et de chiffres Le caractère underscore '_' est considéré comme une lettre Éviter les caractères spéciaux (accents, cédille, etc.) Les mots réservés (ou mots-clés) de Python sont interdits Il y a aussi des conventions (vues plus tard) Exemples : _ex2 Ex2mpl1 Contre-exemple : 2024eiffel Mots-clés et autres mots réservés Les mots suivants sont réservés pour le langage : False await else import pass None break except in raise True class finally is return and continue for lambda try as def from nonlocal while assert del global not with async elif if or yield https://docs.python.org/fr/3/reference/lexical_analysis.html#keywords Exercice : nommage de variables Indiquer parmi les mots suivants ceux qui ne sont pas des noms valides pour une variable : bonjour Hi! au revoir oui Ciao NON byeBye7 6hello6 abc def 6hello6 _upem_ good_morning __repr__ good-afternoon f() ( vers la navigation ) Saisie et afﬁchage Fonction de saisie : x = input("Veuillez rentrer...") L'utilisateur tape une ligne au clavier La ligne est stockée sous forme de chaîne de caractères ( str ) Cette valeur peut ensuite être affectée à une variable (ici x ) Le message d'invite pour l'utilisateur est facultatif https://docs.python.org/fr/3/library/functions.html#input In [ ]: nb_personnes_ref = 2 nb_convives = input("Combien de personnes ? ") rapport = nb_convives / nb_personnes_ref In [ ]: nb_personnes_ref = 2 # on convertit immédiatement le texte saisi en int : nb_convives = int(input("Combien de personnes ? ")) rapport = nb_convives / nb_personnes_ref Fonction d'afﬁchage : print(x) Afﬁche dans le terminal la chaîne de caractères associée à x On peut afﬁcher plusieurs valeurs à la suite : print(x, y, z,...) Appelle automatiquement la fonction str sur chacun de ses arguments S'il y a plusieurs arguments, insère automatiquement des espaces Passe automatiquement à la ligne https://docs.python.org/fr/3/library/functions.html#print In [ ]: nb_personnes_ref = 2 # on convertit immédiatement le texte saisi en int : nb_convives = int(input("Combien de personnes ? ")) rapport = nb_convives / nb_personnes_ref print("Je multiplie toutes les quantités par", rapport) Remarque : Il existe de nombreuses possibilités pour l'afﬁchage de texte, consulter la documentation ofﬁcielle pour plus de détails. ( vers la navigation ) Structures de contrôle Les programmes et algorithmes les plus simples consistent à exécuter des instructions les unes après les autres, en séquence. C'est néanmoins très vite limité : il arrive fréquemment qu'on ait envie d'agir d'une certaine façon dans un cas et d'une autre dans un autre. Typiquement, on voudrait pouvoir continuer le programme de manière adaptée à une entrée de l'utilisateur. On va donc s'intéresser aux structures dites conditionnelles. Ces structures permettent de "brancher" dans le code en fonction de l'évaluation d'une condition, que l'on exprime sous forme d'expression booléenne. Faisons donc d'abord un point sur ce type très important d'expressions : Expressions booléennes Les instructions conditionnelles sont écrites à l'aide d'expressions booléennes, c'est à dire d'expressions qui s'évaluent en un valeur de type bool ( True ou False ). Elles peuvent contenir des opérateurs de comparaison, des opérateurs logiques, etc. Opérateurs de comparaison a b # a strictement supérieur à b a et b sont des expressions elles doivent s'évaluer en des valeurs de même type (sauf exceptions) Les opérateurs de comparaison fonctionnent sur de nombreux types de valeurs Sur les int et float : ordre habituel sur les nombres Sur les str : ordre lexicographique (dictionnaire) Sur d'autres types qu'on verra plus tard Rappel : on ne peut pas ordonner des valeurs de types différents (sauf des nombres) ! Égalité ou inégalité a == b # a égal à b a != b # a différent de b a et b sont des expressions elles peuvent être de types différents Les opérateurs == et != acceptent des opérandes de types différents renvoie généralement False si les opérandes sont de types différents sauf parfois entre nombres Attention ! Ne pas confondre l'opérateur d'égalité ( == ) avec la syntaxe de l'affectation ( = ) ! In [ ]: 17 % 2 == 1 In [ ]: a = -5 a != abs(a) In [ ]: 1.0 == 3 - 2 # l'égalité fonctionne aussi avec les float... In [ ]: 0.3 == 3 * 0.1 # mais réserve parfois des surprises Les opérateurs == et != acceptent des opérandes de types différents renvoie généralement False si les opérandes sont de types différents sauf parfois entre nombres In [ ]: 2 == '2' In [ ]: 'bonjour' != None In [ ]: 2 == 2.0 # Cas particulier : vrai car float(2) == 2.0 Attention ! Ne pas confondre l'opérateur d'égalité ( == ) avec la syntaxe de l'affectation ( = ) ! ( vers la navigation ) Opérateurs logiques On peut combiner plusieurs expressions booléennes a et b à l'aide d'opérateurs logiques, inspirés de la logique mathématique. On peut résumer le comportement de ces opérateurs à l'aide de tableaux, appelés tables de vérité. Négation L'expression not a vaut True si a s'évalue en False , et False sinon (correspond à ¬a). a not a True False False True Conjonction L'expression a and b vaut True si a et b s'évaluent toutes les deux en True , et False sinon (correspond à a ∧ b). a b a and b True True True True False False False True False False False False Disjonction L'expression a or b vaut True si a s'évalue en True ou b s'évalue en True , et False sinon (correspond à a ∨ b). a b a or b True True True True False True False True True False False False In [ ]: not (3 + 4 != 7) In [ ]: 4 < 1 or 'Bonjour' >= 'Au revoir' En réalité les opérateurs and et or ont un comportement un peu spécial appelé évaluation séquentielle : on n'évalue le deuxième opérande que si c'est nécessaire pour déterminer le résultat. a and b est à peu près équivalent à b if a else a a or b est à peu près équivalent à a if a else b Cela signiﬁe qu'on n'évalue pas toujours b dans a and b et dans a or b. Par exemple : In [ ]: 1/0 # erreur : division par 0 In [ ]: True or 1/0 == 1 # ne provoque pas d'erreur ! In [ ]: False and 1/0 == 1 # ne provoque pas d'erreur ! En Python, presque tout objet possède une valeur de vérité et peut s'utiliser comme un booléen... mais les règles sont un peu complexes. Par exemple : les nombres égaux à 0 sont interprétés comme "faux" la chaîne vide est interprétée comme "faux" la valeur None est interprétée comme "faux", etc. Tout le reste est interprété comme "vrai" Si on combine ces deux aspects du langage, ça peut donner des choses assez surprenantes... In : 'patate' and 'courgette' Out: 'courgette' In : 'patate' or 'courgette' Out: 'patate' Ce comportement est largement hors programme et non exigible ! ( vers la navigation ) Quelques règles utiles Lois de De Morgan dire "non (a ou b)" revient à dire "(non a) et (non b)" dire "non (a et b)" revient à dire "(non a) ou (non b)" En Python : not (a and b) == (not a) or (not b) # vrai pour tous a et b not (a or b) == (not a) and (not b) # vrai pour tous a et b Distributivité la conjonction est distributive sur la disjonction la disjonction est distributive sur la conjonction En Python : a and (b or c) == (a and b) or (a and c) # vrai pour tous a, b et c a or (b and c) == (a or b) and (a or c) # vrai pour tous a, b et c Commutativité a and b est (presque) équivalente à b and a (mais elle change l'ordre d'évaluation) a or b est (presque) équivalente à b or a (idem) Absorption a or True est (presque) équivalente à True True or a est équivalente à True a and False est (presque) équivalente à False False and a est équivalente à False Invariance a and True est (presque) équivalente à a True and a est équivalente à a a or False est (presque) équivalente à a False or a est équivalente à a Égalité et négation not a == b est équivalent à a != b not a != b est équivalent à a == b Comparaisons et opérateurs logiques a = b est équivalent à a > b or a == b Comparaisons et négation not a = b ou encore b b est équivalent à a = a not a >= b est équivalent à a a In [ ]: x = -1 inf, sup = 0, 10 x >= inf and x sup In [ ]: x = 1 inf, sup = 0, 10 not (x < inf or x > sup) In [ ]: x = 12 inf, sup = 0, 10 not (x >= inf and x c In [ ]: a, b, c = 10, 2, 6 a + b < 2 * c In [ ]: a, b, c = 10, 2, 6 a - b == b + c In [ ]: a, b, c = 10, 2, 6 (a > b and a > c) or (b > a and b > c) In [ ]: a, b, c = 10, 2, 6 a a and b > c) ( vers la navigation ) Instructions conditionnelles Cas simple : Conditionnelle Si On peut maintenant modiﬁer le ﬂot d'instructions selon la valeur d'expressions booléennes, ou conditions : Si une certaine condition est vraie, exécuter un certain groupe (ou bloc) d'instructions Sinon, passer directement à la suite du programme La syntaxe d'une instruction conditionnelle est : # début if condition: # bloc # d'instructions # indenté # suite (*) Ici condition est une expression booléenne Les instructions du bloc v sont exécutées uniquement si condition est évaluée à True Dans tous les cas, l'exécution reprend à l'instruction suivant le bloc indenté (ligne suite (*) ) Exemple : pile ou face ? Un programme qui :. tire un nombre au hasard entre 0 et 1. afﬁche pile s'il a tiré 1 , face s'il a tiré 0 In [ ]: from random import randint # randint permet de tirer un nombre aléatoire tirage = randint(0,1) print(tirage) if tirage == 1: print("pile") if tirage == 0: print("face") Exemple : mettre deux chaînes dans l'ordre Supposons qu'il existe deux variables a et b désignant des str. Écrire un bout de programme qui modiﬁe ces variables pour que a désigne la plus petite chaîne et b la plus grande (dans l'ordre lexicographique) In [ ]: a = input() b = input() if a > b: # on intervertit les valeurs temp = a # variable temporaire a = b b = temp print(a, b) In [ ]: a = input() b = input() if a > b: # variante a, b = b, a print(a, b) La notion de bloc Sur cet exemple, on a vu un groupe de lignes commençant par des espaces, appelé bloc. Un bloc est utilisé pour regrouper plusieurs instructions dépendant de la même condition. Un tel groupe d'instructions est appelé un bloc Le décalage du début de ligne est appelé indentation Un bloc se termine quand une ligne moins indentée apparaît (sur l'exemple : print(a, b) ) Pour indenter la ligne courante : touche "tabulation" (⇥) Pour désindenter une ligne : "Shift + tabulation" (⇧ + ⇥) Changer l'indentation change le sens du programme (essayez !) In [ ]: from random import randint # randint permet de tirer un nombre aléatoire tirage = randint(0,1) print(tirage) if tirage == 1: print("Le résultat est :") print("pile") if tirage == 0: print("Le résultat est :") print("face") Erreurs fréquentes liées à l'indentation : In [ ]: if a > b # oubli des deux points (:) temp = a a = b b = temp In [ ]: if a > b: temp = a a = b b = temp # ligne pas assez indentée In [ ]: if a > b: temp = a a = b b = temp # ligne trop indentée In [ ]: if a > b: a, b = b, a # oubli d'indentation Conditionnelles Si... Sinon... On peut ajouter un second bloc d'instructions Si une certaine condition est vraie, exécuter le premier bloc Sinon, exécuter le second Enﬁn, continuer l'exécution normale du programme Syntaxe : # début if condition: # bloc v else: # bloc f # suite Ici condition est une expression booléenne Seul l'un des deux blocs d'instructions, v ou bien f, est exécuté Le bloc v uniquement si condition est évaluée à True Le bloc f uniquement si condition est évaluée à False Dans tous les cas, reprise à l'instruction suivant le bloc f Exemple : division euclidienne In [ ]: dividende = int(input("Donnez moi un dividende : ")) diviseur = int(input("Donnez moi un diviseur : ")) if diviseur != 0: quotient = dividende // diviseur reste = dividende % diviseur print(dividende, '=', quotient, '*', diviseur, '+', reste) else: print('Erreur : division par zéro') Exemple : pile ou face ? In [ ]: from random import randint # randint permet de tirer un nombre aléatoire tirage = randint(0,1) print(tirage) if tirage == 1: print("pile") if tirage == 0: print("face") In [ ]: from random import randint # randint permet de tirer un nombre aléatoire tirage = randint(0,1) print(tirage) if tirage == 1: print("pile") else: # Dans ce cas, tirage vaut nécessairement 0 print("face") Exercice Écrire un programme qui permet de jouer à pile ou face :. Demander à l'utilisateur de saisir 1 pour pile et 0 pour face. Tirer un nombre au hasard, l'afﬁcher et afﬁcher Gagné ! ou Perdu ! en fonction du résultat On pourra améliorer le programme pour permettre de saisir directement pile ou face plutôt que 1 ou 0. In [ ]: from random import randint nombre_choisi = int(input("Pile (1) ou face (0) ? ")) tirage = randint(0,1) if tirage == nombre_choisi: print("Gagné !") else: print("Perdu !") In [ ]: from random import randint choix = input("pile ou face ? ") if choix == "pile": nombre_choisi = 1 else: nombre_choisi = 0 tirage = randint(0,1) if tirage == 1: print("Le résultat est pile.") else: print("Le résultat est face.") if tirage == nombre_choisi: print("Gagné !") else: print("Perdu !") Exercices. Écrire un programme qui saisit un nombre entier et afﬁche positif si l'entier est positif ou nul et negatif sinon.. Écrire un programme qui saisit deux nombres entiers et afﬁche le plus grand des deux. In [ ]: entier = int(input("Donnez moi un entier : ")) if entier >= 0: print("positif") else: print("negatif") In [ ]: entier1 = int(input("Donnez moi un premier entier : ")) entier2 = int(input("Donnez moi un deuxième entier : ")) print("L'entier le plus grand est", end = " ") if entier1 > entier2: print(entier1) else: print(entier2) Conditionnelles composées Cette construction peut être imbriquée : # début if : if : # bloc v1v2 else: # bloc v1f2 # suite 2 else: # bloc f1 # suite 1 Toutes les variantes sont possibles — si chaque else correspond à un if de même indentation ! Exemple : pile ou face, deux fois Écrire un programme qui tire deux fois à pile ou face et afﬁche Gagné si les deux tirages sont pile , Perdu sinon. In [ ]: from random import randint tirage1 = randint(0,1) print("Premier tirage :", tirage1) if tirage1 == 1: tirage2 = randint(0,1) print("Second tirage :", tirage2) if tirage2 == 1: print("Gagné") else: print("Perdu") else: print("Perdu") Exemple : discriminant On suppose qu'il existe trois variables a , b et c désignant des nombres. On veut déterminer le nombre de solutions réelles de l'équation a x2 + b x + c = 0. Les cas suivants sont à considérer : si a = b = c = 0, il y a une inﬁnité de solutions si a = b = 0 et c ≠ 0, il n'y a pas de solution si a = 0 et b ≠ 0, il y a exactement une solution 2 sinon, on calcule le discriminant Δ = b - 4 ac et, ▪ si Δ < 0, il n'y a pas de solution ; ▪ si Δ = 0, il y a exactement une solution ; ▪ sinon Δ > 0 et il y a exactement deux solutions. Écrire un programme qui demande à l'utilisateur de saisir au clavier les trois valeurs a , b et c et qui calcule et afﬁche le nombre de solutions réelles de l'équation du second degré associée. In [ ]: a, b, c =... # Calcul et affichage du nombre de solutions if a == 0: if b == 0: if c == 0: print("Une infinité de solutions") else: print("Pas de solution") else : print("Une solution") else: delta = b ** 2 - 4 * a * c if delta < 0: print("Pas de solution") else: if delta == 0: print("Une solution") else: print("Deux solutions") Conditionnelles enchaînées Cas particulier où le bloc else contient seulement un autre if : le mot-clé elif Le code... # début if : # bloc **v1** else: if : # bloc **f1v2** else: # bloc **f1f2** # suite... s'écrit aussi : # début if : # bloc **v1** elif : # bloc **f1v2** else: # bloc **f1f2** # suite On peut ainsi enchaîner autant de conditions qu'on le souhaite, lorsque les cas ne se recouvrent pas : # début if : # bloc **v1** elif : # bloc **f1v2** elif : # bloc **f1f2v3** else: # bloc **f1f2f3** # suite Exemple : pile ou face, deux fois (variante) Écrire un programme qui tire deux fois à pile ou face et afﬁche Gagné si les deux tirages sont différents ( pile puis face ou bien face puis pile ) et afﬁche Perdu sinon. In [ ]: from random import randint tirage1 = randint(0,1) print("Premier tirage :", tirage1) tirage2 = randint(0,1) print("Second tirage :", tirage2) if tirage1 == 1 and tirage2 == 1: print("Gagné") elif tirage1 == 0 and tirage2 == 0: print("Gagné") else: print("Perdu") In [ ]: # Une variante from random import randint tirage1 = randint(0,1) print("Premier tirage :", tirage1) tirage2 = randint(0,1) print("Second tirage :", tirage2) if tirage1 == 1 and tirage2 == 1 or tirage1 == 0 and tirage2 == 0: print("Gagné") else: print("Perdu") In [ ]: # Une autre variante from random import randint tirage1 = randint(0,1) print("Premier tirage :", tirage1) tirage2 = randint(0,1) print("Second tirage :", tirage2) if tirage1 == tirage2: print("Gagné") else: print("Perdu") ( vers la navigation ) Boucles Comment faire si l'on veut répéter une instruction ? Exemple : pile ou face, rejouer tant qu'on perd Écrire un programme qui nous fait rejouer à pile ou face tant qu'on perd. In [ ]: # Un premier essai from random import randint tirage = randint(0,1) nombre_choisi = int(input("Pile (1) ou face (0) ? ")) if tirage == nombre_choisi: print("Gagné") else: print("Perdu. Essaye encore.") tirage = randint(0,1) nombre_choisi = int(input("Pile (1) ou face (0) ? ")) if tirage == nombre_choisi: print("Gagné") #... # Ça peut durer longtemps ! In [ ]: # Un deuxième essai from random import randint gagne = False while not(gagne): tirage = randint(0,1) nombre_choisi = int(input("Pile (1) ou face (0) ? ")) if tirage == nombre_choisi: print("Gagné") gagne = True else: print("Perdu. Essaye encore.") In [ ]: # Une variante from random import randint tirage = 0 nombre_choisi = 1 while tirage != nombre_choisi: tirage = randint(0,1) nombre_choisi = int(input("Pile (1) ou face (0) ? ")) if tirage != nombre_choisi: print("Perdu. Essaye encore.") print("Gagné !") Exemple : pile ou face, rejouer Écrire un programme qui nous fait rejouer à pile ou face tant qu'on perd et qu'on veut rejouer. In [ ]: from random import randint rejouer = True perdu = True while rejouer and perdu: tirage = randint(0,1) nombre_choisi = int(input("Pile (1) ou face (0) ? ")) if tirage == nombre_choisi: perdu = False else: print("Perdu.") reponse = input("Voulez-vous rejouer ? [o/n]") if reponse == "n": rejouer = False if not perdu: print("Gagné") Exemple : Compter de 1 à 100 In [ ]: # à corriger ! i = 0 while i < 100: print(i+1, end=" ") i = i + 1 # ou bien : i += 1 Exercice. Compter de 1 à 100 par pas de 2, de 3.... Compter 100 à 1 par pas de -1, de -2.... Compter de a à b par pas de c pour a , b et c trois entiers quelconques. Dans quels cas a-t-on des problèmes ? In [ ]: i = 1 pas = 4 while i 0: print(i, end=" ") i = i + pas # ou bien : i += 1 In [ ]: a, b, c = 27, 42, 2 i = a pas = c while i 0: r = a % b a = b b = r print("le pgcd de", a0, "et", b0, "est", a) Pourquoi l'algorithme termine-t-il ? on peut choisir comme variant la valeur de b initialement, b > 0 la boucle ne s'exécute pas si b 0 commentaire 0 3 0 42 '' 42 × 2 = 42 0 True avant la première itération 8 1 21 0 '0' 21 × 21 = 42 0 True ﬁn de la 1e itération 8 2 10 1 '10' 10 × 22 = 40 2 True 3 8 3 5 0 '010' 5 × 2 = 40 2 True 8 4 2 1 '1010' 2 × 24 = 32 10 True 8 5 1 0 '01010' 1 × 25 = 32 10 True 6 8 6 0 1 '101010' 0 × 2 = 32 42 False sortie de la boucle Invariant : res contient les (nombre d'itérations) derniers chiffres de la conversion de n en binaire k × 2(itér) + (valeur de res) = n Variant : n - temp initialement ≥ 0, diminue à chaque tour Exercice : dresser le tableau de valeurs pour n = 25 adapter l'algorithme pour convertir n en base 4, puis en base b < 10 ref : Compter comme les Shadoks Exercice : quel est l'invariant de boucle pour l'algorithme d'Euclide ? ( vers la navigation ) Boucles imbriquées On peut écrire une boucle à l'intérieur d'une autre boucle La syntaxe d'une double boucle while : # début while condition1: # début corps 1 while condition2: # corps 2 # fin corps 1 # suite Exemple : table d'addition But : afﬁcher toutes les additions de nombres inférieurs à n In [ ]: m = 3 n = 11 a = 0 # hors de la boucle externe ! while a < m: b = 0 # dans la boucle externe ! while b < n: print(a, '+', b, '=', a+b) b += 1 # dans la boucle interne ! a += 1 # dans la boucle externe ! Exercices :. afﬁcher toutes les additions a + b = c pour a entre 0 et n et b entre 0 et m. essayer d'écrire le programme en utilisant une seule boucle (non recommandé en temps normal !) Exemple : compter jusqu'à 59, dix nombres par ligne In [ ]: # paramètres limite = 60 nb_colonnes = 7 courant = 0 while courant < limite: colonne = 0 while colonne < nb_colonnes and courant < limite: print(courant, end = '\t') colonne += 1 courant += 1 print() # affiche un retour à la ligne Exercice : (pas si évident) faire en sorte que les nombres successifs apparaissent sur une même colonne In [ ]: # paramètres limite = 37 nb_colonnes = 10 nb_lignes = limite // nb_colonnes + 1 ligne = 0 while ligne < nb_lignes: colonne = 0 courant = ligne while courant < limite and colonne < nb_colonnes: print(courant, end = '\t') courant += nb_lignes colonne += 1 ligne += 1 print() # affiche un retour à la ligne ( vers la navigation ) Contrôle de boucle Tout ce qui suit est non exigible en contrôle. Instruction break On peut sortir prématurément d’une boucle while Instruction break dans le corps (en général dans une conditionnelle) Force une sortie de boucle et passe directement à la suite du programme On ne réévalue pas la condition du while Exemple : saisie contrôlée sans duplication de l'instruction input : In [ ]: while True: note_cc1 = float(input('Note du premier contrôle : ')) if 0

1-briques-de-base-1.pdf

Document Details

Related

Full Transcript

Upgrade to continue