25 - Exercices sur les tableaux
Cette activité est composée de plusieurs exercices qui visent à exploiter et réviser les notions vues jusqu'à présent.
Attention : on rappelle que les tableaux qui nous utilisons dans Python sont en réalité dont le type est list.
Cette activité vous permettra de maitriser les tableaux avec assez de recul pour aborder le projet Tkinter, où vous aurez à réaliser un petit jeu graphique.
Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...
Evaluation ✎ : rien, tous les exercices sont corrigés. Par contre, il y a le DS qui va bien derrière :o)
1 - Lecture d'une structure avec index
Commençons par revoir comment parvenir à lire les éléments d'une structure de données indexable.
Rappel : accès à un élément avec [numéro]
Sur une structure de donnée linéaire et ordonnée (string, tableau, p-uplet), on peut accéder à un élément particulier en utilisant le nom de la variabe suivi de crochet contenant l'indice ou le numéro de l'élément voulu.
Si la variable se nomme toto, on notera toto[4] pour obtenir l'élément d'indice ou numéro 4.
Trois remarques :
- Le premier élément porte le numéro d'indice 0 !
- Si une structure possède 20 éléments les indice disponibles vont de 0 à 19
- Pour trouver le nombre d'éléments de toto, il suffit d'utiliser len(toto).
01° Créer la fonction element qui doit renvoyer l'élément d'indice i du paramètre t recu.
En lisant la documentation, on voit qu'il ne sert à rien de tester la valeur d'indice : on considère que l'utilisateur fournit une valeur valide puisque c'est noté dans la documentation. S'il ne le fait pas, ce n'est pas votre problème.
1
2
3
4
5
6
7
8
9 | |
Exemple de fonctionnement :
>>> element('bonjour', 1)
'o'
>>> element(['a', 'b', 'c'], 2)
'c'
...CORRECTION...
1
2
3
4
5
6
7
8
9def element(t, i):
"""Renvoie l'élément stocké au bon indice dans la structure
:: param t(str|list|tuple) :: une structure indexable
:: param i(int) :: un indice VALIDE
:: return (dépend des éléments) :: l'élément voulu
"""
return t[i]
02° On vous demande de fournir une fonction différente : cette fois, la précondition sur le paramètre i est simplement qu'il soit un entier.
Rien ne peut garantir que l'indice reçu soit valide. Avec une instruction conditionnelle , il faudra vérifier que l'indice soit bien compris entre 0 et la valeur maximale disponible. Pour cela, il faut connaître le nombre d'éléments dans la structure recue.
1
2
3
4
5
6
7
8
9 | |
Exemple de fonctionnement :
>>> element('bonjour', 1)
'o'
>>> element(['a', 'b', 'c'], 4)
Un indice invalide ne provoquera pas d'erreur, juste une non-réponse.
...CORRECTION...
1
2
3
4
5
6
7
8
9def element(t, i):
"""Renvoie l'élément stocké au bon indice dans la structure
:: param t(str|list|tuple) :: une structure indexable
:: param i(int) :: un indice VALIDE
:: return (dépend des éléments) :: l'élément voulu
"""
if i >=0 and i < len(t):
return t[i]
03° Répondre au QCM après avoir analysé la fonction afficher qui doit afficher les caractères un par un :
1
2
3 | |
Il faut remplacer ? par :
- element
- i[toto]
- toto[i]
- toto[index]
...CORRECTION...
Réponse C : nom de la variable + crochet contenant le numéro de la case voulue.
04° On vous présente une Prédicat valider qui doit renvoyer True uniquement si le string reçu via le paramètre mot est bien constitué uniquement des lettres autorisées et du tiret.
La version proposée utilise une boucle FOR associée à l'interruption via return : on rappelle qu'on sort de la fonction (et donc de la boucle) dès qu'on rencontre un return.
1
2
3
4
5
6 | |
Trois questions
- Dans la mesure où on voit qu'on utilise for i in range (len(mot)), la variable de boucle i va-t-elle contenir 0-1-2... ou directement les caractères un par un ?
- Que voudrait dire if mot[i] in acceptables en français ? (remarquez bien qu'il n'y a pas le mot-clé not ici)
- Que veut donc dire if not mot[i] in acceptables en français ?
...CORRECTION...
- Nous avons un for "numérique" à cause du range (len(mot). La variable de boucle va donc contenir 0-1-2-3...
- Si le caractère mot[i] se trouve dans la chaine de caractères nommée acceptable.
- L'inverse du cas précédent. Si le caractère mot[i] ne se trouve pas dans la chaine de caractères nommée acceptable.
Lecture de tous les élements d'une structure indexable
Pour lire une par une les cases d'un tableau, d'un string ou d'un tuple, on dispose de 3 manières de faire :
- Avec un while et en incrémentant un indice partant de 0 jusqu'à la valeur finale disponible. Il faut faire attention à bien permettre de rentrer dans la boucle et à penser à faire varier le compteur.
- Avec une boucle FOR "numérique" qui utilise un indice : for i in range(len(a)) avec un accès au contenu avec a[i]
- Avec une boucle FOR "nominative" qui utilise juste le nom du tableau : for case in a avec un accès au contenu avec case
05° En vous basant sur la fonction version "for numérique" (redonnée ci-dessous), fournir la version utilisant un "for nominatif" où derrière le mot-clé in on ne trouve que le nom de la variable contenant le string.
1
2
3
4
5
6 | |
...CORRECTION...
1
2
3
4
5
6 | |
2 - Transformation string en tableau
Nous avons une fonction permettant de tester si un string ne contient bien que des caractères autorisés. Or, le string est immuable.
Nous aimerions faire la même chose mais avec un tableau où chaque case correspond à une lettre de notre mot.
Cela nous permettra de créer un jeu du pendu.
Exemple
- 'bonjour' est le mot inconnu à trouver (stocké en mémoire)
- '*******' est l'affichage initial à l'écran
- On teste la lettre 'o'
- '*o**o**' sera le nouvel affichage à réaliser
Principe
- on vous donne un mot inconnu dont vous ne connaissez que la longueur via le nombre d'étoiles affichées
- vous pouvez demander si une lettre est présente
- si c'est le cas, on remplace les étoiles concernées par la bonne lettre,
- sinon, on commence à dessiner le pendu...
Chaque tâche basique sera encapsulée dans une fonction et nous allons clairement séparer les fonctions d'interface et les fonctions de gestion de données.
Dans cette activité, nous ne traiterons que de la gestion des données. Les fonctions d'interface, c'est l'activité suivante.
Nous avons vu que modifier un string n'est pas possible car le string-python est une structure de donnée non mutable ou immuable.
Nous allons donc tricher : nous allons utiliser la fonction native list pour obtenir un tableau contenant les lettres du mot qu'on cherche à identifier.
>>> list('bonjour')
['b', 'o', 'n', 'j', 'o', 'u', 'r']
L'intérêt ? Ce tableau est muable ou mutable en Python.
06° Ne supprimer pas votre fonction verifier précédente. Coder la fonction transformer qui transforme le string mot valide reçu en tableau de caractères.
1
2
3
4
5
6
7
8
9
10
11
12 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12 | |
3 - Création par compréhension
Maintenant nous savons comment gérer facilement le mot à trouver en utilisant un tableau nommé par exemple vrai_mot plutôt que le string validé en mémoire :
vrai_mot = transformer(mot)
Il est temps de générer le premier affichage composé d'étoiles à afficher au joueur : nous allons devoir générer un tableau ayant le même nombre de cases que vrai_mot mais composé uniquement d'étoiles.
Exemple :
['b', 'o', 'n', 'j', 'o', 'u', 'r']
['*', '*', '*', '*', '*', '*', '*']
Rappel : Déclaration de tableau par compréhension à partir d'un tableau initial
La déclaration d'un tableau par compréhension est celle qui consiste à formuler le contenu du tableau directement dans les crochets à l'aide d'une boucle for.
nouveau = [None for element in base]
>>> base = [1, 2, 5]
>>> nouveau = [None for valeur in base]
>>> nouveau
[None, None, None]
En réalité, on peut faire mieux que mettre None dans chaque case : on peut indiquer le calcul à faire directement !
Si on veut un tableau contenant exactement le double du tableau précédent, on peut faire ceci :
nouveau = [element * 2 for element in base]
>>> base = [1, 2, 5]
>>> nouveau = [valeur*2 for valeur in base]
>>> nouveau
[2, 4, 10]
C'est beaucoup plus simple à écrire qu'avec un for. En réalité, l'interpréteur Python réalise en arrière plan la boucle for.
07° Créer la fonction dissimuler qui renvoie un tableau ayant la même taille que le tableau fourni en paramètre mais dont tous les éléments sont des étoiles "*".
On vous impose de créer le tableau renvoyé avec une déclaration par compréhension à partir du tableau reponse placé dans le paramètre.
1
2
3 | |
Pour varier les choses : voici un exemple d'utilisation hors documentation :
>>> vrai_mot = transformer('bonjour')
>>> vrai_mot
['b', 'o', 'n', 'j', 'o', 'u', 'r']
>>> dissimuler(vrai_mot)
['*', '*', '*', '*', '*', '*', '*']
>>> mot = dissimuler(vrai_mot)
>>> mot
['*', '*', '*', '*', '*', '*', '*']
...CORRECTION...
1
2
3 | |
Nous n'allons pas vraiment l'utiliser ici, mais on peut aussi créer un tableau par compréhension à partir d'un simple range.
Rappel : Déclaration de tableau par compréhension avec un range
On peut également créer des tableaux contenant un nombre précis d'élements de façon assez facile : il suffit d'utliser range.
Exemple 1
>>> tableau = [0 for x in range(10)]
>>> tableau
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Cela veut dire qu'on place 0 dans une case pour chaque des valeurs x (qui valent 0 puis 1 puis 2 ... jusqu'à 9)
Nous avons maintenant un tableau mot ne contenant que des étoiles et un tableau vrai_mot contenant les lettres du vrai mot qu'il faut trouver.
explication en images
Imaginons la situation suivante : on nous avons déjà trouvé la la présence de la lettre 'j' et on teste maintenant 'o' dans le mot :
Comme on le voit, on crée une copie de mot et on modifie éventuellement le contenu attribué à un incide si, pour le même indice, vrai_mot contient la bonne lettre.
Voyons comment faire comprendre cela à un système informatique...
Nous utiliserons ici une fonction renvoyer_nouvelle_version(mot, vrai_mot, caractere) lorsqu'on propose de tester un nouveau caractere :
explication en langage naturel ou presque
- on crée une copie de mot.
- pour chaque indice i de vrai_mot,
- si vrai_mot[i] contient caractere
- on affecte caractere à copie[i]
- sinon
- on ne fait rien, on ne modifie pas copie[i]
- On revient la copie
explication en version plus codifiée
copie ← une copie de mot
POUR chaque indice i possible de vrai_mot
SI vrai_mot[i] est identique à caractere
copie[i] ← caractere
Fin du Si
Fin du Pour
Renvoyer copie
08° Créer la fonction renvoyer_nouvelle_version qui attend un paramètre mot contenant le mot trouvé pour l'instant, un paramètre vrai_mot contenant le mot à trouver au final et un paramètre caractere contenant le caractère à tester.
Voici le prototype suivi d'un exemple d'utilisation :
1 | |
>>> vrai_mot = transformer('bonjour')
>>> mot = dissimuler(vrai_mot)
>>> renvoyer_nouvelle_version(mot, vrai_mot, 'o')
['*', 'o', '*', '*', 'o', '*', '*']
Voici le code qu'il faudra compléter ou modifier. Il s'agit bien entendu de ne modifier que le code de la fonction renvoyer_nouvelle_version de façon à modifier le contenu du tableau local copie.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | |
Il faut donc lire le vrai mot case par case en connaissant son numéro d'indice (attention donc au choix du type de boucle for !).
...Quelques indications...
Il faudra utiliser utiliser une boucle du type for indice in range (len(tableau)) et réaliser une instruction conditionnelle pour chaque case lue.
On rappelle qu'on lit le contenu d'une case d'un tableau avec tableau[numero de la case]
Le tout est de ne pas s'embrouiller entre copie et vrai_mot.
...CORRECTION...
1
2
3
4
5
6
7 | |
On renvoie donc bien un tableau contenant une nouvelle version des lettres trouvées.
Pour l'instant, on ne peut pas savoir si l'utilisateur a bien repondu ou si la lettre demandée n'existe pas dans le mot. N'oublions pas qu'une fonction ne peut renvoyer qu'UNE réponse.
Nous pourrions renvoyer un tuple (tableau, booléeen) contenant le nouveau tableau suivi du booléen pour dire si la lettre existe ou pas.
Mais on peut faire mieux : le tableau est mutable. On peut donc modifier son état (ses "cases") et juste renvoyer le booléen !
4 - Tableaux mutables dans Python
Nous avons vu que les tableaux sont mutables dans Python. Si on veut modifier le contenu d'un tableau dans une fonction, il suffit donc d'avoir son identifiant-mémoire.
Rappel : Fonction et paramètres mutables, l'effet de bord
En Python, les variables font référence à des identifiants-mémoire. Cela provoque des effets dont il faut tenir compte.
>>> tableau = [4, 40, 400]
>>> autre = tableau
Aucune des deux variables ne contient vraiment [4, 40, 400]. En réalité, elles contiennent l'identifiant-mémoire de la zone qui contient [4, 40, 400].
>>> id(tableau)
384
>>> id(autre)
384
La conséquence ? Il ne s'agit pas de deux contenus différents mais d'un seul contenu qui possède plusieurs alias. Si on modifie l'un, on modifie l'autre.
>>> autre[0] = 8000
>>> autre
[8000, 40, 400]
>>> tableau
[8000, 40, 400]
C'est le même phénomène avec un tableau envoyé en tant qu'argument à une fonction : le paramètre de réception ne contient pas le contenu du tableau mais sa référence-mémoire. Du coup, modifier le paramètre modifie aussi le tableau d'origine !
09° Observer l'extrait de code suivant et le prototype de la fonction : que contient en réalité l'argument mot_actuel ?
- mot_actuel contient vraiment ['b', 'o', '*', '*', 'o', '*', '*'] ou
- mot_actuel contient juste l'identifiant-mémoire qui mène à ['b', 'o', '*', '*', 'o', '*', '*']
>>> mot_actuel
['b', 'o', '*', '*', 'o', '*', '*']
>>> trouve = modifier_mot(mot_actuel, vrai_mot, 'u')
>>> mot_actuel
['b', 'o', '*', '*', 'o', 'u', '*']
1 | |
...CORRECTION...
Il s'agit bien évidemment de la référence-mémoire.
Nous allons du coup simplifier notre fonction visant à mettre à jour le mot trouvé pour le moment : nous allons pouvoir modifier directement mot_trouve par effet de bord puisque l'argume nt envoyé mot_trouve et le paramètre mot sont deux alias menant à la même zone-mémoire du tableau des lettres trouvées. Nous allons juste renvoyer un booléen correspondant au fait que la lettre fournie existe bien dans le vrai mot.
10° Modifier la fonction modifier_mot pour qu'elle fonctionne et corresponde bien à la documentation. Attention : elle ne doit donc renvoyer que le booléen existe testant l'existence du caractere dans vrai_mot. Le tableau mot trouvé jusqu'à présent doit être modifié sur place par effet de bord : il suffit d'agir sur le tableau-paramètre mot.
Prototype :
1 | |
La version proposée modifie la copie et renvoie un tuple (tableau, booléen). Ce n'est pas ce qu'on veut.
1
2
3
4
5
6
7
8
9 | |
...CORRECTION...
1
2
3
4
5
6
7
8 | |
11° Notre jeu est presque opérationnel : il manque encore une fonction permettant de savoir si on a fini ou pas.
1
2
3
4
5
6 | |
Expliquer comment fonctionne cette fonction.
D'un point de vue purement algorithmique, ne devrait-on pas plutôt utiliser plutôt un while ?
...CORRECTION...
On crée une boucle bornée qui permet d'obtenir les indice un par un.
On compare alors les cases des deux tableaux case par case (indice par indice).
Si les contenus des cases sont différents, on sort de la fonction en renvoyant FAUX.
Si on arrive à l'instruction finale return True, c'est que tous les caractères étaient identiques.
Comme on peut sortir brutalement de la boucle FOR à cause d'un return False, d'un point de vue algorithmique, cela revient à faire une boucle NON BORNEE : on ne parcourt pas nécessairement TOUTES les cases.
Un while serait donc plus rigoureux ici.
12° Mettre le code total en mémoire. L'utiliser en mode interactif (en tapant directement les appels de fonction dans la console) pour vérifier qu'il fonctionne bien.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | |
Bon, ce n'est pas un 'vrai' jeu pour le moment : il faut taper les fonctions directement dans la console pour jouer... La prochaine activité va vous permettre de réaliser l'interfaçage avec la console.