cours CI

Première partie : les pyBox

I. Les autotests : tester les variables ou les fonctions, aléatoire ou choisi

A) pour tester le contenu d'une variable

[pyBox
slug='auto_a'
title='exemple1'

defaultcode='# ecrire un code qui crée une variable x et lui affecte la valeur 3
votre code ne doit produire aucune sortie en console
'
solver='x=3'
autotests='x'
] Testez avec rien, puis avec x=1 puis avec x=3 dans le code

[/pyBox]
L'autotest génèrera une erreur si la variable x est non définie dans le code élève ou si elle n'a pas la même valeur que lors de l'exécution du solver.

Exercice de code : exemple1
Testez avec rien, puis avec x=1 puis avec x=3 dans le code

On peut cumuler l'autotest avec une sortie console. par exemple :

[pyBox
slug='auto_a2'
defaultcode='# ecrire un code qui crée une variable x et lui affecte la valeur 3
votre code doit ensuite afficher : x = 3
'
solver='x=3
print("x = ",x)
'
autotests='x'
] Testez avec x=3 dans le code, sans le print, puis avec le print.
[/pyBox]
En plus de l'autotests, les sorties consoles sont testées aussi.

Exercice de code
Testez avec x=3 dans le code, sans le print, puis avec le print.

B) pour tester une fonction

C'est ce que j'utilise le plus, sauf début d'année en première (évidement).

[pyBox
slug='auto_b'
defaultcode='def ma_fonction(n:int) -> int:
    # votre code ici
'
solver='def ma_fonction(n):
    return n**2
'
autotests='ma_fonction(3)
ma_fonction(2)
ma_fonction(_rint(3,9))
'
] Ecrire une fonction qui prend en paramètre un entier n et renvoi la valeur de n2.

On peut aussi utiliser des balises latex : [latex size=2](\frac{3}{2})^2[/latex]
[/pyBox]
L'autotests va appeler le solver avec les appels définis, et comparer avec les résultats fournis par le code élève pour les mêmes appels.

Exercice de code
Ecrire une fonction qui prend en paramètre un entier n et renvoi la valeur de n2.
On peut aussi utiliser des balises latex : (\frac{3}{2})^2

vous noterez bien la ligne : ma_fonction(_rint(3,9))

_rint est un raccourci pour random.randint et on a pas besoin d'importer random. Ce test sera donc aléatoire, ce qui évite dans certains cas des codes qui affichent ou renvoi la bonne réponse sans faire vraiment le code !

(quoique... j'ai vu un élève faire ça puis m'appeler pour valider, sa boite était verte, mais si on exécutait ça marchait une fois sur 10....)

II. le precode

C'est un code qui sera excuté, aussi bien avant le solver qu'avant le code de l'élève. On peut y mettre des import, des fonctions, des variables.

Les variables et les fonctions qu'on nomme avec un _ : _truc ne seront pas visibles pour l'élèves même à l'exécution.

[pyBox
title="précode"
slug='precode'
precode = 'def afficher(val,name):
print(name,"=",val)
var = 1
_var = _rint(1,100)
'
defaultcode='# votre code doit créer une variable x qui vaut 2
et l\'afficher en utilisant la fonction afficher
Vous afficherez ensuite le contenu de deux variables prédéfinies
dans le précode nommées var et _var
'
solver='x = 2
afficher(x,"x")
afficher(var,"var")
afficher(_var,"_var")
'
autotests='afficher(3,"x")
afficher(_rint(3,9),"valeur aléatoire")
'
]Dans cet exercice on a prédéfini (dans le précode) une fonction afficher(valeur,nom) qui affiche la valeur d\'une variable sous la forme nom = valeur.

Exemple (si x vaut 2) : afficher(x,"x") affichera x = 2


le code définit également deux variables, var et _var, que vous devez afficher de la même façon avec la fonction afficher.
[/pyBox]
Exercice de code : précode
Dans cet exercice on a prédéfini (dans le précode) une fonction afficher(valeur,nom) qui affiche la valeur d\'une variable sous la forme nom = valeur.
Exemple (si x vaut 2) : afficher(x,"x") affichera x = 2

le code définit également deux variables, var et _var, que vous devez afficher de la même façon avec la fonction afficher.

Attention : l'autotests exécute les appels, mais ici la fonction ne revoie rien mais affiche en console. Le test sera pris en compte mais via les sorties console.

Notez bien aussi :

Before running your code: We defined a function afficher and var equal to 1.

la variable _var n'est pas montrée, mais elle existe.

III. repeats avec generator : Tests aléatoires

On ajoute un élément generator qui génère une (ou plusieurs) valeur(s) qui sera(ont) utilisée(s) par input().

repeats permet de définir combien de test on va faire, ce n'est intéressant que si le générator contient de l'aléatoire.

Ici j'ai ajouté un taboo et je ne met aucun defaultcode, la boite sera donc vide.

[pyBox
slug='absolute'
title="repeats + generator (quand il y a des input)"
generator="print(_rint(-100, 100))"
repeats=3
solver='print(abs(int(input())))
'
taboo="abs"
] Votre code doit lire (avec input) un nombre entier et afficher la valeur absolue de ce nombre.


CONTRAINTE : Vous ne devez pas utiliser la fonction abs() de python. [/pyBox]
Exercice de code : repeats + generator (quand il y a des input)
Votre code doit lire (avec input) un nombre entier et afficher la valeur absolue de ce nombre.

CONTRAINTE : Vous ne devez pas utiliser la fonction abs() de python.

Inconvénient : on ne maitrise pas les tests. Dans l'exemple ci-dessus, il faudrait tester avec un négatif, un positif et avec 0, mais générator ne me permet pas de le faire....

parfois ça peut quand même servir, si on a pas de cas particulier à tester. exemple :

[pyBox
slug='plus_grand'
generator="print(_rint(-100, 100))
print(_rint(-100, 100))"
repeats=3
solver='print( max( int(input()),int(input()) ) )
'
taboo='max'
] Votre code doit lire (avec input) 2 nombres entiers et afficher la valeur du plus grand.


CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python. [/pyBox]
Exercice de code
Votre code doit lire (avec input) 2 nombres entiers et afficher la valeur du plus grand.

CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python.

mais même ici, on ne teste pas le cas ou a = b. Si l'élève écrit :

a = int(input())
b = int(input())
if a>b :
   print(a)
if b>a :
   print(b)
dans le cas a = b le code ne produira rien, mais ce cas n'est pas testé et le correcteur dira que c'est correct...

IV. input au lieu de generator+repeats : Tests choisis, pas d'aléatoire

C'est assez similaire mais ici on défini les tests. Inconvénient, je n'arrive pas à mettre un test aléatoire dans ce cas...

[pyBox
slug=′plus_grand_2′
input1="1\n2"
input2="2\n2"
input3="3\n2"
solver='print( max( int(input()),int(input()) ) )
'
taboo='max'
] Votre code doit lire (avec input) 2 nombres entier et afficher la valeur du plus grand.


CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python. [/pyBox]
Exercice de code
Votre code doit lire (avec input) 2 nombres entier et afficher la valeur du plus grand.

CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python.

pyScramble

[pyScramble 
slug="scramble"
solver="a=1\nb=a+1\nc=b+1"
] Arrangez les lignes dans le bon ordre, pour que le code s'exécute sans erreur.[/pyScramble]

Exercice mêlé
Arrangez les lignes dans le bon ordre, pour que le code s'exécute sans erreur.
  • a=1
  • c=b+1
  • b=a+1

V. Des codes utilisant random

Ces codes posent un problème : il faut initialiser le générateur aléatoire dans le solver et dans le code élève de la même façon.

Prenons cet exemple, qui ne fonctionne pas bien :

[pyBox
slug="plus_grand_3"
title="exemple qui ne fonctionne pas…"
generator='print(_rint(3,8))'
repeats=3
solver='a = int(input())
b = _rint(0,10)
print("le plus grand de ",a,"et",b,"est", max(a,b) )
'
taboo='max'
] Votre code doit lire (avec input) 1 nombres entier et afficher la valeur du plus grand entre ce nombre et un autre que vous générez aléatoirement entre 1 et 10.


CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python. [/pyBox]
Exercice de code : exemple qui ne fonctionne pas...
Votre code doit lire (avec input) 1 nombres entier et afficher la valeur du plus grand entre ce nombre et un autre que vous générez aléatoirement entre 1 et 10.

CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python.

le code élève correct :

import random
a=int(input())
b = random.randint(0,10)
if a>= b:
   print(a)
else :
   print(b)
Ce code devrait donner la même chose que le solver (même si, dans le solver, je m'autorise _rint() et max() parce que je suis feignant, le taboo c'est seulement pour les élèves...)

En fait il faut initialiser le générateur aléatoire. J'ai tenté ceci : l'initialiser à un nombre fixe dans un précode écrit ainsi :

precode = "import random as _rd
_rd.seed(5)
"
ce qui donne ce pyBox :

[pyBox
slug="plus_grand_4"
title="exemple qui ne fonctionne toujours pas…"
precode = "import random as _rd
_rd.seed(5)
"
generator='print(_rint(3,8))'
repeats=1
solver='a = int(input())
b = _rint(0,10)
print("le plus grand de ",a,"et",b,"est", max(a,b) )
'
taboo='max'
] Votre code doit lire (avec input) 1 nombres entier et afficher la valeur du plus grand entre ce nombre et un autre que vous générez alétoirement entre 1 et 10.


CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python. ][/pyBox]
Exercice de code : exemple qui ne fonctionne pas...
Votre code doit lire (avec input) 1 nombres entier et afficher la valeur du plus grand entre ce nombre et un autre que vous générez alétoirement entre 1 et 10.

CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python.

D'une part, ça ne génère pas vraiment des tests aléatoires, les nombre générés sont toujours les mêmes à chaque exécution. Mais pire, les deux codes (solver et élève) n'obtiennent pas la même chose (il semble donc que precode n'est exécuté qu'une seule fois...)

Il faut donc se résoudre à faire le random.seed dans le code (dans le solver et dans le code élève). Ca perturbe les élèves et on perd du temps.

Depuis peu j'ai choisit de créer dans le précode une fonction d'initalisation :

precode = "import random as _rd
def _initialisation_exercice():
   _rd.seed(_codeInitRandom)
_codeInitRandom = _rint(3,10)
"
je génère un nombre aléatoire caché _codeInitRandom qui sera bien le même dans les deux codes. j'appelle dans les deux code la fonction initialisation_exercice() que je met dans le defaultcode évidement...

exemple :

[pyBox
slug="plus_grand_5"
title="et finalement, je contourne le problème"
precode = "import random as _rd
def _initialisation_exercice():
    _rd.seed(_codeInitRandom)

_codeInitRandom = _rint(3,10)
"
generator='print(_rint(3,8))'
repeats=3
solver='_rd.seed(_codeInitRandom)
a = int(input())
b = _rint(0,10)
print("le plus grand de ",a,"et",b,"est", max(a,b) )
'
defaultcode='#La ligne ci-dessous est requise pour la validation automatique, laissez là mais ignorez la
_initialisation_exercice()
import random
'
taboo='max'
] Votre code doit lire (avec input) 1 nombres entier et afficher la valeur du plus grand entre ce nombre et un autre que vous générez alétoirement entre 1 et 10.


CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python. [/pyBox]
Exercice de code
Votre code doit lire (avec input) 1 nombres entier et afficher la valeur du plus grand entre ce nombre et un autre que vous générez alétoirement entre 1 et 10.

CONTRAINTE : Vous ne devez pas utiliser la fonction max() de python.

Notez bien que la fonction et le code d'initialisation sont cachés, cela évite des affichages inutiles lorsque l'élève exécute le code.

De même j'ai importé random as _rd. Le import random est donc indispable dans le code élève. (ici je l'ai mis dans le defaultcode mais je pourrais ne pas le mettre...)

SOS la boite ou même tout le collapsible ne s'affiche plus

La cause la plus fréquente est un problème de guillements.

Par exemple :

[pyBox
slug="bidon"
defaultcode="def ma_fct():
   """
   docstring
   """
   # faire afficher hello
"
solver="def ma_fct():
   """
   docstring
   """
   print('hello')
"]L'énoncé[/pyBox]
Exercice de code
L'enoncé

Dans ce cas vous pouvez avoir un message d'erreur, ou bien un affichage incomplet (dans l'exemple ci-dessus, le defaultcode ne s'affiche pas bien).

Mais testez. Remplacez le code par un code valide, par exemple mettez pass dans la fonction et exécutez.... vous obtenez une boite jaune avec ce message :

PyBox error: unknown option docstring
Il a voulu exécuter le solver, mais il ne l'a pas trouvé. Le default code c'est arrété aux " puis il a lu "" dont il ne fait rien, puis le mot docstring, qu'il ne comprend pas....

Pour éviter cela, il vaut mieux utiliser des ' plutot que " pour délimiter les codes, puis des " dans le code :

[pyBox
slug='bidon'
defaultcode = 'def ma_fct():
   """
   docstring
   """
   # faire afficher hello
'
solver = 'def ma_fct():
   """
   docstring
   """ 
   print("hello")
'
]L'enoncé[/pyBox]
Exercice de code
L'enoncé

Mais même ainsi il vous arrivera cela :

[pyBox
slug='bidon'
defaultcode = 'def ma_fct():
   """
   docstring
   """
   # faire afficher l'expression hello
'
solver = 'def ma_fct():
   """
   docstring
   """ 
   print("hello")
'
]L'enoncé[/pyBox]
je ne vous montre pas ce que ça donne car ça met un gros bordel.... Le [/pyBox] n'a pas été lu, et du coup votre boite pyBox reste ouverte jusqu'à ce qu'on rencontre un /pyBox.... qui se trouvera dans un autre exo et tout sera fusionné en une seule boite plus ou moins lisible (plutot moins que plus).

bref, vous n'y comprendrez rien, et c'est juste que vous avez oublié d'échapper l'apostrophe.

plus vicieux, l'oubli d'un <

[pyBox
slug="bidon2"
defaultcode="
"
solver="if 3 < 2:
   print(a)
"]
[/pyBox]
Exercice de code

la boite ne s'est purement et simplement pas affichée.... le comportement peut être variable mais il y aura forcément souci.

Rectifions :

[pyBox
slug="bidon2"
defaultcode="
"
solver="if 3 &lt; 2:
   print(a)
"]
[/pyBox]
Exercice de code

Les comportements peuvent varier suivant le contexte, l'oubli d'échappement d'une apostrophe peut impliquer la non lecture d'un [/collapsible] et du coup plus rien ne s'affiche, ou ne s'affiche pas dans le collapsible ou je ne sais quels effets les plus déroutants qui soient...

bref....

Quand ça ne marche pas regardez bien vos " et vos ', pensez aussi aux <, et sinon il reste la possibilité d'un code trop long, il y a une limite à chaque code et à la boite totale.

Deuxième partie : les pyHint pyWarn images latex etc...

pyHint

le pyHint peut figure dans le texte d'un exercice ou seul, dans une boite html personalisé comme un pyBox.

exemple si on met seul :

[pyHint hint="Aide"]le texte de l'aide [/pyHint]
Aide

et dans un pyBox :

[pyBox
slug='blabla'
solver='le code'
]L'enoncer de l'exercice.<br>
[pyHint hint="Aide"]le texte de l'aide [/pyHint]
[/pyBox]
Exercice de code
L'enoncer de l'exercice.
le texte de l'aide

pyWarn

[pyWarn]le texte du warning [/pyWarn]
le texte du warning

comme pyHint, pyWarn peut s'utiliser dans un pyBox.

images

Lorsque vous ajoutez un bloc image vous obtenez ceci :

vous pouvez televerser une image depuis votre ordi, elle sera visible et en même temps, ajoutée à la bibliothèque.

Vous pouvez aussi choisir une image de la bibliothèque, ou un lien vers une image.

Pour insérer une image dans un pyBox :

commencez par ajouter un bloc image, et mettez votre image. Puis convertissez ce bloc en html et copiez le code html, qui doit ressembler à ça :

<figure class="wp-block-image size-large">
<img src="https://cscircles.cemc.uwaterloo.ca/wp-content/uploads/img-CI.jpg" alt="" class="wp-image-15151"/>
</figure>
que vous collez dans l'énoncé de votre exercice. Vous supprimerez ensuite le bloc image.

latex

comme les pyWarn et pyHint le code latex peut être inséré dans l'énoncé d'un pyBox ou pyExample, ou dans un paragraphe.

[latex size=2]\sum\limits_{j=1}^k A_{\alpha_j}[/latex]
\sum\limits_{j=1}^k A_{\alpha_j}

T 3.4 Parcours récursifs d'itérables

Le Triptique CAC

Dans tous les algorithmes que vous avez rencontrés, certaines techniques reviennent souvent. Notamment l'utilisation de :

  • Ccompteur : exemple : compter les valeurs paires dans une liste
  • Aaccumulateur : exemple : faire la somme des éléments d'une liste
  • Ccurseur : exemple : rechercher le max des valeurs d'une liste ou rechercher l'indice du max (ce n'est pas tout à fait la même chose)
Vous avez appris à manier ces outils dans des contextes variés. Parfois il faut utiliser deux de ces techniques en même temps.
Par exemple, calculer la moyenne des valeurs paires d'une liste demande un compteur (pour compter les valeurs paires) et un accumulateur (pour additionner les valeurs paires), et on renvoie le rapport somme des valeurs / nombre de valeurs

Dans les cours précédents vous avez appris à utiliser la récursion. Ici nous allons l'appliquer à des itérables (listes, chaîne de caractères etc...)

Transposons ces notions en récursif (pour des parcours de listes)


compteur récursif
Reprenons un exemple de Compteur en impératif: compter le nombre de valeurs paires d'une liste.
Exemple : Un exemple d'utilisation d'un Compteur. nbMult2 est le compteur.


Comment faire la même chose en mode récursif


Notre compteur nbMult2 dans la fonction nbrePairs(lst) peut se concevoir de façon récursive comme :
nbMult2 = (1 si l[0] est pair, 0 sinon) + nbrePairs du reste de la liste
Si le 1er nombre est pair on renvoie 1 + nombre pair du reste
Si le 1er nombre est impair on renvoie 0 + nombre pair du reste

Par exemple : nb=nbPairs([1, 2, 3, 4, 6]) :


renvoyer 0 + nbPairs([2, 3, 4, 6])................................. # 0 car 1 est impair
renvoyer 0 + (1 + nbPairs(3, 4, 6]) )...............................# 1 car 2 est pair
renvoyer 0 + (1+ ( 0 + nbPairs([4, 6]) )........................# 0 car 3 est impair
renvoyer 0 + (1+ ( 0 + 1 nbPairs([6]) ) ) ) ................. # 1 car 4 est pair
renvoyer 0 + (1+ ( 0 + ( 1 + ( 1 + ( nbPairs([]) ) ) ) ).. # 1 car 6 est pair
renvoyer 0 + (1+ ( 0 + ( 1 + ( 1 + ( 0 ) ) ) ).. # fin, on appelle plus la fonction !

Et quand il n'y a aucun élément (liste vide) : nbPairs([]) = 0

  • La longueur de la liste décroit, la liste finira par être vide
  • le nombre d'élément pairs es bien égal à ce qu'on renvoie
Exemple : Un exemple de transposition du compteur en mode récursif

La condition d'arrêt : si lst est vide, nb=0, s'écrit :

if len(lst) == 0:
    return 0

Exercices avec un compteur

Exercice de code : combien de fois ?
Ecrire une fonction récursive qui compte le nombre d'occurrence d'une lettre dans un texte.
Exercice de code : Longueur
compter le nombre d'éléments dans un iterable mutable (liste ou chaine).

Dans cette version utilisant le slicing, on envisage seulement les cas d'itérable str ou list


Accumulateur récursif

Les accumulateurs et la récursion


Reprenons un exemple d'accumulateur en impératif : calculer la somme des éléments d'une liste
Exemple : Un exemple d'utilisation d'un Accumulateur : somme est l'accumulateur.

Notre fonction somme(lst) ci-dessus se comprend de façon récursive comme :

somme = lst[0] + somme du reste de la liste = lst[0] + ( lst[1] + somme du reste ) = etc...

jusqu'à ce que le reste ne contienne aucun élément (liste vide) et la somme sera alors 0.

Exemple :

 somme = somme([2, 4, 1, 5]) 
       = 2 + somme([4, 1, 5])
       = 2 + (4 + somme([1, 5]) ) 
       = 2 + (4 + (1 + somme([5]) ) )
       = 2 + (4 + (1 + (5 + somme([]) ) ) )
       = 2 + (4 + (1 + (5 + 0) ) ) ) = 10

le cas de base sera : si la liste est vide, renvoyer 0

Assurément :

  • La liste perd un élément à chaque appel, elle finira par être vide
  • somme(tous les éléments) est bien égal à lst[0] + sommes des autres éléments

Exercice

Codez la fonction somme en récursif

Exercice de code : Somme des éléments d'une liste (récursivement)

Regardez bien ce que nous avons écrit :
somme = lst[0] + somme du reste devient, dans python :

return lst[0] + somme(lst[1:])
Et pour la condition d'arrêt :
jusqu'à ce que le reste ne contienne aucun élément s'écrit :

if len(lst) == 0 :
    return 0

Des coûts cachés...

Dans les exemples que nous avons traité, nous avons utilisé le slicing avec des instructions comme :

somme(lst[1:])
Pour exécuter une telle instruction, l'interpréteur python va dupliquer la liste (sauf le premier élément). La complexité de cette opération est O(n). Si cette opération doit être réalisé à chaque appel et qu'on fait N appels, on se retrouve avec une complexité en O(n²) alors qu'on a un algorithme en O(n). C'est donc bien commode mais plutôt désastreux.

Nous allons voir comment éviter ces copies de lites, donc coder sans slicing.

Commençons par un exemple.

On veux écrire une fonction estTriee(lst) qui renvoie True si la liste est triée (croissante) et False sinon.

Une version impérative pourrait être :

Exemple
Détermine (en impératif) si une liste est triée ou non

Ce problème est clairement récursif. On compare 2 éléments (on commence par les 2 permiers) et on vérifie l'ordre. Si l'ordre est mauvais on renvoie False, sinon au continue sur le reste de la liste.

Il n'y a pas à proprement parler de curseur dans cette fonction, mais la technique reste quand même assez similaire. Une variante serait de renvoyer la position du premier élément non ordonné, et on aurait vraiment un curseur. Mais nous allons rester sur la version plus simple donnée ci-dessus..

1ere version : en utilisant des slices, pour découper la partie de liste restant à traiter.

Exemple
Détermine (en récursif) si une liste est triée ou non

Ce code fonctionne et il est assez similaire à la version non récursive.

L'algorithme est clairement de complexité linéraire (n-1 comparaison)

Mais notre code n'est pas de complexité linéaire ! En effet, à chaque exécution de estTriee, on effectue une copie de lst.

Pour une longueur N, je dois rappeler estTriee avec une longueur n-1, et je dois copier n-1 élément dans une nouvelle liste. Le temps d'éxécution peut s'ecrire :

T(n) = T-1) + T(n-1) + n

Pour comprendre cette formule, prenons une analogie :

Je dois éplucher n pommes de terre. Le temps que je vais mettre est en principe égal au temps d'éplucher une pomme de terre + le temps d'éplucher les n-1 restantes.

T(n) = T(1) + T(n-1) nous donne une complexité linéaire

Mais imaginons que après chaque pomme de terre épluchée, je doive déplacer une à une toutes les pommes de terre restantes dans une autre pièce avant de poursuivre l'épluchage...

Le temps total sera alors :

T(n) = T(1) + T(déplacer une a une) + T(n-1)

Et comme je dois toutes les déplacer, le temps de déplacement sera proportionnel à n -1. Notons T' le temps pour déplacer une pomme de terre :

T(n) = T(1) + (n - 1) T' + T(n - 1)

Et donc

T(n) = T(1) + (n-1) T' + [  T(1) + (n-2) T' + T(n-2) ]
     = 2 . T(1) + [(n-1) + (n-2)] T' + T(n-2)
     = 2 . T(1) + [(n-1) + (n-2)] T' + [  T(1) + (n-3) T' + T(n-3) ]                      
     = 3 . T(1) + [(n-1) + (n-2) + (n-3)] T' + T(n-3)

Etc.... on arrivera à :

T(N) = N . T(1) + (1 + 2 + ... + n-1) T'

et on reconnait la somme \sum\limits_{n = 1}^{N-1} n = \frac{N(N-1)}{2} = 0(N^2)

Cette formule de récurrence mène donc à une complexité en O(n²).

Retenir :

Si le cas général est en temps constant : T(N) = O(1) + T(N-1) -> complexité linéaire O(N)

Si le cas général est en temps proportionel à N: T(N) = O(N) + T(N-1) -> complexité quadratique O(N²)


Comment éviter le slicing ?

Pour éviter le slicing, il va falloir utiliser les indices. En impératif, nous disposons de l'itérateur qui parcours aisément la liste. En récursif c'est plus délicat, et pour y parvenir nous allons devoir ajouter un attribut à notre fonction.

Au départ il vaudra 0, et nous allons lui attribuer cette valeur par défaut.

A chaque appel de estTriee( lst, n )

  • on compare lst[n] à lst[n+1]
    • Si les deux valeur sont dans l'ordre on reprend en incrémentant n
    • sinon on renvoie False :

On s'arrêtera au dernier, qu'on aura pas besoin de comparer au suivant puisqu'il n'y a plus de suivant.

Le cas de base est donc : si n = len(lst) - 1 renvoyer True

Exemple
Détermine (en récursif et sans slice) si une liste est triée ou non

Ici le cas général et constitué d'un simple test de comparaison, une affectation, et un appel, c'est bien en temps constant : T(N) = T(1) + T(N-1)

La complexité du code est donc linéaire O(N).

Retenir :

Pour connaitre l'indice de l'élément en cours de traitement :

° Définir un paramètre avec valeur par défaut égale à 0

° A chaque appel, incrémenter ce paramètre

Exercices

Reprendre les 2 codes des accumulateurs et les réécrire en n'utilisant pas de slice.

Somme des éléments d'une liste

Exercice de code : Somme des éléments d'une liste (récursivement sans slice)
Le code fourni utilise des slice. Vous devez le modifier pour parcourir la liste sans utiliser de slicing.

Nombre d'élément pairs dans une liste

Exercice de code : Compter le nombre d'éléments pairs en récursif et sans slice
Le code fourni utilise des slices. Vous devez le modifier pour parcourir la liste sans utiliser de slicing.

Si vous n'aimez pas les paramètres par défaut....

Il existe une autre façon de procéder. L'idée est la même : ajouter un paramètre. Mais au lieu d'en ajouter un avec une valeur par défaut, on crée purement et simplement une autre fonction :

Exemple
Détermine (en récursif et sans slice) si une liste est triée ou non

RETENIR

Le problème des traitements récursifs d'itérables est un peu différent, on ne dispose pas d'un itérateur comme dans la boucle for, et pourtant on itère...

1er solution : on fait du slicing
exemple :

def somme_lst(lst) :   
     if len(lst) == 0 : 
         return 0    
     return lst[0]  + somme_lst(lst[1:])

C'est plutot simple, et élégant, mais cela à un coût ( en 0(n) ) et c'est donc peu recommandé d'autant plus si on prend aussi en compte la complexité en espace.

2eme solution : un paramètre par défaut (ou plusieurs)

exemple :

def somme_lst(lst, n = 0) :
    if n == len(lst) : 
        return 0
    return lst[n]  + somme_lst(lst, n+1)

3eme solution : une fonction intermédiaire ou une fonction locale

exemple 

def somme_lst(lst ) :
    return somme_lst_rec(lst, 0)

def somme_lst_rec(lst, n) :
    if n == len(lst) : 
        return 0
    return lst[n]  + somme_lst_rec(lst, n+1)

variante avec fonction locale :
def somme_lst(lst) :
    def somme_lst_rec(lst, n):
        if n == len(lst): 
            return 0 
        return lst[n]  + somme_lst_rec(lst, n+1)
    return somme_lst_rec(lst, 0)

Curseur récursif 1 : la fonction getMax

Les curseurs sont utilisés lorsqu'on doit scanner un itérables pour repérer un éléments selon un critère. Par exemple le plus grand, ou la dernière (ou première) occurrence d'une valeur, ou le premier (ou dernier) multiple d'un nombre, ou une clef d'un dictionnaire ayant une valeur donnée etc...

Les codes sont présentés pour une recherche du max mais peuvent aisément être adaptés pour la recherche du min.

Recherche du max : on déplace le curseur en notant la valeur la plus grande

Avant de débuter notons que rechercher le max dans une liste vide n'a pas de sens. Nous ne considérerons que des listes non vides

La version itérative :

  • on initialise vmax à lst[0]
  • Du 1er au dernier élément :
    • si l'élément est plus grand on actualise vmax
Exemple : Un exemple d'utilisation d'un Curseur. vmax est le curseur

Les curseurs et la récursion


Envisageons un exemple : la recherche de la plus grande valeur dans une liste de nombres : lst = [1, 3, 7, 2, 11, 4] le max est 11.

Si on pense en récursif ici, cela donne :

Exemple
Dans ce code, nous avons écrit :
       vmaxReste  = getMax(lst[1:])
if lst[0] >vmaxReste:
vmax = lst[0]
else :
vmax = vmaxReste
return vmax

Nous avons donc d'abord appelé getMax avant de renvoyer la bonne valeur. Pourquoi ?
On aurait put écrire : :
if lst[0] > getMax(lst[1:])
return lst[0]
else :
return getMax(lst[1:])

Mais quel problème cela pose-t-il ?
Pour vous aider, visualiser le code qui a été recopié ci-dessous, puis comparer en visualisant également le code précédant.
N'oubliez pas de choisir la langue anglaise.
Exemple

Et pour le faire sans slice ?

On introduit un second paramètre, dont la valeur par défaut est 0, qui est l'indice de l'élément en cours de traitement.

Par exemple, si n = 1 :

Et le cas de base sera n = len(lst) - 1 : un seul élément donc c'est lui le max, on renvoie lst[n]

Exercice de code

Curseur récursif 2 : la fonction idxMax

Cas de la recherche de l'indice du max : on déplace le curseur en notant l'indice

Dans le cas ou l'on recherche l'indice du max de façon récursive, nous allons devoir bien comprendre un point plus délicat : l'indice d'une valeur dans lst[1:] n'est pas le même que l'indice de la même valeur dans lst.

Ce qu'il faut bien comprend c'est le 1 + indice du max du reste.


La fonction s'écrira donc :

Exemple : Un exemple d'utilisation d'un Curseur en récursif

la ligne clé est :

        idxMaxReste = 1 + idxMax(l[1:])
L'utilisation du curseur est donc un peu plus compliquée à bien comprendre. En fait, idx est l'indice du max dans la liste, mais dans la fonction appelante, qui contient un élément de plus en tête, l'indice est idx + 1. Une fois bien compris ceci, l'utilisation de curseur ne devrait plus vous poser de difficulté.
La condition d'arrêt si len(l) == 1 : return 0 est intuitive

Une autre approche : un argument supplémentaire par défaut

Dans ces situations, comme pour le cas de la fonction estTriee, une autre approche peut se révéler plus intuitive, mais elle nécessite l'utilisation d'un paramètre supplémentaire qui doit avoir une valeur par défaut.

Rappelons le principe d'un paramètre avec valeur par défaut :

def f(x, n = 0):
    pass
# appel sans le second paramètre :
f(2) # x vaudra 2 et n vaudra 0
f(2) est identique à f(2,0) ou f(2, n=0 )

# appel avec 2 paramètres :
f(2, 3) ou f(2, n=3) # x vaudra 2 et n vaudra 3
La fonction sera définie ainsi :

def idxMax(lst: list, idx = 0)
Exemple : chercher l'indice du max dans [ 1 , 3 , 4 , 2 ]

1er appel : getIdxMax( [1 , 3 , 4 , 2 ] )

idx vaut 0 : on cherche dans toute la liste

On renvoie le plus grand entre lst[0] et getIdxMax(lst, 1)

2ème appel idx vaut 1, On renvoie l'indice associé à la plusgrande valeur (on compare lst[1] et lst[ getIdxMax(lst, 2) ]

Voir ci-dessous, par exemple un appel avec idx = 2 :

etc... et on arrête quand idx et l'indice du dernier élément, c'est-à-dire len(lst) - 1. Dans ce cas l'indice du max est idx puisqu'on ne cherche que parmi le dernier élément.

L'algorithme peut être décrit ainsi :

cas général :
idxMaxReste = indice_du_max(lst, idx + 1) (indice du plus grand dans le reste de la liste)
on renvoie idx si lst[idx] > lst[idxMaxReste] sinon on renvoie idxMaxReste
cas de base :
si idx est l'indice du dernier, il n'y a pas de reste de la liste. On renvoie idx

On se rend compte que les curseur récursifs sans slice sont bien plus simple qu'avec slice, et même plus naturel que la version itérative.

A vous :

Exemple : Un exemple d'utilisation d'un Curseur sans slice.

Les deux versions de ce code ne sont pas du tout équivalentes. La première utilise des slices lors de l'appel avec lst[1:]. Cela induit des coûts importants de temps de calculs et de coût en mémoire, car python va dupliquer la liste.

La seconde version utilise l'indice et ne requiert aucune copie de liste. Elle sera bien plus efficace en temps et en espace.

Exercice

On vous demande de coder une version récursive de la fonction appartient donnée ci-dessous :

Exemple : Recherche de l'appartenance

1ère version : avec slicing:

Exercice de code : Appartenance d'un élément à une liste (récursivement)

2ème version : Sans slicing (paramètre par défaut ou fonction intermédiaire) :

Exercice de code : Appartenance d'un élément à une liste (récursivement)

P5.1b premiers algorithmes exercices

sommes et moyenne des valeurs paires

Ecrire l'algorithme d'une fonction sommePaires(lst) qui renvoie la somme des valeurs paires d'une liste.

Exercice à choix multiple
Dans sommesPaires vous aurez besoin d'un compteur ?
Correct !

Exercice à choix multiple
Dans sommesPaires vous aurez besoin d'un curseur?
Correct !
Exercice à choix multiple
Dans sommesPaires vous aurez besoin d'un accumulateur ?
Correct !

Ecrire un second algorithme pour moyPaires qui renvoie la moyenne des valeurs paires d'une liste.

Exercice à choix multiple
Dans moyPaires vous aurez besoin d'un compteur ?
Correct !
Exercice à choix multiple
Dans moyPaires vous aurez besoin d'un curseur?
Correct !
Exercice à choix multiple
Dans moyPaires vous aurez besoin d'un accumulateur ?
Correct !
moyenne pondérée
N'oubliez pas que vous pouvez visualiser l'exécution de votre code pour vous aider à le mettre au point.
Exercice de code : moyenne coefficientée
Ecrire une fonction moyPondee(notes , coefs) qui renvoie la moyenne coefficientée.

Exercice à réponse courte
Combien y'a-t-il d'opération élémentaires avant la boucle ?
Correct !
Exercice à réponse courte
Combien y'a-t-il d'opération élémentaires après la boucle (seulement dans la fonction) ?
Correct !
Exercice à réponse courte
Combien y'a-t-il d'opération élémentaires en tout (en fonction du nombre N de notes) ?
Correct !
Exercice à réponse courte
La complexité est elle linéaire ?
Correct !
un curseur délicat

Nous avons déjà traité la question de la recherche d'un caractère dans un texte. Nous allons ici traiter un problème assez similaire mais un peu plus délicat : chercher une chaine dans une autre. Pour plus de clarté, nous appellerons mot la chaine recherchée, et texte la chaine dans laquelle on effectue la recherche.

Commencez par regarder la vidéo ci-dessous pour comprendre le problème.

Ecrivez le pseudo code sur votre feuille et faites le valider :
Exercice de code : reverse avec pop

MODELE

pyexample : insérer code court

Exemple
Texte explicatif

Test avec les sorties consoles :

Exercice de code
ATTENTION
créer une fonction qui affiche un nombre n et appelez cette fonction pour n=3 AIDE1

avec un precode et repeats

Exercice de code
Avant d'exécuter votre code, le correcteur définir une variable a
créer une fonction qui affiche un nombre n et appelez cette fonction pour afficher la valeur de a AIDE1

avec autotest : on teste le résultat sur la valeur d'une variable

Exercice de code
Dans cet exercice le correcteur va vérifier la valeur de la variable a Les sorties consoles sont quand même vérifiées

avec autotest : on teste ce que la fonction renvoie

Exercice de code
Dans cet exercice le correcteur va vérifier ce que fct renvoie Les sorties consoles sont quand même vérifiées

avec autotest : on teste ce que la fonction renvoie

on peut mettre plusieurs appels dans autotests

on peut appeler avec des variables définies dans precode ou des tests choisis

Exercice de code
Dans cet exercice le correcteur va vérifier ce que fct renvoie Les sorties consoles sont quand même vérifiées

Exemple d'utilisation de taboo

Exercice de code
Dans cet exercice le correcteur va vérifier ce que fct renvoie Les sorties consoles sont quand même vérifiées

WARNING: this problem needs a permanent slug to save user data
Exercice à choix multiple
la question
Correct !

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

Exercice de code : 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.

Exercice de code : 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

Exercice de code : 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()

Exercice de code : 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

Exercice de code : 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

Exercice de code : 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

Exercice de code : 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 ?

Exercice de code : 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.

Exercice de code : 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

Exercice de code : 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

Exercice de code : 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
      
Exercice de code : 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 //
Exercice de code : 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

S-RS Modéliser les réseaux sociaux

Nous allons reprendre l'exemple d'un petit réseau social vu en classe :

Alban, Béatrice, Charles, Déborah, Éric, Fatima, Gérald, Hélène sont inscrits sur Facebook.

  • Alban est ami avec Béatrice, Déborah, Éric et Fatima.
  • Béatrice est amie avec Alban, Charles, Déborah, Éric et Gérald.
  • Charles est ami avec Béatrice, Déborah et Hélène.
  • Déborah est amie avec Charles, Béatrice, Alban et Gérald.
  • Éric est ami avec Béatrice et Alban
  • Fatima, avec Alban, Gérald et Hélène.
  • Gérald est ami avec Béatrice, Fatima et Hélène
  • Hélène est amie avec Fatima, Gérald et Charles.

Pour modéliser cette situation nous pouvons utiliser une matrice, c'est à dire un tableau à deux dimension. En python on dira une liste de listes, c'est à dire une liste dont les éléments sont des listes. Par exemple, la liste des amis de Alban s'écrira : [0,1,0,1,1,1,0] car ses relation sont :

Alban : 0 Béatrice : 1 Charles : 0 Déborah 1 Eric : 1 Fatima :1 Gérald : 0 Hélène : 0

De même les amis de Béatrice s'écriront : [1,0,1,1,1,0,1,0] et ainsi de suite pour les autres.

Le graphe sera donc :

Exercice de code

Cette représentation n'est pas idéale, nous verrons plus tard dans l'année un autre type de donnée en python qui permet de conserver le nom du nœud associé à sa liste, pour le moment nous nous en tiendrons à l'utilisation de listes de listes.

Nous pouvons néanmoins, sans aller plus loin à ce stade, utiliser la matrice ci-dessus en ajoutant les noms des nœuds, dans un tuple (nom,listeAmi) :

Exercice de code
Publié dans Non classé

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

Exercice à réponse courte
"Le code Hexadécimal 52 correspond à quel caractère ?"
Correct !
Exercice à réponse courte
"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 :

Exemple

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 :

Exemple

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

Exercice

Exercice à réponse courte
"Quel est le code hexa correspondant au caractère 'b' ?"
Correct !
Exercice à réponse courte
"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.

Exercice à réponse courte
"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)

Exercice de code
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) :

Exemple

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

Exemple

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 :

Exemple

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

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

Exemple : 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.

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

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

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

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

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

Exemple : 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.

Exercice de code : 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...

Exercice de code : 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.
Exercice de code : 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 :

Exemple : Ajouter en fin de liste

exemple 2 :

Exemple : Initialiser une liste avec append

exemple 3 :

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

Exemple : 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.

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

Exemple : 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)

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

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

Exemple : convertir une chaine en liste

Convertir une liste en chaine, avec join :

Exemple : 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()