---
tags: corrTD, info, dict, 2425
---
# <center>TD3 : dictionnaires</center>
> :books: Documents de base : le [cours](http://demeslay.maths.free.fr/fichiers/info/spe/01_dictionnaires_cours.pdf) et le [TD3](http://demeslay.maths.free.fr/fichiers/info/spe/TD03_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 5 : 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 6 : 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 7 : 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 8 : 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.