T SDD4 Parcours de graphes

Comme les autres structures de données, nous avons souvent besoin de parcourir un graphe.

Ci-contre un graphe non orienté, contenant 8 sommets et 10 arrêtes.

Sa matrice d'adjacence se définit ainsi :

matrice = [[0,1,1,0,0,0,0,0],
          [1,0,0,1,1,0,0,0],
          [1,0,0,1,0,0,0,0],
          [0,1,1,0,1,0,0,0],
          [0,1,0,1,0,1,1,0],
          [0,0,0,0,1,0,1,0],
          [0,0,0,0,1,1,0,1],
          [0,0,0,0,0,0,1,0]]
Sa liste d'adjacence s'écrit
A : B,C
B : A,D,E
C : A,D
D : B,C,E
E : B,D,F,G
F : E,G
G : E,F,H

Deux stratégies possibles

  • Recherche en profondeur d'abord, nommée Depth First Search alias DFS
  • Recherche en largeur d'abord, nommé BFS, Breadth First Seard, alias BFS
Recherche en profondeur d'abord

ci-dessous le sujet (à compléter) au format pdf

https://cscircles.cemc.uwaterloo.ca/wp-content/uploads/deroule-dfs-nonrec.pdf

Activité débranchée : Recherche en profondeur d'abord

Pour parcourir le graphes en profondeur d'abord :

  • on commence avec un nœud donné (point de départ)
  • on explore chaque branche complètement avant de passer à la suivante. Autrement dit, on commence d'abord par aller le plus profond possible. Comme pour les arbres, cet algorithme s'écrit naturellement de manière récursive.

Donc, parcourir un graphe en profondeur à partir d’un sommet, consiste à explorer le graphe en suivant un chemin. Lorsqu’on arrive sur un sommet qui n’a plus de voisins non visités, on remonte dans le chemin pour explorer les voisins non visités d’un autre sommet…

Première version : non récursive
On utilise une pile (aVoir) et une liste (vus)

Prenons en exemple le graphe montré plus haut :
On dispose

  • d’un graphe
  • d'une liste vus sommets_visités
  • et d’une pile aVoir des sommets à visiter

Algorithme de parcours DFS

  • Le sommet de départ est par exemple ’G’ on ajoute ce sommet de départ dans vus
  • On met dans la pile aVoir tous les voisins de G
  • Puis, tant que aVoir n’est pas vide :


• On récupère le sommet de la pile aVoir dans une variable sommet et on ajoute sommet dans vus
• on empile tous les voisins (non déjà visités et non déjà à voir) de sommet dans aVoir


Voici les contenus des variables au premier tour de la boucle tant que :

Au début:

sommet = g
aVoir: [h,f,e]
1er tour de la boucle :
sommet=e
vus : [g,e]
aVoir = [h,f,d,b]


Au second tour de la boucle tant que :

2nd tour
sommet = b
vu = [g,e,b]
aVoir : [h,f,d,a]


Au troisième tour de la boucle tant que :

3ème tour
sommet = a
vu = [g,e,b,a]
aVoir : [h,f,d,c]


Au quatrième tour de la boucle tant que :

4ème tour
sommet = c
vu = [g,e,b,a,c]
aVoir : [h,f,d]


Au cinqième tour de la boucle tant que :

5ème tour
sommet = d
vu = [g,e,b,a,c,d]
aVoir : [h,f]


Au sixième tour de la boucle tant que :

6ème tour
sommet = f
vu = [g,e,b,a,c,d,f]
aVoir : [h]


Au septième tour de la boucle tant que :

7ème tour
sommet = h
vu = [g,e,b,a,c,d,f,h]
aVoir : []
la boucle s'arrête


la liste aVoir est utilisée comme une PILE. On empile les voisins du sommet que l'on visite, puis on les dépile, c-a-d qu'on repart du dernier sommet empilé. C'est pour cette raison que l'on parcours l'arbre en profondeur, on commence par les voisin du dernier sommet. Si on utilisait aVoir comme une file, on parcourrais en largeur (ce que nous ferons plus loin).

Voici une représentation schématique du parcours que nous venons de faire, si on représente le graphe avec G en haut, puis par couche selon la distance à G :

Implémentation non récursive de l'algorithme


Algorithme :

Placer le sommet de départ dans vus
Empiler les voisins de ce sommet dans aVoir
tant que aVoir n'est pas vide :
       depiler le prochain sommet
       l'ajouter dans vus
       ajouter ses voisins non vus et non à voir dans aVoir


Coding Exercise
Ecrire la fonction DFS qui renvoie la liste des sommets vus (dans l'ordre de visite) Le correcteur va générer une classe graphe, et une instance gr de graphe. Cet objet dispose d'un attribut lstAdj qui contient un dictionnaire avec la liste d'adjence d'un graphe (celui étudié en cours).

Implémentation récursive de l'algorithme DFS

Algorithme :

DFS(gr , sommet , vus) :
Placer le sommet de départ dans vus
pour chaque voisin de liste des voisins de ce sommet :
   si le voisin n'est pas déjà vu :
     DFS(gr,voisin,vus)
renvoyer la liste vus

Coding Exercise
Ecrire la fonction DFS qui renvoie la liste des sommets vus (dans l'ordre de visite) Le correcteur va générer une classe graphe, et une instance gr de graphe. Cet objet dispose d'un attribut lstAdj qui contient un dictionnaire avec la liste d'adjence d'un graphe (celui étudié en cours).

Recherche en largeur d'abord

Activité débranchée : Recherche en LARGEUR d'abord BFS

https://cscircles.cemc.uwaterloo.ca/wp-content/uploads/deroule-bfs.pdf

Pour parcourir le graphes en largeur d'abord :

Algorithme de parcours BFS

  • on commence avec un nœud donné (point de départ)
  • on ajoute ce sommet dans vus
  • on enfile les voisins de ce sommet dans aVoir
  • tant que la FILE aVoir n'est pas vide :
  • -- on defile le prochain sommet et on l'ajoute dans la liste vus
  • -- on enfile ses voisins dans aVoir

Donc, parcourir un graphe en largeur à partir d’un sommet, consiste à explorer le graphe en explorant systématiquement tous les voisins d'un sommet avant de descendre dans la profondeur du graphe.


Voici les contenus des variables au premier tour de la boucle tant que :

Au début:

sommet = g
aVoir: [e,f,h]
1er tour de la boucle :
sommet=e
vus : [g,e]
aVoir = [f,h,d,b]


Au second tour de la boucle tant que :

2nd tour
sommet = f
vu = [g,e,f]
aVoir : [h,b,d]


Au troisième tour de la boucle tant que :

3ème tour
sommet = h
vu = [g,e,f,h]
aVoir : [b,d]


Au quatrième tour de la boucle tant que :

4ème tour
sommet = b
vu = [g,e,f,h,b]
aVoir : [d,a]


Au cinqième tour de la boucle tant que :

5ème tour
sommet = d
vu = [g,e,f,h,b,d]
aVoir : [a,c]


Au sixième tour de la boucle tant que :

6ème tour
sommet = a
vu = [g,e,f,h,b,d,a]
aVoir : [c]


Au septième tour de la boucle tant que :

7ème tour
sommet = c
vu = [g,e,f,h,b,d,a,c]
aVoir : []
la boucle s'arrête


la liste aVoir est utilisée comme une FILE. On enfile les voisins du sommet que l'on visite, puis on les défile, c-a-d qu'on repart du premier sommet enfilé. C'est pour cette raison que l'on parcours l'arbre en largeur, on commence par les voisins des premier sommets visités.

Voici une représentation schématique du parcours que nous venons de faire, si on représente le graphe avec G en haut, puis par couche selon la distance à G :

Implémentation (non récursive) de l'algorithme BFS


Algorithme :

Placer le sommet de départ dans vus
Enfiler les voisins de ce sommet dans aVoir
tant que aVoir n'est pas vide :
       defiler le prochain sommet
       l'ajouter dans vus
       ajouter ses voisins non vus et non à voir dans aVoir


Coding Exercise
Ecrire la fonction BFS qui renvoie la liste des sommets vus (dans l'ordre de visite) Le correcteur va générer une classe graphe, et une instance gr de graphe. Cet objet dispose d'un attribut lstAdj qui contient un dictionnaire avec la liste d'adjence d'un graphe (celui étudié en cours).

T 3.3 Exercices recursivité

Les classiques

Ces exercices se rapprochent de l'exponentiation. On écrit par exemple des chose comme :

Avec un seul paramètre :

  • f(n) = 1 + f(n-1)
  • f(n) = 2 * (n-1)
  • f(n) = n + f(n-1)
  • f(txt) = txt[0] + f(txt[1:])
  • f(lst) = [ lst[0] ] + f( lst[1:] )
  • f(lst) = lst[0] < lst[1] and f( lst[1:] )



ou avec deux paramètres, on trouvera des choses comme :

  • f(a, n) = a * f(a, n-1)
  • f(a, n) = 1 + f(a, n-1)
  • f(x , lst) = (x == lst[0]) or f(x , lst[1:] ) # ! la fct renvoie un booléen
  • f(lettre,txt) = ( lettre == txt[0] ) + f(lettre,txt[1:]) # ! La fct renvoi un int

Pour les booléens il y a parfois quelques subtilités....

f(x , lst) = (x == lst[0]) or f(x , lst[1:] ) # ! la fct renvoie un booléen

rappellez vous que pour évaluer condition1 or condition2 python n'évalue condition2 que si condition1 s'évalue à False.

En d'autres termes, si x==lst[0] est True, on ne fera pas l'appel récursif ! C'est ce qu'on fait dans appartient(x,lst), quand on le trouve, plus besoin de continuer... 
autre exemple :

f(lettre,txt) = ( lettre == txt[0] ) + f(lettre,txt[1:]) # ! La fct renvoi un int
Ici il y a une addition d'un booléen avec f(..). Les seules additions autorisées avec des booléens sont :

bool + bool -> int
bool + int -> int

exemple :
False + False s'évalue à 0 (False est converti en 0, True en 1)
False + 3 s'évalue à 3
True + 1 s'évalue à 2
a = 1
print( (a==1) + 1 )
ce code affiche 2

Dans la récursion cela peut être parfois bien utile, mais on pourrait s'en tirer autrement (et c'est recommandé si ce qui précède ne vous semble pas clair pour vous) :

f(lettre,txt) = ( lettre == txt[0] ) + f(lettre,txt[1:]) # ! La fct renvoi un int

sera identique à :
if lettre == txt[0] :
     n = 0
else :
     n = 1
return n + f(lettre,txt[1:])

c'est juste plus facile de lire le code en une ligne que le code 
de 5 lignes.... 
il est plus élégant, mais recommandé seulement quand on maitrise 
bien les problèmes de typages des expressions.
La chose vraiment à retenir : respectez les types !

Si la fonction renvoie une list, les return (du cas de base comme du cas général) devront renvoyer une list.

si on veux construire la list en ajoutant un nombre à chaque appel, le return du cas général sera forcément du genre :

return [a] + f(...)
Les ... indique qu'on rapelle la fonction avec de nouveaux paramètres (une liste modifiée, ou un paramètre avec une valeur modifiée etc...)

ex 1 - somme de n entiers

Coding Exercise: somme
Ecrire une fonction récursives somme qui prendra en argument un nombre n, et qui renvoie la somme des n premiers entiers jusqu'à n.
Exemple : somme(4) renvera 10 (1 + 2 + 3 + 4 = 10)

ex 2 - addition unitaire

Dans cet exercice nous voulons calculer la somme a + b, mais de façon très basique.

Imaginez deux tas, à gauche a cailloux et à droite, b cailloux.

pour ajouter b à a, je passe les cailloux UN PAR UN du tas de droite au tas de gauche.

je compte donc jusqu'à a, puis a chaque cailloux ajouté, j'augmente de 1, et le tas de droite diminue. Quand le tas de droite est vide, je sais combien vaut a + b.

Ce processus est similaire à la fonction récursive demandée ci-dessous.

Coding Exercise: Addition unitaire
Ecrire une fonction somme qui renvoi la somme a+b en utilisant seulement les opération +1 ou -1

Exemples:
somme(2,4) renvoie 6 (sans jamais écrire 2+4)

ex 3 - longueur

Coding Exercise: Longueur d'une chaine
Ecrire une fonction longueur qui renvoi la logueur d'une chaine

CONTRAINTE : vous ne devez pas utiliser for, while ou len.

ex 4 - my_range

Dans cet exercice nous allons écrire un substitut de la fonction range()

Coding Exercise: my_range()
Ecrire une fonction my_range qui renvoi une liste contenant les entiers de a à b-1.

CONTRAINTE : vous ne pouvez pas utiliser de boucle for ou while ni de liste en compréhension, ni la fonction range()

Avec des chaînes de charactères

Le principe sera le même : décomposer le problème en une opération simple et une répétition du problème légèrement simplifié.

Dans les exercices qui suivent, essayez de comprendre comment on peut décomposer le problème, cela vous indiquera la solution.

ex 5 - repeteur

Coding Exercise: Begaiement
Ecrire une fonction récursive repeat qui prendra en argument un nombre n et une chaine de caractère txt, et qui renvoie une chaine de caractères qui contient n fois la chaine de caractères txt.
Exemple: repeat(5, "bla") renvoie blablablablabla
Aide

ex 6 - reverse

Coding Exercise: retournement
Ecrire une fonction récursive reverse qui prendra en argument une chaine de caractère txt, et qui renvoie la même chaine de caractères écrite à l'envers.
Exemple: reverse("bla") renvoie alb
Aide 1 Aide 2

ex 7 - Anagrammes

Coding Exercise: Anagrammes

ex 8 - la tête à toto

Dans cet exercice vous pouvez utiliser la méthode replace des objets string :

Testez dans un environnement python ou dans la console pour bien comprendre le fonctionnement de la méthode replace.

exemple

s = 'abacab'
print(s.replace('b','B'))
print(s.replace('b','B',1))
print(s.replace('bac','BAC'))
Quand vous avez bien compris le fonctionnement de replace(), il faut réfléchir au problème sur un cas simple.
Que renverront ces appels :

tete_a_toto('---0---' , 1) ?
tete_a_toto('---0---' , 2) ?
tete_a_toto('---0---' , 0) ?
Que faites vous à chaque fois ?

Coding Exercise: La tête à toto
Ecrire une fonction tete_a_toto qui répète n fois la substitution suivante : Remplacer tout les 0 par (0 + 0)


Exemples:
tete_a_toto("0",1) renvoie (0 + 0)
tete_a_toto("0",2) renvoie ((0 + 0) + (0 + 0))
Aide 1

ex 8 - Affichage récursif

Si vous avez réussit les 2 exercices précédents, celui là devrait vous sembler assez simple.

Coding Exercise: Print inline
Affichage d'une suite d'entiers Ecrire une fonction récursive printInLine qui prend 2 arguments i et k, et affiche les entiers entre i et k compris.


Par exemple :
printInLine(2, 5) doit afficher : 2 3 4 5 (séparés par des espaces).
Attention : printInLine ne renvoie rien, elle ne fait que des affichages....

Vous pourrez utiliser print(...,end=...) pour faire ce travail.
Aide 1 Aide 1

Avec une liste

ex 9 - test tri

Coding Exercise: Rangement
Ecrire une fonction récursive estTriee qui prend un argument tableau de type list, et qui renvoie True si le tableau est trié par ordre croissant, False sinon.

Par exemple, Si T1 = [1, 2, 3, 4, 5, 7, 8] et T2 = [1, 3, 2, 4, 5, 7, 8]
print(estTriee(T1)) affichera True
print(estTriee(T2)) affichera False
Aide 1

Des algos un peu plus complexes

ex 10 - somme digitale

Coding Exercise: Somme digitale
La somme digitale d'une nombre n est la somme de ces chiffres. Ecrivez une fonction récursive sommeDigital(n) qui prend en entrée un nombre positif n et retourne sa somme digitale. Par exemple, sommeDigital(2019) retournera 12 car 2 + 0 + 1 + 9 = 12. Indice #1 Indice #2 Indice #3

ex 11 - Conversion

On rappelle l'algorithme qui permet de convertir un nombre entier écrit en décimal en une chaine binaire équivalente.

fonction dec2bin(n) :
    chaine = ""
    tant que n est non nul :
        chaine = str(n%2) + chaine # on ajoute le reste de n/2 en tête dans la chaine
        n = n//2 # on recommence avec le quotient de n/2
    fin tant que
    renvoyer chaine
      
Coding Exercise: Division successives
Ecrire une fonction récursive dec2bin qui prend un argument un nombre entier, et qui affiche la représentation binaire de ce nombre (en chaine de caractères). Vous utiliserez la méthode des divisions successives par 2.
Par exemple, dec2bin(127) doit afficher 1111111

Avec deux fonctions qui s'appellent mutuellement

ex 12 - Exercice Pair Impair

Dans cet exercice, vous ne pouvez utiliser Vous ne devez utiliser les opérateur % et / ou //
Coding Exercise: pair impair
Ecrire 2 fonctions récursives est_pair et est_impair, qui s'appeleront mutuellement pour arriver à la solution. La fonction est_pair renvoie True si le nombre n est pair, False sinon, et inversement la fonction est_impair renvoie True si n est impair, False sinon.
On ne peut pas utiliser %,/ ou //.A vous de jouer. Indice

P4.1 Encodage des textes

Nous savons qu'un ordinateur est uniquement capable de traiter des données binaires, comment sont donc codés les textes dans un ordinateur ? Ou plus précisément, comment sont codés les caractères dans un ordinateur ?

ASCII

Avant 1960 de nombreux systèmes de codage de caractères existaient, ils étaient souvent incompatibles entre eux. En 1960, l'organisation internationale de normalisation (ISO) décide de mettre un peu d'ordre dans ce bazar en créant la norme ASCII (American Standard Code for Information Interchange) :

À chaque caractère est associé un nombre binaire sur 8 bits (1 octet). En fait, seuls 7 bits sont utilisés pour coder un caractère, le 8e bit n'est pas utilisé pour le codage des caractères. Avec 7 bits il est possible de coder jusqu'à 128 caractères ce qui est largement suffisant pour un texte écrit en langue anglaise (pas d'accents et autres lettres particulières).

Short Answer Exercise
"Le code Hexadécimal 52 correspond à quel caractère ?"
Correct!
Short Answer Exercise
"Quel est (sur 8 bits) le code binaire correspondant à ce caractère (donnez les 8 bits sans espace)?"
Correct!

Vérifions en demandant de l'aide à Python :

Example

Comme vous pouvez le constater, certains codes ne correspondent pas à des caractères (de 0 à (31)10), nous n'aborderons pas ce sujet ici.

ISO-8859-1

La norme ASCII convient bien à la langue anglaise, mais pose des problèmes dans d'autres langues, par exemple le français. En effet l'ASCII ne prévoit pas d'encoder les lettres accentuées. C'est pour répondre à ce problème qu'est née la norme ISO-8859-1. Cette norme reprend les mêmes principes que l'ASCII, mais les nombres binaires associés à chaque caractère sont codés sur 8 bits, ce qui permet d'encoder jusqu'à 256 caractères. Cette norme va être principalement utilisée dans les pays européens puisqu'elle permet d'encoder les caractères utilisés dans les principales langues européennes (la norme ISO-8859-1 est aussi appelée "latin1" car elle permet d'encoder les caractères de l'alphabet dit "latin")

Problème, il existe beaucoup d'autres langues dans le monde qui n'utilisent pas l'alphabet dit "latin", par exemple le chinois ou le japonnais ! D'autres normes ont donc dû voir le jour, par exemple la norme "GB2312" pour le chinois simplifié ou encore la norme "JIS_X_0208" pour le japonais.

Cette multiplication des normes a très rapidement posé des problèmes. Imaginons un français qui parle le japonais. Son traitement de texte est configuré pour reconnaître les caractères de l'alphabet "latin" (norme ISO-8859-1). Un ami japonais lui envoie un fichier texte écrit en japonais. Le français devra modifier la configuration de son traitement de texte afin que ce dernier puisse afficher correctement l'alphabet japonais. S'il n'effectue pas ce changement de configuration, il verra s'afficher des caractères ésotériques.

Unicode

Pour éviter ce genre de problème, en 1991 une nouvelle norme a vu le jour : Unicode

Unicode a pour ambition de rassembler tous les caractères existant afin qu'une personne utilisant Unicode puisse, sans changer la configuration de son traitement de texte, à la fois lire des textes en français ou en japonais

Unicode est uniquement une table qui regroupe tous les caractères existant au monde, il ne s'occupe pas de la façon dont les caractères sont codés dans la machine. Unicode accepte plusieurs systèmes de codage : UTF-8, UTF-16, UTF-32. Le plus utilisé, notamment sur le Web, est UTF-8.

Pour encoder les caractères Unicode, UTF-8 utilise un nombre variable d'octets : les caractères "classiques" (les plus couramment utilisés) sont codés sur un octet, alors que des caractères "moins classiques" sont codés sur un nombre d'octets plus important (jusqu'à 4 octets). Un des avantages d'UTF-8 c'est qu'il est totalement compatible avec la norme ASCII : Les caractères Unicode codés avec UTF-8 ont exactement le même code que les mêmes caractères en ASCII.

La richesse de 'utf-8'

La norme UTF-8 est une table qui associe un code à chaque caractère, mais quand la table ASCII contenait 127 caractères, la table UTF-8 en contient plus de 1 million ! Quelques exemples :

Example

Voici un lien vers la table des caractères codés en UTF-8 : https://www.utf8-chartable.de/

Exercice

Short Answer Exercise
"Quel est le code hexa correspondant au caractère 'b' ?"
Correct!
Short Answer Exercise
"Quel est le code hexa correspondant au caractère '=' ?"
Correct!

Vérifiez dans la table ASCII qu'il s'agit bien du même code.

Short Answer Exercise
"Quel est le caractère correspondant au code UTF-8 décimal 91 ?"
Correct!

Codage avec Python

On veux écrire un code en python qui donne la chaîne binaire (en UTF-8) d'un texte.

Les caractère UTF-8 sont codés sur 1 à 4 octets. Les caractères de l'ancienne table ascii sont codés en 1 octet, le premier bit étant un zéro. Ce sont des les mêmes codes que les codes ascii.

Pour ajouter des caractères on a convenu que l'on met le premier bit à 1 pour indiquer qu'il y a plus d'un octet. On ne va pas entrer dans les détails de l'encodage, nous allons nous limiter à des caractères de la tables ASCII.

L'objet de l'exercice est donc d'afficher la suite de 0 et 1 correspondant à un texte dont tout les caractères sont présentés en ascii.

Exemple :

on veux convertir le mot « Arbre », détaillons comment on va coder le A :

A → (65)10 → (01000001)2 codé sur 1 octet

code= ord("A") → code= 65

chaineBin = format(code,'08b') → chaineBin = '01000001' ceci est le code binaire (sur 8 bits) de 65, mais attention, c'est une chaine de charactères !

vous pouvez bien entendu grouper ces deux instructions : chaineBin('A')=format(ord('A'),'08b') vous donnera le code binaire de A.

Prévisualiser(ouvre un nouvel onglet)

Coding Exercise
Ecrire une fonction text2bin(txt : str) -> str
La fonction prend en entrée une chaine, et revoie la chaine binaire correspondante, utilisant les codes UTF-8.
Votre code sera testé avec une chaine (cf ci-dessous) qui sera affichée avec l'appel d'uune fonction decoupe() que vous n'avez pas besoin de coder.
Aide

P3.4 Gestion de fichiers

Utilisez des fichiers

Dans cette partie vous allez utiliser l'environnement de développement de votre choix (EduPython, Thonny, Anaconda, Pyzo...).
Vous allez gérer des fichiers dans des répertoires.
Si vous êtes au lycée (et vous pourrez faire de même chez vous), il est probable que vous allez travailler sur votre clef USB et que celle-ci est installée sur D:\

Avant de commencer

Nous allons beaucoup travailler sur des répertoires et des fichiers, autrement dit sur votre disque ou clef ou autre support de stockage de données. Donc je vais vous donner quelques informations générales avant de commencer pour que, malgré vos différents systèmes et configurations, vous puissiez essayer les instructions que je vais vous montrer.

Mais d'abord, pourquoi lire ou écrire dans des fichiers ?

Peut-être que vous ne voyez pas trop l'intérêt de savoir lire et écrire dans des fichiers, hormis quelques applications de temps à autre. Mais souvenez-vous que, quand vous fermez votre programme, aucune de vos variables n'est sauvegardée. Or, les fichiers peuvent être, justement, un excellent moyen de garder les valeurs de certains objets pour pouvoir les récupérer quand vous rouvrirez votre programme. Par exemple, un petit jeu peut enregistrer les scores des joueurs.

Si, dans notre TP ZCasino, nous avions pu enregistrer la somme que nous avions en poche au moment de quitter le casino, nous aurions pu rejouer sans repartir de zéro.

AVANT DE COMMENCER

Il faut créer un répertoire JUPYTER sur votre clef usb (gardez les majuscules).Nous considèrerons ce repertoire D:\JUPYTER comme la racine (le point de départ).
Créez ensuite un répertoire lireEcrireFichier dans le répertoire JUPYTER.

SE REPERER

Lancez Edupython et saisir dans la console :

>>>import os
>>>print os.getcwd()
Vous obtenez par exemple :

'C:/users/JLT/Documents'

(Ce ne sera sans doute pas celà pour vous, mais cette commande indique dans quel répertoire que vous travaillez en ce moment).

Je vous conseille, que vous soyez sous Windows ou non, d'utiliser le symbole / pour décrire un chemin.

Vous pouvez utiliser, en le doublant, l'antislash \\ mais, si vous oubliez de le doubler, vous aurez des erreurs. Je vous conseille donc d'utiliser le slash /, cela fonctionne très bien même sous Windows.

Quand vous lancez un programme Python directement, par exemple en faisant un double-clic dessus, le répertoire courant est celui d'où vous lancez le programme.

Par exemple, Si vous avez un fichier mon_programme.py contenu sur le disqueC:/users/Bureau, le répertoire de travail courant quand vous lancerez le programme sera C:/users/Bureau.

Chemins relatifs et absolus

Pour décrire l'arborescence d'un système, on a deux possibilités :

  • les chemins absolus ;
  • les chemins relatifs.

Le chemin absolu

Quand on décrit une cible (un fichier ou un répertoire) sous la forme d'un chemin absolu, on décrit la suite des répertoires menant au fichier. Sous Windows, on partira du nom de volume (C:\,D:\…). Sous les systèmes Unix, ce sera plus vraisemblablement depuis /.

Par exemple, sous Windows, si on a un fichier nomméfic.txt, contenu dans un dossiertest, lui-même présent sur le disqueC:, le chemin absolu menant à notre fichier seraC:\test\fic.txt.

Le chemin relatif

Quand on décrit la position d'un fichier grâce à un chemin relatif, cela veut dire que l'on tient compte du dossier dans lequel on se trouve actuellement. Ainsi, si on se trouve dans le dossierC:\testet que l'on souhaite accéder au fichierfic.txtcontenu dans ce même dossier, le chemin relatif menant à ce fichier sera tout simplementfic.txt.

Maintenant, si on se trouve dansC:, notre chemin relatif sera test/fic.txt.

Quand on décrit un chemin relatif, on utilise parfois le symbole..qui désigne le répertoire parent. Voici un nouvel exemple :

  • C:
    • test
      • rep1
        • fic1.txt
      • rep2
        • fic2.txt
        • fic3.txt

C'est dans notre dossiertestque tout se passe. Nous avons deux sous-répertoires nommésrep1etrep2. Dansrep1, nous avons un seul fichier :fic1.txt. Dansrep2, nous avons deux fichiers :fic2.txtetfic3.txt.

Si le répertoire de travail courant estrep2et que l'on souhaite accéder àfic1.txt, notre chemin relatif sera donc..\rep1\fic1.txt.

J'utilise ici des antislashs parce que l'exemple d'arborescence est un modèle Windows et que ce sont les séparateurs utilisés pour décrire une arborescence Windows. Mais, dans votre code je vous conseille quand même d'utiliser un slash(/).

Nous allons commencer à lire avant d'écrire dans un fichier. Pour l'exemple donc, je vous invite à créer :

1- Un répertoire Data dans D:/JUPYTER/lireEcrireFichier

2- un nouveau fichier dans ce répertoire. Je suis en manque flagrant d'inspiration, je vais donc l'appelerfichier.txt. A l'aide d'un éditeur sans mise en forme (tel que le bloc-notes Windows, ou notepad++, mais veillez à enregistrer au format txt ) écrivons dans ce fichier :

C'est le contenu du fichier. Spectaculaire non ?

la fonction open

Dans edupython

Vous devez maintenant, dans python, changer de répertoire de travail courant.
Pour cela, vous devez utiliser une fonction du module os, qui s'appelle chdir (abréviantion de Change Directory).

>>> os.chdir("D:/JUPYTER/lireEcrireFichier")
>>>

Lecture et écriture dans un fichier

Ouverture du fichier

D'abord, il nous faut ouvrir le fichier avec Python. On utilise pour ce faire la fonctionopen, disponible sans avoir besoin de rien importer. Elle prend en paramètre :

  • le chemin (absolu ou relatif) menant au fichier à ouvrir ;
  • le mode d'ouverture.

Le mode est donné sous la forme d'une chaîne de caractères. Voici les principaux modes :

  • 'r': ouverture en lecture (Read).
  • 'w': ouverture en écriture (Write). Le contenu du fichier est écrasé. Si le fichier n'existe pas, il est créé.
  • 'a': ouverture en écriture en mode ajout (Append). On écrit à la fin du fichier sans écraser l'ancien contenu du fichier. Si le fichier n'existe pas, il est créé.

Il existe d'autres modes, mais pour nous cela sera suffisant.

Ici nous souhaitons lire le fichier. Nous allons donc utiliser le mode'r'.

>>> mon_fichier = open("Date/fichier.txt", "r")
>>> mon_fichier
<_io.TextIOWrapper name='fichier.txt' encoding='cp1252'>
>>> type(mon_fichier)
<class '_io.TextIOWrapper'>
>>>
L'encodage précisé quand on affiche le fichier dans l'interpréteur peut être très différent suivant votre système. Ici, je suis dans l'interpréteur Python dans Windows et l'encodage choisi est donc un encodage Windows propre à la console. Ne soyez pas surpris s'il est différent chez vous. Nous verrons un peu plus loin comment choisir un encodage plus adapté.

La fonctionopencrée donc un fichier. Elle renvoie un objet de la classeTextIoWrapper. Par la suite, nous allons utiliser des fonctions liées à cette classe pour interagir avec le fichier.

Le type de l'objet doit vous surprendre quelque peu. Cela aurait très bien pu être un typefileaprès tout. En fait,openpermet d'ouvrir un fichier, maisTextIoWrapperest utilisé dans d'autres circonstances, pour afficher du texte à l'écran par exemple. Bon, cela ne nous concerne pas trop ici, je ne vais pas m'y attarder.

Fermer le fichier

N'oubliez pas de fermer un fichier après l'avoir ouvert. Si d'autres applications, ou d'autres morceaux de votre propre code, souhaitent accéder à ce fichier, ils ne pourront pas car le fichier sera déjà ouvert. C'est surtout vrai en écriture, mais prenez de bonnes habitudes. La méthode à utiliser estclose:

>>> mon_fichier.close()
>>>

Lire l'intégralité du fichier

Pour ce faire, on utilise la méthodereadde la classeTextIoWrapper. Elle renvoie l'intégralité du fichier :

>>> mon_fichier = open("fichier.txt", "r")
>>> contenu = mon_fichier.read()
>>> print(contenu)
C'est le contenu du fichier. Spectaculaire non ?
>>> mon_fichier.close()
>>>
Quoi de plus simple ? La méthodereadrenvoie tout le contenu du fichier, que l'on capture dans une chaîne de caractères. Notre fichier ne contient pas de saut de ligne mais, si c'était le cas, vous auriez dans votre variablecontenules signes\ntraduisant un saut de ligne.

Maintenant que vous avez une chaîne, vous pouvez naturellement tout faire : la convertir, tout entière ou en partie… bref, tout est possible.

Écriture dans un fichier

Bien entendu, il nous faut ouvrir le fichier avant tout. Vous pouvez utiliser le modewou le modea. Le premier écrase le contenu éventuel du fichier, alors que le second ajoute ce que l'on écrit à la fin du fichier. À vous de voir en fonction de vos besoins. Dans tous les cas, ces deux modes créent le fichier s'il n'existe pas.

Écrire une chaîne

Pour écrire dans un fichier, on utilise la méthode write en lui passant en paramètre la chaîne à écrire dans le fichier. Elle renvoie le nombre de caractères qui ont été écrits. On n'est naturellement pas obligé de récupérer cette valeur, sauf si on en a besoin.

Voici un exemple : nous allons d'abord écrire 2 lignes dans le fichier, puis les relire :

>>> mon_fichier = open("fichier.txt", "w") # Argh j'ai tout écrasé !
>>> mon_fichier.write("Premier test d'écriture dans un fichier via Python")

50
>>> mon_fichier.write('ligne2')
6
>>> mon_fichier.close()
>>> mon_fichier = open("fichier.txt", "r") 
>>> c=mon_fichier.read()
>>> c
"Premier test d'écriture dans un fichier via Pythonligne2"
>>> 
Vous pouvez vérifier que votre fichier contient bien le texte qu'on y a écrit. Vous avez de fortes chance d'observer 2 défauts :

  • L'accent de écriture est mal transcrit
  • La deuxième ligne est mis au bout de la première

encodage et caractères de fin de ligne

Pour le problème des accents, c'est un problème d'encodage du texte, et nous aborderons plus tard cette question. Pour y remédier, lors de l'ouverture (en écriture comme en lecture), vous aller toujours prend l'habitude de préciser l'encodage avec l'option encoding='utf-8'

Pour le problème de retour à la ligne, il suffit d'ajouter un caractère de fin de ligne lors de l'écriture : \n.

Mais ce caractère devra alors être pris en compte car il sera relu....

>>> mon_fichier = open("fichier.txt", "w", encoding='utf-8') 
mon_fichier.write("Premier test d'écriture dans un fichier via Python\n")
51
>>> mon_fichier.write('ligne2'+'\n')
7
>>> mon_fichier.close()
>>> mon_fichier = open("fichier.txt", "r" , encoding='utf-8') 
>>> c=mon_fichier.read()
>>> c
"Premier test d'écriture dans un fichier via Python\nligne2\n"
>>> print(c)
Premier test d'écriture dans un fichier via Python
ligne2
Vous pouvez regarder dans fichier.txt, vous verrez que les \n n'apparaissent pas et que le texte est bien sur 2 lignes.

ecrire autre chose que du texte

Écrire d'autres types de données

La méthodewriten'accepte en paramètre que des chaînes de caractères. Si vous voulez écrire dans votre fichier des nombres, des scores par exemple, il vous faudra les convertir en chaîne avant de les écrire et les convertir en entier après les avoir lus.

la méthode with (recommandée)

Le mot-clé with

Ne désespérez pas, il ne nous reste plus autant de mots-clés à découvrir… mais quelques-uns tout de même. Et même certains dont je ne parlerai pas…

On n'est jamais à l'abri d'une erreur. Surtout quand on manipule des fichiers. Il peut se produire des erreurs quand on lit, quand on écrit… et si l'on n'y prend pas garde, le fichier restera ouvert.

Comme je vous l'ai dit, c'est plutôt gênant et cela peut même être grave. Si votre programme souhaite de nouveau utiliser ce fichier, il ne pourra pas forcément y accéder, puisqu'il a déjà été ouvert.

Il existe un mot-clé qui permet d'éviter cette situation :with. Voici sa syntaxe :

with open(mon_fichier, mode_ouverture) as variable:
    # Opérations sur le fichier
On trouve dans l'ordre :

  • Le mot-clé with, prélude au bloc dans lequel on va manipuler notre fichier. On peut trouver with dans la manipulation d'autres objets mais nous ne le verrons pas ici.
  • Notre objet. Ici, on appelleopenqui va renvoyer un objetTextIOWrapper(notre fichier).
  • Le mot-cléasque nous avons déjà vu dans le mécanisme d'importation et dans les exceptions. Il signifie toujours la même chose : « en tant que ».
  • Notre variable qui contiendra notre objet. Si la variable n'existe pas, Python la crée.

Un exemple :

>>> with open('fichier.txt', 'r') as mon_fichier:
...     texte = mon_fichier.read()
... 
>>>
Cela ne veut pas dire que le bloc d'instructions ne lèvera aucune exception (erreur).

Cela signifie simplement que, si une exception se produit, le fichier sera tout de même fermé à la fin du bloc.

Le mot-cléwithpermet de créer un "context manager" (gestionnaire de contexte) qui vérifie que le fichier est ouvert et fermé, même si des erreurs se produisent pendant le bloc. Vous verrez plus loin d'autres objets utilisant le même mécanisme.

Vous pouvez appelermon_fichier.closedpour vérifier que le fichier est refermé. Si le fichier est fermé,mon_fichier.closedvaudraTrue.

Il est inutile, par conséquent, de fermer le fichier à la fin du blocwith. Python va le faire tout seul, qu'une exception soit levée ou non. Je vous encourage à utiliser cette syntaxe, elle est plus sûre et plus facile à comprendre.

lire ligne par ligne

Lire tout le fichier d'un seul bloc n'est pas forcément idéal, nous allons envisager d'autres façon de lire, ligne par ligne. Pour cela on aura avantage à utiliser la méthode with

with open('fichier.txt', 'r' , ecoding='utf-8') as mon_fichier:
    for i in mon_fichier.readlines() :
        print(i)
qui donne dans la console :

Premier test d'"criture dans un fichier via Python

ligne2
Pourquoi y'a-t-il un saut d'une ligne entre les 2 lignes ? A cause des \n !

Changez votre code ainsi :

with open('fichier.txt', 'r' , ecoding='utf-8') as mon_fichier:
    for i in mon_fichier.readlines() :
        ligne=i.replace('\n','')
        print(ligne)
Cette fois il affiche bien :

Premier test d'écriture dans un fichier via Python
ligne2
Cette fois on a l'accentuation, et les retour de fin de ligne :

En résumé

Récapitulons le code complet lecture et écriture :

with open('fichier.txt', 'w' , encoding='utf-8') as mon_fichier:
    mon_fichier.write("Premier test d'écriture dans un fichier via Python\n")
    mon_fichier.write("ligne2\n")
with open('fichier.txt', 'r' , encoding='utf-8') as mon_fichier:
    for i in mon_fichier.readlines() :
        ligne=i.replace('\n','')
        print(ligne)
  • On peut ouvrir un fichier en utilisant la fonction open prenant en paramètre le chemin vers le fichier et le mode d'ouverture, il est bon d'ajouter la norme d'encodage avec encoding='utf-8'.
    1. On peut lire dans un fichier en utilisant la méthode read.
    2. On peut écrire dans un fichier en utilisant la méthodewrite.
    3. Un fichier doit être refermé après usage en utilisant la méthodeclose.
    On peut (et c'est préférable) utilise la méthode with (il faut aussi préciser le chemin, le mode et l'encodage)
    • Dans le bloc with on effectue les opération (read ou write, mais aussi tout ce qu'on voudra)
    • Quand on sort du bloc with (on enlève l'indentation) python referme le fichier.
    • On peut lire ligne par ligne dans une boucle for (cela est aussi possible avec open mais moins lisible et moins fiable)

P1 TP final

TP : tous au ZCasino

Nous allons nous atteler au développement d'un petit jeu de casino. Vous trouverez le détail de l'énoncé plus bas, ainsi que quelques conseils pour la réalisation de ce mini projet.

Si, durant ce travail, vous sentez que certaines connaissances vous manquent, revenez en arrière ; prenez tout votre temps, on n'est pas pressé !

Notre sujet

Vous devez écrire un petit programme que nous appellerons ZCasino. Il s'agira d'un petit jeu de roulette très simplifié dans lequel vous pourrez miser une certaine somme et gagner ou perdre de l'argent (telle est la fortune, au casino !). Quand vous n'avez plus d'argent, vous avez perdu.

Notre règle du jeu

Bon, la roulette, c'est très sympathique comme jeu, mais un peu trop compliqué pour un premier projet. Alors, on va simplifier les règles et je vous présente tout de suite ce que l'on obtient :

  • Le joueur mise sur un numéro compris entre 0 et 49 (50 numéros en tout). En choisissant son numéro, il y dépose la somme qu'il souhaite miser.
  • La roulette est constituée de 50 cases allant naturellement de 0 à 49. Les numéros pairs sont de couleur noire, les numéros impairs sont de couleur rouge. Le croupier lance la roulette, lâche la bille et quand la roulette s'arrête, relève le numéro de la case dans laquelle la bille s'est arrêtée. Dans notre programme, nous ne reprendrons pas tous ces détails « matériels » mais ces explications sont aussi à l'intention de ceux qui ont eu la chance d'éviter les salles de casino jusqu'ici. Le numéro sur lequel s'est arrêtée la bille est, naturellement, le numéro gagnant.
  • Si le numéro gagnant est celui sur lequel le joueur a misé (probabilité de 1/50, plutôt faible), le croupier lui remet 3 fois la somme misée.
  • Sinon, deux situations possibles :
    1. le croupier regarde si le numéro misé par le joueur est de la même couleur que le numéro gagnant (s'ils sont tous les deux pairs ou tous les deux impairs). Si c'est le cas, le croupier lui remet 50 % de la somme misée (et il reprend sa mise).
    2. Si ce n'est pas le cas, le joueur ne gagne rien et perd sa mise.

Dans les deux scénarios gagnants vus ci-dessus (le numéro misé et le numéro gagnant sont identiques ou ont la même couleur), le croupier remet au joueur la somme initialement misée avant d'y ajouter ses gains. Cela veut dire que, dans ces deux scénarios, le joueur récupère de l'argent. Il n'y a que dans le troisième cas qu'il perd la somme misée. On utilisera pour devise le dollar $ à la place de l'euro pour des raisons d'encodage sous la console Windows.

Organisons notre projet

Pour ce projet, nous allons avoir besoin d'un module : le module random

Un peu d'aide pour commencer...

Le module random

Dans ce module, nous allons nous intéresser particulièrement à la fonction randrange qui peut s'utiliser de deux manières :

  • en ne précisant qu'un paramètre (randrange(6)renvoie un nombre aléatoire compris entre 0 et 5) ;
  • en précisant deux paramètres (randrange(1, 7): renvoie un nombre aléatoire compris entre 1 et 6, ce qui est utile, par exemple, pour reproduire une expérience avec un dé à six faces).

Pour tirer un nombre aléatoire compris entre 0 et 49 et simuler ainsi l'expérience du jeu de la roulette, nous allons donc utiliser l'instruction randrange(50).

Il existe d'autres façons d'utiliser randrange mais nous n'en aurons pas besoin ici.

N'hésitez pas à faire des tests (ouvrez pour cela le code dans la console) et essayez plusieurs syntaxes de la fonction randrange.

Elle se trouve dans le module random, il faudra l'importer avec l'instruction import comme montré ci-dessous (que vous placerez en tout début de votre code) :

Example

La mise : un nombre entier

Vous l'avez peut-être bien noté, dans l'explication des règles je spécifiais que si le joueur misait sur la bonne couleur, il obtenait 50% de sa mise. Oui mais… c'est quand même mieux de travailler avec des entiers. Si le joueur mise 3$, par exemple, on lui donne 1,5$. il remet en jeu 1.5$ et gagne à nouveau 50%, il va gagner 0.75$, et si cela se poursuit, on risque d'arriver à des nombres flottants avec beaucoup de chiffres après la virgule.

Pour éviter cela, on va instaurer la règle suivante : le joueur doit toujours miser un nombre entier.

À vous de jouer

Concrètement que devez vous faire ?

  • Initialiser le jeu :
    - le joueur dispose d'une somme de départ, qu'on va nommer le solde. Vous initialiserez ce solde. Il faudra aussi initialiser une variable mise à une valeur non nulle, elle sera utile pour lancer la boucle ci-dessous.
  • Commencer à jouer
    - on entre dans une boucle while (tant que). Tant que le jeu n'est pas terminé.
    Nous dirons que le jeu se termine si le joueur n'a plus d'argent (le solde est nul) ou s'il mise 0. tant que ces deux conditions ne sont pas réunis, le jeu continue.
    A chaque partie :
    - le joueur choisit une case et mise une somme (vous utiliserez input() pour que le code connaisse ces deux valeurs).
    - on lance la roulette (tirage aléatoire avec random)
    - on détermine le gain et on met à jour le solde du joueur.
  • Fin de la partie
    Afficher le solde du joueur

Pour déterminer le gain :

Si la case misée est égale au résultat du tirage, le gain est trois fois la mise

Sinon, si le tirage et la case misée ont la même parité, le gain est 1.5 fois la mise
Comment savoir si 2 nombre ont la même parité ? Testez le code ci-dessous, vos pouvez l'ouvrir en console pour faire varier les valeurs de a et b...

Example

Sinon le gain est -1 fois la mise

À vous de jouer !

Bonus :

Bonus1 : Votre code peut vérifier que la somme misée par le joueur est un entier :

exemple, si je veux vérifier qu'une valeur entrée est un entier :

Example

Bonus2 : Votre code peut vérifier que la somme misée est inférieure ou égale au solde. Inspirez vous du bonus 1 pour réaliser cette vérification.

Auteur : Vincent Le Goff

P3.4 Les listes

Prérequis pour ce cours:

  • Les boucles et instructions conditionnelles
  • Les fonctions

Rappel sur le parcours de listes avec les indices

Les listes sont maintenant des objets familiers, vous y êtes habitués. Rappelons ce que nous avons déjà vu, concernant les parcours de listes :

Parcours de liste Avec les indices

Example: Parcours de liste sur les indices
Parcours de liste avec les indices

Dans le code ci-dessus on parcours la liste lst, et pour chaque élément on affiche la valeur. Mais ce n'est pas très pratique car pour faire ce parcours séquentiel (on référence séquentiellement les valeurs de la liste) on a besoin, dans le in range(..) de connaître le nombre d'éléments de la liste.

Connaitre la longueur (le nombre d'éléments) d'une liste

la commande len(liste) nous donne le nombre d'éléments de la liste.

Le code ci-dessus peut donc être écrit ainsi :

Example: La fonction len()
Parcours de liste avec les indices et la fonction len()

Ajoutez des éléments dans la liste pour observer que le parcours s'effectue toujours correctement sur tousles éléments jusqu'à la fin.

Les Tranches

Vous avez déjà vu comment on peut accéder à la valeur d'un élément du tableau. Il est aussi possible d'accéder à une partie du tableau.

Example: Le slicing
les tranches (slices)

Ce code affiche un tableau avec les éléments de lst de l'indice 2 à l'indice 4, c'est à dire [2,3,4]

Souvent on souhaite en réalité une partie de longueur variable, par exemple tous les éléments du tableau à partir du 3ème. Pour cela on omet l'indice de fin, cela signifie : jusqu'à la fin

Example: Le slicing
les tranches à part de ... (slices)

Ce code affiche un tableau avec les éléments de lst de l'indice 5 jusqu'à la fin : [5,6,7]

De la même façon on peut omettre l'indice de début, ceci signifiant qu'on prend tout depuis le début :

Example: Le slicing
les tranches jusqu'à l'élément ... (slices)

Ce code affiche un tableau avec les éléments de lst du début jusqu'à l'indice 4, c'est à dire [0,1,2,3,4]

Enfin, une spécificité de Python (rarement disponible dans d'autres langages), est d'utiliser une syntaxe avec des valeurs négatives. Les indices négatifs n'existent pas, mais en python ils sont interprété comme "en partant de la fin". Ainsi :

Example: Le slicing
les tranches jusqu'à l'élément ... (slices)

Ce code affiche la dernière valeur de lst : 7

Et bien sur on peut combiner cette dernière notation avec les slices :

Example: Le slicing
les tranches jusqu'à l'élément ... (slices)

Ce code affiche les valeur de la première à l'avant dernière : [0,1,2,3,4,5,6]

Parcours de liste sur les éléments

parcours de toute une liste

Il existe une autre façon de parcourir une liste, qui n'utilise pas les indices des éléments, mais les éléments eux mêmes :

Example: Parcours sur les éléments
les tranches jusqu'à l'élément ... (slices)

Le code ci-dessus parcours aussi la liste lst, et pour chaque élément on affiche la valeur. Mais au lieu d'avoir un indice i allant de 0 à len(lst)-1, i prend successivement les valeurs des éléments de la liste.

Ces deux façons de parcourir une liste sont fondamentales et doivent être bien comprises.

Exercice

double()

Vous donnerez la solution en utilisant un parcours de listes sur les indices.

Coding Exercise: double
Ecrire une fonction double(tab) qui renvoi le tableau en remplaçant chaque élément par lui même multiplié par 2.

Ecrire une fonction max_lst(tab) qui renvoi le max d'un tableau.


Vous donnerez la solution en utilisant un parcours de listes sur les indices, puis une autre en utilisant le parcours de liste sur les éléments.

L'algorithme est le suivant :

max ← tab[0]
pour i allant de 1 à N-1 :
    si tab[i]>max:
        max ← tab[i]
renvoyer max

l'algorithme ci contre est donné en faisant un parcours sur les indices, pour le parcours sur les éléments vous devrez adapter...

Coding Exercise: Maximum avec parcours sur les indices
Ecrire une fonction max_lst(tab : list) -> float qui renvoie la plus grande valeur du tableau.
Vous ferez un parcours de la liste sur les indices.
Coding Exercise: Maximum avec parcours sur les éléments
Ecrire une fonction max_lst(tab : list) -> float qui renvoie la plus grande valeur du tableau.
Vous ferez un parcours de la liste sur les éléments.
Vous ne pouvez pas utiliser la fonction len() dans cet exercice.

Commandes essentielles

Préambule : objets, attributs et méthodes

Python est un langage très orienté objets. Pour le moment vous ne pouvez pas savoir ce que cela signifie mais on va simplement résumer cela en trois idées :

  • Toutes les variables sont des objets.
  • Les objets ont des attributs : des valeurs qui leurs sont attribuées et qu'on peut connaitre avec la syntaxe : objet.attribut
  • Les objets ont aussi des méthodes : ce sont des fonctions qu'on peut utiliser pour faire des opérations variées sur nos objets. Pour utiliser une méthode d'un objet, on utilise la syntaxe : objet.methode()

Pour le moment vous n'avez pas besoin d'en savoir davantage sur les objets, mais vous allez dès à présent découvrir les méthodes de l'objet liste.

Ajouter des éléments en fin de liste

la méthode append() : lst.append(element) ajoute un élément à la fin de la liste.

exemple 1 :

Example: Ajouter en fin de liste

exemple 2 :

Example: Initialiser une liste avec append

exemple 3 :

Example: Un peu différent

Retirer un élément

Il existe plusieurs façon de retirer des éléments d'une liste :

La méthode remove : a.remove(element) retire la 1ère occurence de element dans la listeExemple 1

Example: retirer une valeur donnée :

Ce code génère une erreur : ValueError: list.remove(x): x not in list car 13 n'est pas dans la liste.

Example: retirer une valeur donnée :

La fonction del : del a[i] supprime l'élément à l'indice i

Ceci n'est pas une méthode à proprement parler et sa syntaxe est donc différente : del a[i] et non a.del(i) comme pour remove ou pop

Example: retirer une valeur à l'index i :

a vaut : [1,2,4,3,2,1] après exécution de ce code.

ce code génère une erreur : IndexError: list assignment index out of range car 15 > len(a)

Example: retirer une valeur à l'index i :

La méthode pop() : a.pop(i) : supprime l'element d'indice i et renvoie sa valeur.

cette méthode ressemble beaucoup à la précédente mais

  • d'une part c'est une méthode (appel avec a.pop(i) et non pop a[i])
  • par ailleurs, pop renvoie la valeur de l'élément supprimé.

Typiquement c'est la méthode pour un tirage sans remise, type le loto :

Example: retirer une valeur à l'index i et récupérer la valeur :
  • Au départ a=[1,2,3,4...49]
  • A chaque tirage on retire un élément, mais du coup, si j'ai retire le 2 par exemple, l'élément d'indice 1 est maintenant 3 car a= [1,3,4...49].
  • Il n'y a donc plus de correspondance entre l'indice et la valeur. Cela permet d'empêcher de tirer 2 fois le même numéro (tirage sans remise) mais pour connaitre la valeur correspondant à l'indice choisi, pop est la meilleure méthode.

Tester la présence d'un élément dans la liste

x in a : True si x est un élément de la liste a, False sinon.


>>> a=[1,2,3,4,3,2,1]
>>> 3 in a
True
>>> 13 in a 
False

Conversion de listes en chaine, et réciproquement

convertir une chaîne en liste :

Example: convertir une chaine en liste

Convertir une liste en chaine, avec join :

Example: convertir une liste en chaine

D'autres instructions sont importantes et doivent être connues (voir plus ici) mais nous les verrons ultérieurement.

lst.count()

lst.reverse()

lst.index()

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).

Example: 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

Example

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.

Example

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 !

Example

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

Example

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.

Example

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 :

Example

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
Example

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.
Coding Exercise
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
Coding Exercise
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
Coding Exercise: 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 :

Example

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 :

Example

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

Example
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 :

Example

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 ;

Example

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.

Scramble Exercise: 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
Example
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.
Example
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.

Example
Produit des entiers de 1 à 5
Multiple Choice Exercise
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

Example: (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.

Coding Exercise
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.

Coding Exercise
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)

Coding Exercise
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 :
Example

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 :
Example

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.
Example

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.

Example

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.

Coding Exercise: 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
Coding Exercise: Parité
Clique sur Visualiser pour debugguer ce code qui renvoi toujours None.