---
tags: corrTD, info, dict, 2526
---
<center>TD3 : dictionnaires</center>
===
> :books: Documents de base : le [cours](http://demeslay.maths.free.fr/fichiers/info/1_dictionnaires_cours.pdf) et le [TD3](http://demeslay.maths.free.fr/fichiers/info/TD3_dictionnaires.pdf). [color=red]
[TOC]
## Exercice 1 : Comptage d'éléments
* **Q1.** On parcourt le texte, si on croise un nouveau caractère, on initialise le compteur correspondant à 1, sinon on l'incrémente de 1.
```python=
def comptage(texte: str) -> dict:
"""
Renvoie le dictionnaire dont les clés sont
les caractères présents dans texte et
les valeurs leur nombre d'occurrences.
"""
occurrences = {}
for cara in texte:
if cara not in occurrences:
occurrences[cara] = 1
else:
occurrences[cara] = occurrences[cara] + 1
return occurrences
```
> :eye: Pour visualiser l'exécutation pas à pas de ce code sur un exemple, suivre [ce lien](https://pythontutor.com/render.html#code=def%20comptage%28texte%3A%20str%29%20-%3E%20dict%3A%0A%20%20%20%20occurrences%20%3D%20%7B%7D%0A%20%20%20%20for%20cara%20in%20texte%3A%0A%20%20%20%20%20%20%20%20if%20cara%20not%20in%20occurrences%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20occurrences%5Bcara%5D%20%3D%201%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20occurrences%5Bcara%5D%20%3D%20occurrences%5Bcara%5D%20%2B%201%0A%20%20%20%20return%20occurrences%0A%0Acomptage%28%22Je%20retravaille%20mon%20TD%20d'informatique.%22%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false) puis cliquer sur le bouton *Next* autant que nécessaire. [color=green]
* **Q2.** Il s'agit d'un simple parcours de la chaîne `texte` et d'après le cours le test d'appartenance ou non au dictionnaire présent en ligne 9 est de complexité constante $O(1)$. Cette fonction est donc de complexité $O(n)$ où $n$ est la longueur de `texte`.
---
## Exercice 2 : Marchandises disponibles
* **Q1.** On teste d'abord si le produit existe (= la clé existe dans le dictionnaire) puis s'il est en nombre suffisant (= quantité demandée inférieure ou égale à la valeur dans le dictionnaire).
```python=
def possible(stock: dict, produit: str, quantite: int) -> bool:
"""
Renvoie si oui ou non il y a au moins quantite du
produit dans le stock.
"""
if produit not in stock:
return False
if stock[produit] < quantite:
return False
return True
```
Les conditions des lignes 6 à 9 peuvent être regroupées avec un `or` :
```python
if produit not in stock or stock[produite] < quantite:
return False
```
On pourrait même renvoyer directement un booléen en vérifiant la condition :
```python
def possible(stock: dict , produit: str , quantite: int) -> bool:
return produit in stock and stock[produit] >= quantite
```
:::info
:bulb: **À retenir** : Il est souvent nécessaire de vérifier que quelque chose est bien une clef valide d'un dictionnaire avant de s'intéresser à la valeur associée.
:::
* **Q2.** Prenons par exemple `stock = {"bananes": 10, "pommes": 5, "oranges": 2}`. Un jeu de test pourrait être donné par
| Cas testé | `produit` | `quantite` | résultat attendu |
|:----------------- |:----------- |:---------- | ---------------- |
| quantité large | `"bananes"` | 5 | `True ` |
| quantité maxi | `"bananes"` | 10 | `True ` |
| quantité dépassée | `"bananes"` | 40 | `False` |
| pas ce produit | `"poires"` | 3 | `False` |
On aurait pu aussi vérifier le cas d'un stock vide, de celui d'une marchandise que l'on commande en quantité 0, etc.
---
## Exercice 3 : Scrabble
* **Q1.** On crée le dictionnaire avec la syntaxe `clef:valeur` :
```python
POINTS = {'A':1, 'B':3, 'C':3, 'D':2, 'E':1, 'F':4, 'G':2, 'H':4, 'I':1, 'J':8, 'K':10, 'L':1, 'M':2, 'N':1, 'O':1, 'P':3, 'Q':8, 'R':1, 'S':1, 'T':1, 'U':1, 'V':4, 'W':10, 'X':10, 'Y':10, 'Z':10}
```
* **Q2.** On reconnaît un classique algorithme de somme mais où il faut aller chercher les valeurs dans un dictionnaire.
```python
def score(mot: str) -> int:
"""
Renvoie la valeur du mot au scrabble.
"""
total = 0
for lettre in mot:
total = total + POINTS[lettre]
return total
```
:::info
On a utilisé ici une variable *globale* (par opposition à *locale* qui désigne les variables définies dans le corps d'une fonction).
Cette variable globale est définie en dehors de toute fonction et on peut l'utiliser partout : hors et dans les fonctions.
Par convention, on écrit souvent en majuscules le nom des variables globales.
:::
---
<!--
## Exercice 4 : Alphabet radio
```python
CODE = {'A': 'Alpha', 'B': 'Bravo', 'C': 'Charlie', 'D': 'Delta', 'E': 'Echo', 'F': 'Foxtrot', 'G': 'Golf', 'H': 'Hotel', 'I': 'India', 'J': 'Juliett', 'K': 'Kilo', 'L': 'Lima', 'M': 'Mike', 'N': 'November', 'O': 'Oscar', 'P': 'Papa', 'Q': 'Quebec', 'R': 'Romeo', 'S': 'Sierra', 'T': 'Tango', 'U': 'Uniform', 'V': 'Victor', 'W': 'Whiskey', 'X': 'Xray', 'Y': 'Yankee', 'Z': 'Zulu'}
def codage_radio(texte: str) -> str:
"""
Transcription en alphabet radio de la chaîne texte.
On a supposé que texte ne contient que des majuscules et des espaces.
"""
message = ""
for lettre in texte:
if lettre != ' ':
message = message + CODE[lettre] + ' '
return message
```
---
-->
## Exercice 4 : Avec des chaînes de caractères
* **Q1.** Il s'agit d'un classique algorithme de maximum mais sur les entrées d'un dictionnaire.
On commence par rappeler l'algorithme du maximum sur une liste :
```python=
def max(L):
"""
Renvoie l'indice et la valeur du maximum
parmi les éléments de la liste L.
"""
imax = 0
vmax = L[imax]
for i in range(1, len(L)):
if L[i] > vmax:
imax = i
vmax = L[i]
return imax, vmax
```
Il faut donc principalement modifier les lignes 6 et 7 (initialisations) ainsi que la ligne 8 (parcours).
```python
def plus_frequent(texte: str) -> (str, int):
"""
Renvoie le caractère le plus fréquent dans texte
ainsi que son nombre d'occurrences.
"""
occur = comptage(texte) # cf exercice 1
lettre_max = ''
valeur_max = 0
for lettre in occur:
if occur[lettre] > valeur_max:
lettre_max = lettre
valeur_max = occur[lettre]
return lettre_max, valeur_max
```
* **Q2.** Par rapport à la fonction précédente, il faut distinguer les cas où l'on a une nouvelle valeur maximale (cas comme la question précédente) et le cas où l'on a une égalité avec la valeur maximale en cours (dans ce cas on doit ajouter la lettre à la liste de celles correspondant déjà au maximum).
```python
def plus_frequent_v2(texte: str) -> (str, int):
"""
Renvoie la liste des caractères les plus fréquents
dans texte ainsi que leur nombre d'occurrences.
"""
occur = comptage(texte) # cf exercice 1
lettre_max = []
valeur_max = 0
for lettre in occur:
if occur[lettre] == valeur_max:
lettre_max.append(lettre)
elif occur[lettre] > valeur_max:
lettre_max = lettre
valeur_max = occur[lettre]
return lettre_max, valeur_max
```
* **Q3.**
On se ressert de la fonction `comptage` de **Q1**, il s'agira alors simplement de comparer si les deux dictionnaires obtenus sont égaux.
```python
def compare(chaine1: str, chaine2: str) -> bool:
"""
Renvoie si oui ou non les deux chaines contiennent
les mêmes caractères (ordre quelconque).
"""
if len(chaine1) != len(chaine2):
return False
occ1 = comptage(chaine1)
occ2 = comptage(chaine2)
# On compare les deux dictionnaires
for cara in occ1:
if cara not in occ2:
return False
if occ1[cara] != occ2[cara]:
return False
return True
```
On pourrait aussi vouloir vérifier que les clés de `dc2` sont bien aussi des clés de `dc1` mais cela n'est pas nécessaire grâce au test sur les longueurs au début.
:::info
:bulb: **À retenir** : Pour comparer deux dictionnaires `D1` et `D2`, on doit vérfier qu'ils ont les mêmes clés (toutes celles de `D1` sont dans `D2` et vice-versa), et que pour chaque clé les valeurs sont les mêmes.
:::
---
## Exercice 5 : Créer un dictionnaire à partir de deux listes
* **Q1.** On parcourt les deux listes en même temps et on insère les couples (clé, valeur) au fur et à mesure dans le dictionnaire initialement vide.
```python
def creation(cles: list, valeurs: list) -> dict:
"""
Renvoie le dictionnaire dont les clés et les valeurs
sont dans les deux listes données en arguments.
On suppose ces deux listes de même longueur.
"""
assert len(cles) == len(valeurs)
dico = {}
for i in range(len(cles)): # ou len(valeurs)
dico[cles[i]] = valeurs[i]
return dico
```
* **Q2.** Deux cas suivant les longueurs respectives des deux listes : si `len(cles) <= len(valeurs)`, c'est comme Q1. Sinon on doit ajouter des `None` pour les valeurs manquantes.
Voici une première façon de faire :
```python
def creation_v2(cles: list, valeurs: list) -> dict:
dico = {}
for i in range(len(cles)):
if i < len(valeurs):
dico[cles[i]] = valeurs[i]
else:
dico[cles[i]] = None
return dico
```
On peut aussi faire appel à la fonction de **Q1** :
```python
def creation_v3(cles: list, valeurs: list) -> dict:
dico = {}
if len(cles) <= len(valeurs):
return creation(cles, valeurs)
else:
# Création d'une nouvelle liste de valeurs où
# on rajoute à la fin le bon nombre de None.
new_val = valeurs.copy()
for i in range(len(cles), len(valeurs)):
new_val.append(None)
return creation(cles, new_val)
```
---
## Exercice 6 : Graphes
* **Q1.**
```python
graphe = {'A': ['B', 'C', 'E'],
'B': ['D'],
'C': ['E'],
'D': ['C', 'E'],
'E': []}
```
* **Q2.** Idées :
- On initialise un nouveau graphe vide.
- On parcourt les sommets du graphe (donc les clés du dictionnaire) et on les mets comme clés du nouveau graphe avec des listes vides comme valeurs associées.
- On parcourt à nouveau les sommets du graphe et pour chacun, on parcourt les valeurs associées (c'est-à-dire les voisins dudit sommet). Pour chacun de ces voisins, dans le nouveau graphe, on ajoute le sommet de départ à la liste associée à ce voisin.
```python
def inverse(graphe: dict) -> dict:
"""
Renvoie le dictionnaire représentant le graphe
construit à partir du graphe donné en argument
en inversant le sens de chaque arête.
"""
ginv = {}
for sommet in graphe:
ginv[sommet] = []
for sommet in graphe:
for voisin in graphe[sommet]:
ginv[voisin].append(sommet)
return ginv
```
---
## Exercice 7 : Des paires de chaussettes
Idée :
- on compte d'abord le nombre de chaussettes de chaque couleur (ressemble à l'exercice 1),
- pour chaque couleur, on calcule le nombre de paires faisables grâce à l'opérateur `//` (division entière),
- on réalise un algorithme de somme (voir exercice 3) sur ces nombres de paires.
---
## Exercice 8 : Une fonction à comprendre
Ce programme sert à réaliser une tâche très simple, compréhensible sans connaissance en informatique (mais pour sa réalisation c'est une autre affaire).
Faites des tests pour vous donner de l'intuition puis essayez de comprendre comment cela fonctionne.