P1.5 boucles non bornées

Bases en Python : boucle tant que 

Un exemple

Les boucles for que nous avons vues jusqu'ici sont bornées : on sait combien de fois la boucle sera exécutée (parfois la boucle pourra être interrompue, mais disons qu'on sait combien de fois au maximum le boucle sera exécutée).

Exemple : la boucle while
Jusqu'à ce que l'ai un 6...

Examinons le problème suivant :

Je lance un dé à 6 faces, et je compte combien de fois je dois le lancer avant d'obtenir un 6.

Dans cette situation, on ne sait pas à l'avance combien de fois on devra relancer le dé, on ne sait même pas donner un nombre maximum. On va lancer Tant que on obtient pas un 6, et arrêter dès qu'on en obtient un.

Dans ce cas on ne peux pas faire une boucle for, on utilise la boucle while :

Nous n'avons parlé jusqu'ici que de variables qui sont des nombres ou des chaînes de caractères. Ici nous allons avoir besoin de variables booléennes.
Voir qui était george Boole
Les variable booléennes sont des variables qui n'ont que 2 valeurs possibles : Vrai ou Faux

En anglais (donc dans tous les langages informatiques) c'est True ou False.

Coder en python la solution du problème

Exemple

Exécutez le code plusieurs fois et vérifiez que le nombre de lancés est variable.


Un mauvais exemple

Il n'est pas convenable d'utiliser une boucle while quand on connaît le nombre d'itérations requis.

Exemple

Ce code est parfaitement fonctionnel mais l'utilisation de tant que est injustifiée. Elle rend le code plus difficile à lire, et si on oublie le i = i + 1 on court à la catastrophe !

Exemple

Lorsque l'on peut, on utilise une boucle `for`.  
Ici tout simplement :

Exemple

Si vous avez déjà étudié les listes en Python, vous pouvez regarder cet autre mauvais exemple

Il n'est pas convenable d'utiliser une boucle while quand on connaît le nombre d'itérations requis.

Exemple

Ce code est parfaitement fonctionnel mais l'utilisation de Tant que est injustifiée. Elle rend le code plus difficile à lire, et si on oublie le i = i + 1 :

Exemple

A votre avis.... que va-t-il se passer ? Vous pouvez vérifier...

Très important

Avec les boucles while il y a un risque que la boucle ne s'arrête jamais. Dans ce cas le programme ne se termine pas. Ce genre de bug est assez fréquent. Pour s'en prémunir il est indispensable de vérifier soigneusement que la condition d'arrêt sera atteinte au cours des itérations.

Exercices

compte a rebourd
Exemple

Voici la structure générale:

La première ligne est une boucle while «condition»: où «condition» est une expression qui retourne True ou False (une expression Booléenne, comme pour l'instruction if). Ensuite, on utilise un block indenté (comme pour une instruction if) qui contient des instructions que l'on veut répéter. Cela s'appelle le corps de la boucle. Quand vous exécutez le programme, les étapes suivantes sont répétées:

début

  • La condition est testée.
  • Si la condition est True alors le corps de la boucle est exécuté et ensuite nous revenons au début
  • Si la condition est évaluée à False, la boucle s'arrête.
Exercice de code
Modifiez l'exemple ci-dessus pour obtenir un programme qui compte de manière croissante de 1 à 10 et qui écrit à la fin: Décollage!
puissances de 2
Exercice de code
Ecire un code qui trouve le plus petit entier n tel que 2**n soit supérieur à un entier N.
Le nombre N sera généré automatiquement lors de l'exécution de votre code.
suite de grelon
Exercice de code : suite de grelon
Ecire un code qui demande un nombre entier positif puis, tant que cet entier n'est pas égal à 1 :
  • le divise par deux s'il est pair
  • le multiplie par 3 et ajoute 1 s'il est impair
Un nombre n est pair lorsque n%2 est égal à 0
Un nombre n est impair lorsque n%2 est égal à 1
En effet n%2 renvoie le reste de la division euclidienne de n par 2.
Attention : // est la division entière qui est utilisée ici.
6 / 2 renvoie 3.0
6 // 2 renvoie 3
7 / 2 renvoie 3.5
7 // 2 renvoie 3

P1.2 Premières boucles

Les boucles en python

première boucle

Voici un code très simple :

Exemple

Mais à quoi sert la variable i ? En fait, dans le cas de ce code très simple, i ne sert à rien ! i est un compteur de la boucle : une variable qui augmente de 1 à chaque passage. Au départ, i vaut 0, puis 1, puis 2.

Vérifions cela, en demandant d'afficher la valeur de i dans la boucle :

Exemple

Et une fois sorti de la boucle, est-ce que i vaut quelque chose ? Regardons !

Exemple
Avec une variable définie en dehors de la boucle

Souvent une boucle va effectuer des opération en utilisant des variables qui ont déjà une valeur en dehors de cette boucle, et qui seront modifiées durant l'exécution de la boucle.

Voyons un exemple simple :

Exemple

Avant le début de la boucle, a vaut 1.
Au premier passage dans la boucle, a=a+1 (donc a vaut 2) avant qu'on affiche sa valeur.
Au second passage dans la boucle, a=a+1 (donc a vaut 3) avant qu'on affiche sa valeur.
Au 3ème passage dans la boucle, a=a+1 (donc a vaut 4) avant qu'on affiche sa valeur.
A la sortie de la boucle a vaut toujours 4 (on ne l'a pas modifiée).

Attention !

Regardons ce code, très légèrement différent du précédent ;

Exemple

Cette fois, on affiche la valeur de a AVANT de l'augmenter. Du coup, au 1er passage, a vaut 1 et on fait a=a+1 après le print.
Du coup, au 3ème passage on affichera a qui vaut 3 mais on ajoutera encore 1 avant de sortir de la boucle.

Exercice mêlé : code en bouillie
Remet les lignes dans le bon ordre, ce code doit afficher les multiples de 10 de 10 à 100.
  • a = a + 10
  • a = 10
  • print(a)
  • print(a)
  • for i in range(9):

Les accumulateurs - La règle des 3I

Dans de nombreux cas, une boucle est accompagnée d'un accumulateur qui suit la règle des 3i.

L'accumulateur est la variable qui nous sert à calculer quelques chose. Par exemple, pour calculer la somme des entiers de 1 à 10, je défini une variable, que je peux appeler somme, qui à la fin de la boucle sera égale au résultat souhaité.

Pour faire cela je dois :

  1. Initialisation :Avant la boucle, je met somme à 0 ← choix de la valeur de départ
  2. Itération On va ajouter chaque entier en allant de 1 à 10← choix des bornes de la boucle de .. à ...
  3. Instructions : Dans la boucle, j'ajoute i à la somme : somme = somme + i← que doit on faire à chaque itération
Exemple
Exemple d'utilisation d'un accumulateur : faire la somme des valeurs.

L'initialisation n'est pas toujours mettre à 0. Par exemple, si je veux calculer le produit des entiers de 1 à 10:

  • Initialisation : je vais initialiser une variable (cette fois ci, je l'appellerais produit mais ce n'est évidement pas obligé de la nommer ainsi...). produit = 1
  • Itérations Les bornes seront bien les mêmes, je vais de 1 à 10
  • Instructions dans la boucle calculera produit=produit*i.
Exemple
Exemple d'utilisation d'un accumulateur : faire un produit valeurs.

Attention : l'initialisation est différente, on a initialisé à 1, pas à 0. Si j'initialise produit à 0, à la première itération je vais calculer 0*1 qui fait 0, puis à la 2eme 0*2 etc....
Ici la produit doit donc être initialisé à 1 (avant la boucle bien entendu) .

Regardez le code ci-dessous et essayez de prévoir le résultat, puis exécutez le.

Exemple
Produit des entiers de 1 à 5
Exercice à choix multiple
Le message commence par NameError, cela signifie que :
Correct !

P2.1 convertir de Base10 en Base2 et inversement

convertir de Base10 en Base2 et inversement

Nous avons vu comment passer de base 10 en base 2 et inversement. Nous allons maintenant coder les conversions décimal - binaire en python.
⚠️ Avant de déplier un paragraphe (titre en bleu), replier le précédent

des boucles avec des chaînes de caractères

Dans ce TP nous allons manipuler des nombres en base 10, qui seront de type int et des nombres codés en binaire, qui seront écrit comme des mots et seront de type str.

Pour décoder un nombre écrit en binaire :

Prenons un exemple : bin = "101"

  • On va lire le mot lettre par lettre, en faisant un parcours de chaine (comme les parcours de listes).
  • Pour chaque lettre, on devra la convertir en int, et la multiplier par une puissance de 2
  • Et on va faire la somme des valeurs obtenues

Exemple : (101)_2 
ightarrow 1 	imes 2^2 + 0 	imes 2^1 + 1 	imes 2^0 = 5

Ce code vous sert d'exemple, mais vous allez devoir faire des modification pour qu'il puisse convertir n'importe quel nombre donnée en chaîne binaire en sa valeur en base 10.

base 2 en base 10

Le code que vous devez complétez doit effectuer les opération suivante :

il commence par afficher le nombre en binaire (une chaine bin prédéfinie par le correcteur automatique).

Il va falloir ici faire 2 initialisations avant la boucle.

  • D'une part, la variable somme, qui va nous servir à calculer la somme des termes.
  • D'autre part la plus grande puissance de p, et pour cela il faudra se servir de len() qui permet de connaître le nombre de lettres dans le mot.

Ensuite on va itérer, sur les lettre du mot.

Dans la boucle :

  • si la lettre est 1 on ajoute 2**p
  • puis on diminue p (avant de passer à la lettre suivante)

Après la boucle on affiche le résultat.

Exercice de code
Ecrire un code qui converti un nombre écrit en binaire dans la base 10.

un nombre binaire nommé bin sera automatiquement généré.

A l'exécution de votre code, un nombre binaire bin sera généré automatiquement. Ce nombre est une chaine de caractère (par exemple : "010011" est une chaine représentant un nombre binaire).
Aide 1 Aide 2 Aide 3

base 10 en base 2 (prérequis : la boucle while)

Rapellons l'algorithme de conversion de base 10 vers la base 2 :

soit un nombre n en base 10

initialiser une variable chaine_bin à une chaine vide 
# on commence les divisions successives
# au début le dividende est n
# on arrête quand le dividende est nul
tant que dividende non nul :
      reste =  reste de la division par 2
      ajouter reste au début de chaine_bin
      quotient = quotient de la division de dividende par 2
      dividende prend la valeur de quotient
fin tant que
afficher le résultat
Cmplétez le code ci-dessous, en suivant l'algorithme des divisions successives donné ci-dessus.

Exercice de code
Complétez ce code qui converti un nombre écrit en base 10 en binaire.

A l'exécution de votre code, un nombre (en base 10) n sera généré automatiquement.

base 16 en base 10 (prérequis : les dictionnaires)

Exercice de code
Complétez ce code qui convertit un nombre écrit en base 16 en binaire.
⚠️ Ne faire cet exercice qu'après avoir étudié les dictionnaires.

Avant l'exécution de votre code, une chaine nommée hex réprésentant un nombre en base 16 sera générée automatiquement.


AUTEURS : Jean-Louis THIROT

T - 3.1 récursivité

Exemples

Exemple 1 : créer une spirale carrée

Nous désirons créer un programme qui produise cette figure :

description de l'image

Pour cela nous allons utiliser le module turtle de façon très basique.

Vous devez commencer par vous connecter à votre compte replit pour faire les activités de dessin Turtle. Ensuite, vous cliquez sur le lien désiré, puis une fois le lien ouvert, en haut à droite, sur open in replit. Si ce n'est pas actif, bien penser à fermer toutes les boites de dialogues qui ont été ouvertes. Une fois la fenêtre de replit ouverte, il faudra cliquer en haut à droite sur Fork

Decouvrir Turtle : Si tu ne connais pas Turtle, ouvre le lien Découverte de Turtle en haut de la page pour apprendre les instructions de base dont nous aurons besoin.

Passons au dessin proprement dit

La récursivité en action : Utilise le lien Dessin récursif en haut de la page

Exemple 2 : créer un arbre

Par exemple, nous voulons écrire un programme qui produit le dessin ci-dessous avec turtle. Cela semble assez difficile.

description de l'image

Le code utilisant une fonction récursive est finalement assez simple à imaginer .

Utiliser le lien Dessin récursif 2 en haut de la page pour voir sa structure

Exemple 3 : calculer an

Nous voulons créer une fonction qui calcule an sans utiliser la fonction puissance.

description de limage
Ci-dessous, la fonction puiss(a,n) qui renvoie la valeur de an. On a donc la transcription immédiate en Python :
Exemple

Regardons ce qu'il se passe si on appelle puiss(3,4)

De façon triviale puiss(3,1) renvoie 3.

description de l'image

Fonctions récursives

Qu'est ce qu'une fonction récursive ?

La récursivité est une méthode de résolution de problèmes qui consiste à décomposer le problème en sous-problèmes identiques de plus en plus simples jusqu'à obtenir un problème suffisamment simple qui puisse être résolu de manière évidente (triviale).

On peut appeler ce problème très simple : cas de base, ou cas trivial.

Dans l'exemple précédant le cas de base est : puiss(a,1) qui renvoie a.


Pourquoi utiliser une fonction récursive ?
Pour le calcul de an , nous aurions pu tout simplement écrire le code suivant, qui est un code dit "itératif", sans utiliser une fonction récursive :
Exemple

Le plus souvent nous utilisons une fonction récursive, lorsque cela est beaucoup plus simple à programmer qu'un programme itératif (décomposition en sous-problèmes identiques de plus en plus simples).


Conditions d'arrêt
Attention ! Une fonction récursive étant une fonction qui s'appelle elle-même, on peut créer une fonction qui "tourne" indéfiniment.
Exemple

Python s'arrête au bout d'un certain nombre d'appels récursifs, et affiche le message d'erreur. Il manquait dans cette fonction le cas de base :

if n == 1 :
       return a

Python limite explicitement le nombre d’appels récursifs dans une fonction. Ainsi, après 1000 appels récursifs, l’interpréteur Python va lever l’exception RecursionError et afficher le message d’erreur suivant : RecursionError: maximum recursion depth exceeded.

Cette limite, fixée à 1000 appels récursifs, est une valeur par défaut qu’il est possible de modifier en utilisant la fonction setrecursionlimit disponible dans le module sys. Par exemple, pour passer cette limite à 2000 appels maximum, on exécutera le code Python suivant :

       import sys
       sys.setrecursionlimit(2000)  
Un tel changement reste cependant dérisoire lorsque l’on a une définition récursive qui, par nature, effectue un très grand nombre d’appels emboîtés.

Source : spécialité Numérique et sciences informatiques, 24 leçons avec exercices corrigés classe de terminale - ellipses

Il peut y avoir un autre problème si les appels récursifs successifs éloignent du cas de base au lieu d'en rapprocher.

Reprenons la fonction puiss() écrite plus haut de façon récursive.

Exemple

Ici puiss(4, -1) appelle puiss(4, -2), qui appelle puis(4, -3) etc...

On n'atteindra jamais le cas de base qui aurait été puiss(4, 1), et le processus est infini.

Comment concevoir un programme récursif ?

  1. Trouver le cas général : trouver l'élément de récursivité qui permet de décomposer le problème en cas plus simple.
  2. Trouver le cas de base : trouver la condition d'arrêt, et la solution du problème dans ce cas particulier. La condition d'arrêt sera bien atteinte après un nombre fini d'appels. Chaque appel récursif tend à se rapprocher du cas de base.
  3. Réunir ces deux cas dans le programme : Le programme ne contient aucune boucle (for ou while) dans la partie qui résout le problème. Le programme contient un général une structure if / else introduisant le cas de base

Alice a réalisé le code suivant pour savoir si un entier se trouve dans un tableau (typ list python). C'est une recherche par dichotomie utilisant une fonction récursive.

Exercice de code : Vous êtes Bob
Clique sur Visualiser pour debugguer ce code qui renvoi toujours None.

Malheureusement, ce code ne fonctionne pas. Elle a donc demandé de l'aide à son ami Bob pour rectifier ce script. Vous êtes Bob, à vous de jouer !

à vous de jouer

Vous devez vous aider du bouton "visualiser" pour comprendre le déroulement du code proposé par Alice.

Compléter la fonction suivante, écrite de façon récursive, pour qu'elle retourne True si un entier est pair, et False sinon.
Vous ne pouvez pas utiliser le modulo %, ni la division /, ni la division entière //

Aide 1      Aide 2
Exercice de code : Parité
Clique sur Visualiser pour debugguer ce code qui renvoi toujours None.

T2.2 Programmation Orientée Objet : TP Morpion

1. Introduction

Le but de ce TP est ici de modéliser le jeu du Morpion, en utilisant le paradigme de la programmation orientée objet, et de mettre en pratique les différents éléments vus dans le cours précédent.

Nous ferons une version sans interface graphique.

Rappel des règles du morpion

Deux joueurs s'affrontent. Ils doivent remplir chacun à leur tour une case de la grille avec le symbole qui leur est attribué : O ou X. Le gagnant est celui qui arrive à aligner trois symboles identiques, horizontalement, verticalement ou en diagonale. Il est coutume de laisser le joueur jouant X effectuer le premier coup de la partie.

Une partie gagnée par le joueur X :

Une partie nulle :

En raison du nombre de combinaisons limité, l'analyse complète du jeu est facile à réaliser : si les deux joueurs jouent chacun de manière optimale, la partie doit toujours se terminer par un match nul.

Visualisez l'extrait vidéo ci-dessous du film Wargames, dans lequel une IA va jouer contre elle même au morpion, pour arriver à la conclusion qu'il n'y a pas de possibilité de gagner et ainsi sauver le monde de la 3e guerre mondiale ...

2. Implémentation, création d'une classe Morpion

Nous allons donc ici créer une classe Morpion, qui contiendra toutes les méthodes et tous les attributs nécessaires à la réalisation du jeu.

Cette classe contiendra les méthodes suivantes (en dehors de la fonction d'initialisation) :

  1. Fonction jouer, qui permet à un joueur de jouer son tour. Cette fonction prend 2 arguments en entrée :
    • le joueur
    • la case jouée.
  2. Fonction afficher_plateau, qui comme son nom l'indique affichera le plateau du jeu (qui ne prend aucun argument en entrée).
  3. Fonction test_fin_jeu, qui teste si un joueur est vainqueur, ou s'il n'y a plus de mouvement possible (qui prend en argument le joueur en entrée).
  4. Fonction jeu, qui contiendra le code qui assure le bon déroulement du jeu en lui-même (qui ne prend aucun argument en entrée).
1. Créer la classe Morpion

Exercice de code : Créez votre classe morpion

(n'oubliez pas la fonction d'initialisation **__init__** )


**Rappel:** les fonctions qui n'ont pas d'argument en entrée ne doivent pas s'écrire () mais (self)

Créez simplement les fonctions avec les bons arguments, et dans le corps de la fonction mettez seulement l'instruction pass, nous allons les remplir après.

Quand vous allez exécuter ce code, il ne se passera rien, ce qui est normal. Mais si lors de l'exécution, votre programme ne passe pas les tests, c'est qu'il y a des erreurs de syntaxe, et vous devez les corriger.

3. Implémentation, création des différentes fonctions de la classe Morpion

Maintenant, nous allons devoir écrire le contenu de chacune de ces fonctions.

2. Créer la Fonction __init__

Dans la fonction __init__, le plateau de jeu est initialisé avec des “-”, le joueur 1 est initialisé avec une croix X et le joueur 2 est initialisé avec un rond O.

Cela signifie que partout sur le plateau ou il y a des tirets, les joueurs n'ont pas encore choisi ces emplacements.

Partout ou il y a des croix cela signifie que le joueur 1 a joué et enfin, partout où il y a des ronds, cela signifie que le joueur 2 a joué.

Nous allons donc déclarer 3 attributs :

  • un attribut nommé plateau, qui contiendra le plateau du jeu. Comme vu ci-dessus, il sera rempli de tirets. Donc ici, nous initialiserons notre plateau avec des '-', de façon à afficher un plateau de 3*3 tirets .
    (Pensez à une liste de listes, avec une liste comprenant 3 listes qui contiennent chacun les 3 tirets).
    Voici ci-dessous le plateau au début du jeu :
                   ---
                   ---
                   ---
  • un attribut J1, qui contiendra un 'X'
  • un attribut J2, qui contiendra un 'O'

Avant d'implementer cette fonction , recopier et coller ci-dessous le code de la classe morpion

Exercice de code : Créez le constructeur
complétez la fonction __init__ Aide 1
3. Créer la fonction jouer

Avant d'appeler la fonction jouer, on commence (dans le programme principal) par lire au clavier 2 nombres (séparés par une virgule) qui sont les n° de ligne, de colonne et de la position où le joueur courant souhaite jouer (1 à 3 en abscisse, puis 1 à 3 en ordonnée). Le joueur entrera par exemple 2,2 pour jouer la case au centre du plateau.

(attention, s'il joue la case 1,1, en python il faudra transcrire : ligne = 0, colonne = 0).

La méthode jouer prend deux arguments :

joueur : str : "X" ou "O"

case : une chaine lue au clavier telle que décrit ci-dessus

Le signe (X ou O) du joueur courant est par la suite écrit sur le plateau à la position précédemment indiquée.

Danc cette fonction vous devrez donc affecter la marque du joueur à la position x et y du plateau (attention aux indices). joueur et case_jouee sont 2 arguments de la fonction. Il faut décoder la case, par exemple "1,1" doit être compris comme ligne=0 et colonne=0.

Ecrivez bien les spécification de la fonction.

Implémentez, ci-dessous, cette fonction (qui prend en argument le joueur en entrée 'X' ou 'O')


(Vous recopierez la classe définie précédemment dans cet exercice (classe + fonction init + les autres fonctions non complétée sauf la fonction jouer).

Exercice de code : Implémenter la méthode jouer
complétez la fonction jouer Aide2 Aide1
4. Créer la Fonction afficher_plateau

La fonction afficher_plateau parcourt le plateau et l’affiche en veillant à bien séparer chaque signe par deux barres “|” pour que cela soit plus lisible

Voilà comment le plateau sera affiché au début du jeu :

|-|-|-|
|-|-|-|
|-|-|-|
Comme le plateau est stocké dans une liste de listes, il faudra utiliser 2 boucles imbriquées. Dans le premier exercice vous avez un exemple, qui donne un résultat assez proche de ce qui est demandé ici. Inspirez vous de cet exemple pour implementer la fonction afficher_plateau

N'oubliez pas de recopier la classe et les fonctions déjà définies.
Exercice de code : Implémenter afficher_plateau
Complétez la fonction afficher_plateau Aide
5. Créer la Fonction test_fin_jeu

test_fin_jeu va vérifier si l’un des deux joueurs a gagné ou s’il n’y a pas égalité.

Pour cela elle va vérifier qu’il n’y a pas 3 fois le même signe aligné ni en horizontal, ni en vertical, ni en diagonal.

Elle va également vérifier qu'il reste de la place pour jouer en vérifiant qu’il reste des signes “-” sur le plateau.

Il y aura 3 cas possibles :

  • Soit le joueur passé en argument aura gagné, et dans ce cas là cette fonction renverra ce joueur.
  • Soit il n'y a plus de place sur le plateau, et dans ce cas on renverra True
  • Soit le jeu n'est pas encore fini, et dans ce cas on retournera False

Ces valeurs de retour seront utilisées dans la fonction principale, jeu, que nous implémenterons en dernier.

Cas où un joueur gagne :

  • Un joueur gagne s'il a aligné 3 fois son signe en horizontal
  • Un joueur gagne s'il a aligné 3 fois son signe en vertical
  • Un joueur gagne s'il a aligné 3 fois son signe en diagonale Pour tester ce dernier cas, vous pourrez si vous voulez faire 2 tests : 1 pour la première diagonale, et un pour la seconde (attention aux indices de vos boucles imbriquées).

A vous de jouer ...
Pour la mise au point, n'hésitez pas à insérer des print dans votre fonction pour voir les résultats intermédiaires, vous les enlèverez ensuite....

Exercice de code : Implémenter la méthode test_fin_jeu
Comme pour les autres exercices, recopiez votre classe, puis ajoutez les instructions pour la fonction test_fin_jeu(). Aide Diagonales Aide Diagonales++ Aide lignes Aide colonnes Aide jeu terminé ? Aide rien ne marche
6. Créer la Fonction jeu

La fonction jeu va lancer le jeu en affichant premièrement le tableau, puis en appelant les fonctions définies plus haut.

Tant que l'un des deux joueurs n’aura pas gagné, elle va les faire jouer chacun leur tour (vous pouvez commencer par faire jouer J1, puis ensuite J2, et ainsi que suite), puis afficher le nouveau plateau et tester que le jeu n’est pas fini.

Vous pourrez utiliser une boucle infinie, en utilisant un booléen qui changera de valeur quand la partie sera terminée.

Si le jeu est fini on sort de la fonction en renvoyant le signe du joueur gagnant (X ou O) ou en renvoyant égalité si c’est une égalité.

Exercice de code : Implémenter la méthode jeu qui lance le jeu
Ajoutez les instructions pour la fonction jeu(). Aide

Améliorations possibles

  • Quand le joueur entre son abscisse et son ordonnée, il faut vérifier que:
    • L'abscisse et l'ordonnée entrés par le joueur sont bien des nombres compris entre 1 et 3, sans quoi il faut leur redemander.
    • Qu'il n'y a pas déjà de X ou de O à l'abscisse et l'ordonnée entrés par le joueur, sans quoi il faut leur redemander.
  • Peut être mettre un menu, puis un choix de niveau de difficulté qui pourrait mettre un temps limite pour répondre.
  • Utiliser la librairie Pygame pour améliorer l'aspect graphique (demander au professeur de vérifier votre travail avant d'attaquer la partie graphique avec Pygame).

Interface graphique

4. Partie graphique avec PyGame

Le but est ici de retranscrire notre travail effectué ici, pour l'afficher proprement avec Pygame.

Nous améliorerons également l'ergonomie du logiciel : ici plus rien à taper au clavier, on pourra directement cliquer sur la case choisie avec la souris pour choisir où mettre son X ou son O

4.1 Changements à apporter dans la structure du programme

  • La première chose à faire sera de copier votre code (fonctionnel) dans edupython, ce sera votre base de départ. Nous ne continuons pas à coder dans Google Coolab car la librairie Pygame n'est pas compatible (l'environnement Python est sur une machine distante, et Pygame a besin d'accéder à la carte graphique de votre ordinateur, ce qui est impossible).
  • Nous allons également faire des changements dans la structure du programme. Nous allons garder notre classe Morpion, mais nous allons créer une 2e classe, intitulée Grille, qui s'occupera uniquement de gérer l'affichage. Et nous créerons une instance de cette classe à l'initilisation de la classe Morpion.
  • Dernière chose, n'oubliez pas d'importer la librairire pygame (évidemment) mais également la librairie sys.

Commençons par le commencement ...

4.2 Création de la fenêtre et de la grille

Pour commencer, nous allons donc créer une nouvelle classe nommée Grille

La fonction d'initialisation prendra un argument en entrée (nommé ecran). Nous verrons son utilité plus tard.

Cettte fonction comprendra :

  • Un attribut ecran que l'on initialisera avec la valeur ecran passée en paramètre.
  • Un attribut lignes qui sera une liste qui contient 4 tuples, avec des coordonnées de points pour tracer les 4 lignes de la grille. Utilisez les valeurs suivantes :[( (200,0),(200,600)), ((400,0),(400,600)), ((0,200),(600,200)), ((0,400),(600,400))]
  • Un attribut grille qui sera un tableau de tableau, qui correspond à notre plateau créé ci-dessus. On l'initialisera avec les valeurs None cette fois-ci (et non plus avec les tirets)

On ajoutera également une fonction afficher pour afficher la grille (qui ne prendra pas d'arguments).

On parcourera juste notre attribut lignes créé ci-dessus, pour tracer des lignes en utilisant la méthode draw.line de pygame :

for ligne in self.lignes :

            pygame.draw.line(self.ecran,(0,0,0),ligne[0],ligne[1],2)
Maintenant, intéressons nous à notre classe Morpion

Nous allons modifier la fonction d'initialisation, en créant la fenêtre Pygame (rappelez vous son fonctionnement)

Dans cette fonction (sans argument ), ajouter :

  • Un attribut ecran, qui créera la fenêtre Pygame:
pygame.display.set_mode((600,600))
  • Un attribut grille, qui sera une instance de la classe Grille (avec en paramètre l'attribut ecran)

Nous allons également modifier la fonction jeu;

Rappelez vous, Pygame fonctionne avec des événements. Il faut donc rajouter une boucle For sur ces événements, et prévoir la sortie :

for event in pygame.event.get():

                if event.type == pygame.QUIT:
                    sys.exit()
Rajouter également ces 2 instructions à la suite de la boucle for, pour ajouter une couleur et rafraichir l'affichage :

self.ecran.fill((240,240,240))
pygame.display.flip()
Enfin, à la suite de ces 2 lignes, nous allons appeler la méthode afficher de l'attribut grille (qui est une instance de la classe Grille, dans laquelle nous avons une méthode afficher)

4.3 Création et affichage des X/O

Nous allons utiliser la souris pour placer nos X et nos O Pour cela, nous utiliserons la méthode mouse.getpos() de pygame. Cette fonction nous renvoie les coordonnées de l'endroit où l'on clique. Or, nos cases font 200 pixels de large et 200 pixels de long.

Comment faire pour convertir facilement ces coordonnées sous forme d'indices qui seront plus facilement utilisables ? Nous allons utiliser la division entière par 200 : nous aurons alors des indices de position.

Rajoutez ces lignes dans la boucle principale de la fonction jeu (nous testons si on a cliqué avec les bouton gauche de la souris):

if event.type == pygame.MOUSEBUTTONDOWN and pygame.mouse.get_pressed()[0]:                 
                    position = pygame.mouse.get_pos() 
                    position_x ,position_y = position[0]//200 ,position[1]//200 

                    if self.compteur % 2 == 0 :
                                  self.grille.fixer_la_valeur(position_x, position_y, self.J1)
                    else:
                                  self.grille.fixer_la_valeur(position_x, position_y, self.J2)
Si vous regardez les dernières lignes, nous testons la parité d'un attribut compteur. Quand il est pair, c'est J1 qui joue, sinon c'est l'inverse.

Nous allons définir la méthode fixer_la_valeur de notre attribut grille juste après.

N'oubliez pas de rajouter également dans la fonction d'initialisation de la classe Morpion l'attribut compteur, qui sera initialisé à 0.

Retour à la classe Grille :

  • Rajouter une nouvelle méthode : fixer_la_valeur.

Cette méthode sera utilisée pour modifier une valeur de la grille, avec X ou O. Elle prendra 3 paramètres : x,y, et la valeur

Testez si la valeur de la grille d'abscisse x et d'ordonnée y est égale à None. Si c'est le cas, on modifie cette valeur de la grille avec valeur

  • Rajoutez un attribut compteur_on, qui sera initialisé à False, qui va nous permettre de définir si le compteur est actif ou pas
    • Mettez le à True quand vous avez modifié une valeur dans fixer_le_valeur
    • Mettez le à False dans la boucle principale, en testant si le compteur est actif, à savoir juste après avoir testé la parité du compteur :
if self.compteur % 2 == 0 :#1
                    self.grille.fixer_la_valeur(position_x, position_y, self.J1)
else:
                    self.grille.fixer_la_valeur(position_x, position_y, self.J2)

if self.grille.compteur_on: #1
                    self.compteur += 1
                    self.grille.compteur_on = False
Enfin, dernière chose avant de tester :

Dans la méthode afficher de la classe Grille, nous affichons déjà les 4 lignes qui font la grille.

Mais il serait bien d'afficher les X et les O également, suivant les valeur de la grille ?

Pour cela, nous allons parcourir les éléments de la grille (double boucle), puis quand nous allons trouver un 'X', nous allons dessiner un X avec la méthode draw.line, et idem pour O avec la méthode draw.circle. Nous utiliserons les fonctions de dessins de Pygame.

Je vous épargne cette recherche fastidieuse qui n'est pas le but du TP ici, et je vous donne les instructions à rajouter :

for y in range(0,len(self.grille)):
            for x in range(0,len(self.grille)):


                    if self.grille[y][x] == 'X' :

                        pygame.draw.line(self.ecran, (0, 0, 0), (x * 200, y * 200), (200 + (x * 200), 200 + (y * 200)), 3) 
                        pygame.draw.line(self.ecran, (0, 0, 0), ((x * 200), 200 + (y * 200)), (200 + (x * 200), (y * 200)),
                                     3)

                    elif self.grille[y][x] == 'O' :

                        pygame.draw.circle(self.ecran, (0, 0, 0), (100 + (x * 200), 100 + (y * 200)), 100, 3)

4.4 Vainqueur et fin de partie

Nous y sommes presque. Il vous reste à réutiliser la méthode test_fin_jeu définie ci-dessus, qui nous permettait de savoir qui était vainqueur.

En effet, nous ne parcourons plus le plateau, mais la grille

Attention cependant si vous remplacez juste plateau par grille, cela risque de ne pas fonctionner et de générer le message d'erreur suivant :

TypeError: 'Grille' object does not support indexing

A vous de voir pourquoi il y a ce message d'erreur, et quelle modification, liée à la nature de l'attribut grille il faut effectuer

Un peu de ménage de code :

N'oubliez pas de supprimer certaines fonctions qui ne sont plus utiles, comme afficher_plateau et jouer de la classe Morpion qui ne sont plus utilisées.

BON JEU !!!

4.5 Aller plus loin

Pour ceux qui ont une version fonctionnelle, vous pouvez faire un menu de démarrage, avec la possiblité de rentrer des noms pour les joueurs, et de recommencer une partie.

Et également, pour ceux qui le souhaitent, programmer une IA qui pourrait jouer contre vous.

Mais ceci est une autre histoire ...

t1.2 révisions : les dictionnaires

Découverte

Nous souhaitons lire avec un code écrit en python des données dans un fichier csv. Nous allons avoir besoin d'un nouveau type de variable : les dictionnaires.

Vous connaissez déjà les listes. Par exemple lst=[1,2,4,1,0] est une liste de nombres, et on sait accéder aux valeur de chaque élément :

Exemple

Finalement, chaque élément de la liste est associé à un indice.

  • 1 est à l'indice 0
  • 2 à l'ndice 1
  • etc...

Dans un dictionnaire, les indices sont remplacés par des descripteurs aussi appelés les clés du dictionnaire. Voila comment pourrait être écrite la liste précédente sous forme d'un dictionnaire :

Exemple

Bon, ça ne sert pas à grand chose vu comme ça ! car ici on a utilisé des clés qui sont strictement identiques aux indices de la liste. Mais ça devient beaucoup plus intéressant si ces clés sont des mots décrivant le contenu :

Exemple
Un dictionnaire permet de décrire les valeurs

Exercice

Exercice de code : afficher les valeurs des clés
Dans cet exercice, vous disposez d'un dictionnaire déjà créé. Faire afficher successivement le nom, le prenom et l'année de naissance.

Modifier un dictionnaire

Exemple
Un dictionnaire permet de décrire les valeurs

Nous venons de voir comment modifier la valeur d'une clé existante. Mais comme pour les listes, on peut bien sur aussi ajouter des éléments :

Exemple
Un dictionnaire permet de décrire les valeurs

Dans le cas d'une liste, les indices sont toujours les mêmes : 0, 1, 2 ...

Dans un dictionnaire en revanche, les descripteurs sont spécifiques, et on peut avoir besoin de les connaitre. On utilise pour cela la méthode keys() :

parcourir un dictionnaire

Rappel parcours de listes

Exemple
rappel : parcours de liste (avec les indices)

Parcours d'un dictionnaire avec keys

On peut parcourir de la même manière un dictionnaire, mais comme les indices sont remplacé par des clés, il faut itérer sur les clés. Pour cela on utilise la méthodé keys() qui nous donne la liste des clés.

Exemple
Un dictionnaire permet de décrire les valeurs

On peux également utiliser les méthodes values et items

Exemple : La méthode Values
Exemple : La méthode items
items renvoi un objet dict_items qui ressemble beaucoup à une liste de tuples.

Exercice

Exercice de code : implementez et afficher un dictionnaire
Voici ci dessous un court extrait de la liste des 72 noms de scientifiques, gravés sur la tour Eiffel. Il s'agit d'une petit partie de ceux gravé sur la face Trocadéro.
Représentez l'information de ce tableau dans trois dictionnaire avec les descripteurs suivants :
  • numéro
  • nom
  • prenom
  • naissance
  • deces
  • metier
(vous n'incluerez pas le Titre dans les dictionnaires).
Le code, à partir de la ligne 6, vous est donné : on va regrouper les 3 dictionnaires dans une liste et afficher cette liste, d'abord dans un parcours de liste, puis d'un seul bloc.
FACE TROCADÉRO
No  Nom en abrégé inscrit sur la tour Eiffel Prénom Dates de naissance et de mort Métier(s) Titres de gloire
1 SEGUIN Marc 1786-1875 Mécanicien Constructeur de ponts suspendus - Inventeur de la chaudière tubulaire
2 LALANDE Joseph 1732-1807 Astronome Nombreux travaux d'astronomie et d'hydrologie
3 TRESCA Henri 1814-1885 Ingénieur et mécanicien Auteur du critère de Tresca (résistance des matériaux)

T2.1 Programmation orientée objet

Créer une classe pas à pas

créer une Classe

Un exemple pas à pas

Nous allons commencer par écrire une classe Personnage (qui sera dans un premier temps une coquille vide) et, à partir de cette classe créer 2 instances : bilbo et gollum.

Exemple : création d'une classe

Exécutez ce code. Observez le type des variables gollum et bilbo

Les classe (ou objets) sont des types personnalisés


Pour l'instant, notre classe ne sert à rien et nos instances d'objet ne peuvent rien faire. Comme il n'est pas possible de créer une classe totalement vide, nous avons utilisé l'instruction pass qui ne fait rien. Ensuite nous avons créé 2 instances de la classe Personnage : gollum et bilbo.

Le constructeur : la méthode __init__

La méthode __init__

Les attributs de l'objet doivent être définis dans la classe, à l'aide d'une méthode d'initialisation des attributs.

Une méthode particulière, nommée LE CONSTRUCTEUR, permet de définir les attribut dès l'instanciation d'un objet.

Cette méthode est définie dans le code source par la ligne :

def __init__ (self) :
Rappel : La méthode __init__ est automatiquement exécutée au moment de la création d'une instance. Le mot self est obligatoirement le premier argument d'une méthode.

Le mot self représente l'instance. Quand vous définissez une instance de classe (bilbo ou gollum) le nom de votre instance va remplacer le mot self.

Dans le code source, nous allons avoir :

class Personnage:
def __init__ (self):
    self.vie = 20
Ensuite lors de la création de l'instance gollum, python va créer un attribut vie de la variable gollum.

Cet attribut aura aura pour valeur de départ la valeur donnée à self.vie dans la méthode __init__

Il se passera exactement la même chose au moment de la création de l'instance bilbo, on aura automatiquement la création de l'attribut vie de la variable bilbo.

Exécutez ce code, et dans la console, faites afficher les valeurs de gollum.vie et bilbo.vie

Exercice de code : Encapsuler les attributs
Ajoutez les instruction pour afficher les vies de Bilbo puis de Gollum.

Imaginons que nos 2 personnages n'aient pas au départ les mêmes points de vie ! Pour l'instant, impossible d'introduire cette contrainte (self.vie = 20)

Une méthode, comme une fonction, peut prendre des paramètres (des arguments).

Le passage de paramètres se fait au moment de la création de l'instance. Modifiez le code pour que le nombre de vies soit un paramètre dont la valeur sera fixée lors de l'instanciation.

Exercice de code : Passer des arguments aux méthodes
Votre code doit :
  • Permettre de passer un argument nbVies
  • Crée une instance Personnage nommée bilbo initialisée avec 20 vies.
  • Créer une autre instance, gollum, avec 15 vies.
  • Afficher les valeurs de l'attribut vie pour bilbo
  • Afficher les valeurs de l'attribut vie pour gollum

Au moment de la création de l'instance gollum, on passe comme argument le nombre de vies (gollum = Personnage (15)).

Nous pouvons passer plusieurs arguments à la méthode __init__ (comme pour n'importe quelle fonction).

Exercice de code : Passer 2 arguments
Votre code doit :
  • Permettre de passez deux paramètres au constructeur.
  • Utiliser les paramètres pour initialiser les attibuts vie et age.
  • Créer une instance, gollum, avec 20 vies et 127 ans.
  • Afficher ceci (en utilisant les attributs) : gollum a 127 ans et 20 vies

Améliorons en ajoutant d'autres méthodes

utiliser une classe avec plusieurs méthodes
Exercice de code : plus de méthodes...
Votre code doit :
  • Ajouter une méthode perdVie qui modifie l'attibut vie (retire une vie)
  • Ajouter une méthode donneEtat qui renvoie la valeur de l'attibut vie
  • Créez 1 seul personnage, gollum, avec 20 vies. puis vous définirez
  • créer 1 variable etat1 égale à son nombre de vie.
  • Modifier le nombre de vie avec la méthode perdVie
  • créer 1 variable etat2 égale à son nombre de vie.

Vous avez sans doute remarqué que lors de "l'utilisation" des instances bilbo et gollum, nous avons uniquement utilisé des méthodes et nous n'avons plus directement utilisé des attributs (plus de "gollum.vie"). Il est important de savoir qu'en dehors de la classe l'utilisation des attributs est une mauvaise pratique en programmation orientée objet : les attributs doivent rester "à l'intérieur" de la classe, l'utilisateur de la classe ne doit pas les utiliser directement. Il peut les manipuler, mais uniquement par l'intermédiaire d'une méthode (la méthode self.perdVie() permet de manipuler l'attribut self.vie)

Ajouter une méthode puis utliser la classe
Exercice de code
Nos personnages peuvent boire une potion qui leur ajoute un point de vie. Vous devez :
  • Modifiez la classe Personnage en ajoutant une méthode boirePotion.
  • créer une fonction simul(n) qui crée un personnage avec n vies, lui fait boire une potion, et renvoi le nombre de vie.
Passer des arguments à une méthode

Passer des arguments à nos méthodes

Selon le type d'attaque subit, le personnage peut perdre plus ou moins de points de vie. Pour tenir compte de cet élément, ajoutez un paramètre à la méthode perdVie.

Exercice de code
Vous devez :
  • Modifier la méthode perdVie pour que le nombre de vies perdues soit un paramètre.
  • instancier gollum avec 15 vies
  • Lui faire perdre 2 vies avec la méthode perdVie
  • Faire afficher le nombre de vies avec la méthode donneEtat
CONTRAINTE : vous ne pouvez pas utiliser la notation pointée gollum.vie
De l'impératif dans les méthodes

Il est bien entendu possible d'utiliser la librairie random pour ajouter une part d'aléatoire dans la méthode perdVie.

Exercice de code : Un peu de hasard ne nuira pas...
Modifiez le code précédent, de façon que perdVie(nbreDeVie) retire entre 1 et un paramère nbreDeVie vies au personnage attaqué. Vous devez :
  1. Modifier la class Personnage
  2. Completer le code de façon à créer un personnage ayant 100 vies puis qui subit 3 attaques consécutives, lui infligeant chacune 1 à 10 vies perdues...

Dans une méthode vous pouvez utiliser toutes les instructions que vous connaissez déjà en paradigme impératif. Modifiez de nouveau le code, cette fois la méthode perdVie doit être écrite de façon à ne jamais renvoyer un nombre de vie négatif. Si le nombre de vie est négatif, nombre de vie sera mis à 0.

Exercice de code : plus mort que mort ?
Modifiez de nouveau le code, cette fois la méthode perdVie doit être écrite de façon à ne jamais renvoyer un nombre de vie négatif. Si le nombre de vie est négatif, nombre de vie sera mis à 0.. Vous devez :
  1. Modifier la class Personnage
  2. Completer le code de façon à créer un personnage ayant 100 vies puis qui subit des attaques consécutives, lui infligeant chacune 1 à 10 vies perdues, jusqu'à ce qu'il n'ai plus aucune vie. Le code affichera le nombre d'attaques subies.

T2.1 Effets de bord

Variables locales et variables globales

Portée des variables

Premier exemple :

Exemple : premier exemple
Avant d'exécutez le programme ci-dessus, interrogez vous sur la valeur de la variable i à l'issue de l’exécution, puis lancer le code et vérifiez

Comme vous avez pu le constater, nous avons eu droit à une erreur : "NameError: name 'i' is not defined".

Pourquoi cette erreur, la variable i est bien définie dans la fonction fct() et la fonction fct() est bien exécutée, où est donc le problème ?

En fait, la variable i est une variable dite locale : elle a été définie dans une fonction et elle "restera" dans cette fonction. Une fois que l'exécution de la fonction sera terminée, la variable i sera "détruite" (supprimée de la mémoire). Elle n'est donc pas accessible depuis "l'extérieur" de la fonction (ce qui explique le message d'erreur que nous obtenons).

Une variable définie dans une fonction est locale.
Elle ne peut pas être utilisée en dehors de la fonction.

Deuxième exemple :

Exemple : Deuxième exemple
Avant d'exécutez le programme ci-dessus, interrogez vous sur la valeur de la variable i à l'issue de l’exécution, puis lancer le code et vérifiez

Cette fois pas d'erreur, mais à la fin de l'exécution de ce programme, la variable i référence la valeur 3.

En fait, dans cet exemple nous avons 2 variables i différentes : la variable i "globale" (celle qui a été définie en dehors de toute fonction) et la variable i "locale" (celle qui a été définie dans la fonction). Ces 2 variables portent le même nom, mais sont différentes.

Une variable définie localement dans une fonction peut porter le même nom qu'une variable globale. Dans ce cas, ce sont deux variable distinctes mais de même nom (ce qui n'est pas une bonne pratique).

Troisième exemple :

Exécutez le programme suivant :

Exemple : Troisième exemple
Avant d'exécutez le programme ci-dessus, interrogez vous sur la valeur de la variable i à l'issue de l’exécution, puis lancer le code et vérifiez

La variable i est définie en dehors de la fonction, elle est globale.

Une variable globale peut être "utilisée" à l'intérieur d'une fonction.

Quatrième exemple :

Avant d'exécutez le programme ci-dessus, déterminez la valeur référencée par la variable i en fin d'exécution

Exemple : Quatrième exemple
Avant d'exécutez le programme ci-dessus, interrogez vous sur la valeur de la variable i à l'issue de l’exécution, puis lancer le code et vérifiez

Pour le "print(i)" situé dans la fonction le système trouve une variable i dans l'espace local de la fonction "fct", et il utilise donc celle ci, même s'il existe une variable globale i. Il est important de bien comprendre que le lorsque système trouve une variable i dans l'espace local de la fonction, la "recherche" de la variable i s'arrête là. D'autre part, ici nous avons deux variable i : l'une globale, définie en dehors de fct(), une autre locale, définie dans fct(). Lorsque la fonction s'arrête, la variable locale est détruite, la variable globale demeure et n'a pas été modifiée.

Cliquez Visualiser et observez l'état de la mémoire au cours de l'exécution.

Cinquième exemple :

Exécutez le programme ci-dessus, déterminez la valeur référencée par la variable i en fin de programme.

Exemple : Cinquième exemple (version 1)
Avant d'exécutez le programme ci-dessus, interrogez vous sur la valeur de la variable i à l'issue de l’exécution, puis lancer le code et vérifiez

Nous avons une erreur "UnboundLocalError: local variable 'i' referenced before assignment"

Cinquième exemple (avec global)

Exécutez maintenant cette seconde version de l'exemple 5 :


Exemple : Cinquième exemple (version 2)
Avant d'exécutez le programme ci-dessus, interrogez vous sur la valeur de la variable i à l'issue de l’exécution, puis lancer le code et vérifiez

Pour pouvoir modifier une variable globale dans une fonction, il faut utiliser l'instruction "global"

En fait, l'utilisation de "global" est une (très) mauvaise pratique, car cette utilisation peut entraîner des "effets de bord".

Effet de bord

Effet de bord (secondaire)

On parle d'effet de bord (c'est une bien mauvaise traduction de side effet, on devrait dire effets secondaires) quand une fonction modifie l'état d'une variable globale. Dans notre exemple ci-dessus la fonction fct modifie bien la valeur référencée par la variable i : avant l'exécution de fct, la variable i référence la valeur 5, après l'exécution de la fonction fct la variable i référence la valeur 6. Nous avons donc bien un effet de bord.

Les effets de bord c'est "mal" ! Mais pourquoi est-ce "mal" ?

Les effets de bords provoquent parfois des comportements non désirés par le programmeur (évidemment dans des programmes très complexes, pas dans des cas simplistes comme celui que nous venons de voir). Ils rendent aussi parfois les programmes difficilement lisibles (difficilement compréhensibles). À cause des effets de bord, on risque de se retrouver avec des variables qui référenceront des valeurs qui n'étaient pas prévues par le programmeur. On dit aussi qu'à un instant donné, l'état futur des variables est difficilement prévisible à cause des effets de bord.

En résumé, on évitera autant que possible l'utilisation du "global".

Un paradigme de programmation se propose d'éviter au maximum les effets de bords : la programmation fonctionnelle. Nous étudierons ce paradigme de programmation très prochainement.

T - 4.3 Files

II. Les Files

Vous allez vous-même compléter ci-dessous une possible implémentation de ces fonctions primaire, en utilisant le vocabulaire de la programmation orientée objet que nous avons déjà abordée. Dans toute la suite les files seront affichées entre crochets, comme des list python. Le coté du défilage est l'élément écrit le plus à droite. Ainsi, si l'on part d'une file vide, et que l'on enfile successivement les entiers 1, puis 2, puis 3, on obtiendra une file qui s'affichera de la façon suivante : [3, 2, 1]. Le sommet de cette file est l'entier 1.

Pour ne pas perdre de vue le sens de la File, la méthode str permettra d'afficher de quel coté on enfile et de quel coté on défile. Ce choix est arbitraire.

Implementer les fonctions primaires
Exercice de code

Maintenant que vos primitives sont définies vous allez pouvoir les tester

Exemple

A vous de jouer !

Écrire ci dessous les instructions qui permettent d'obtenir successivement les affichages suivants :

enfilage -> [8] -> défilage
enfilage -> [14, 8] -> défilage
enfilage -> [12, 14, 8] -> défilage
enfilage -> [12, 14] -> défilage
enfilage -> [12] -> défilage
enfilage -> [] -> défilage

Exercice de code

T4.3 dictionnaire versus listes

Dans une bibliothèque, nous avons 10000 livres. Pour chacun un certain nombre de caractéristiques : auteur, date de parution, nombre de pages etc...

Nous allons nous limiter à une seule caractéristique, par exemple le nombre de pages. Chaque livre à donc un nombre de page (remarquons qu'inversement, plusieurs livres peuvent avoir le même nombre de pages).

Nous aimerions trouver le plus rapidement possible le nombre de pages d'un livre. Nous devons décider comment représenter la situation. Nous pouvons utiliser des tuples (livre, nbDePages), on construira alors une liste de tuples, ou nous pouvons utiliser un dictionnaire : {livre1: nbDePages1, livre2: nbDePages2 etc...}

A première vue, laquelle des deux représentations vous semble la plus adaptée (laquelle vous semble plus naturelle) ?

Par ailleurs, ce choix aura-t-il un impact en terme d'efficacité dans la recherche ?

C'est ce que nous allons explorer dans ce TP.

👉 Nous utilisons ici le type : list de python

Implémenter avec une liste ou un dictionnaire

Implémentation avec liste ou dictionnaire

Exercice de code : représenter le problème avec une liste de tuples
Vous disposez de 2 listes : une liste de livres, et une liste de nombre de pages. Les deux listes sont en correspondance : nbPages[i] est le nombre de pages de livre[i].
En utilisant ces deux listes vous devez en construire une nouvelle, avec des tuples (livre, nombre de pages).
Ensuite, en repartant de cette liste, construire un dictionnaire comme décrit plus haut.
Rechercher l'information souhaitée

Fonctions de recherche de l'information

Bravo ! Vous avez bien implémenté les deux modèles. Maintenant, créez deux fonctions pour trouver le nombre de pages d'un livre.

Exercice de code : Chercher l'information

Le correcteur automatique va maintenant générer pour vous une liste et un dictionnaire, comme vous l'aviez fait dans l'exercice précédent.
Vous devez coder deux fonctions de recherche, l'une dans la liste, l'autre dans le dictionnaire, renvoyant toute deux le nombre de page d'un livre.
Votre code ne doit rien afficher, le correcteur définira des arguments pour tester vos deux fonctions.
Mesure d'efficacité

Mesure de l'efficacité

La liste et le dictionnaire générés sont de taille très limitée, aussi la mesure de l'efficacité de l'un et l'autre n'est pas aussi probante que si nous travaillions avec des listes de 10000 livres.

Néanmoins nous pouvons comparer la recherche dans la liste et la recherche dans le dictionnaire.

Exercice de code : Chercher l'information

Le correcteur automatique va maintenant générer pour vous
  • une liste et un dictionnaire, comme précédemment, nommées liste et dico
  • les deux fonctions de recherche findInlist et findInDico
  • une variable livre1.
Tout ce que vous avez à faire est d'inclure des appels répétés (disons 10000 fois) à chacune de vos fonction, pour mesurer les temps des recherches.

Vous rechercherez livre1 dans la liste, ou dans le dico.

Pour une fois, le correcteur ne tiendra pas compte des affichage en console pour évaluer votre code, mais il évaluera quand même le résultat important : quelle méthode est la plus efficace ?

Mesure plus fine de la complexité

Bon, le dictionnaire est plus efficace. Mais ici on travaille sur une bibliothèque de 5 livres.... passons à quelques chose de plus réaliste. Dans l'exemple ci-dessous vous n'avez rien à coder, mais observer et conclure.

On génère pour vous une bibliothèque (c'est à dire, une liste et un dictionnaire) de 10000 livres (bon, les noms des livres ici sont des entiers, mais ça importe peu..). Le code ci-dessous va utiliser les deux fonctions de recherche pour déterminer le nombre de pages d'un livre. On va prendre des livres du début de liste, puis de plus en plus loin dans la liste.... on devrait donc mettre de plus en plus longtemps pour les trouver.

Pour chaque livre la recherche est répétée 100 fois afin d'estimer un temps moyen a peu près stable.

Exemple : Complexités
Exercice à choix multiple
La complexité de la recherche dans la liste vous semble :
Correct !
Exercice à choix multiple
La complexité de la recherche dans le dictionnaire vous semble :
Correct !