Loading [MathJax]/jax/output/HTML-CSS/fonts/STIX-Web/fontdata.js

Autour des dictionnaires

📝 Rappels 📝

Soit dico un dictionnaire.

  • Les clefs de dico doivent être hachables et donc NE peuvent PAS être des containers mutables (list, dict ou set).
  • On parcourt les clefs avec l'instruction for k in dico.keys() : ou, plus simplement, for k in dico :.
  • On parcourt les valeurs avec l'instruction for v in dico.values() :.
  • On parcourt les paires clef:valeur avec l'instruction for k, v in dico.items() :.

📝 Fin des rappels 📝

Question 1 :

Pourquoi l'instruction suivante provoque-t-elle une erreur ?

Entrée[ ]:
Solution

L'instruction provoque une erreur parce que les clefs utilisées sont des tableaux (de type list) qui ne sont pas hachables.

Question 2 :

On s'intéresse au stockage des données issues d'un vote en ligne.

Compléter le code de la fonction comptage qui :

  • prend en paramètre un tableau t de chaînes de caractères,
  • renvoie un dictionnaire ayant :
    • pour clefs les chaînes de caractères du tableau t,
    • pour valeurs les effectifs de chaque chaîne de caractères dans le tableau t.

On pourra consulter le jeu de tests si besoin.

Entrée[ ]:
Entrée[ ]:
Solution 
def comptage(t):
    d = {}
    for chaine in t:
        if chaine in d.keys():
            d[chaine] = d[chaine] + 1
        else:
            d[chaine] = 1
    return d

Question 3 :

On s'intéresse à la mise en commun des données issues de deux votes différents.

Compléter le code de la fonction fusion_de_votes qui :

  • prend en paramètres deux dictionnaires d1 et d2 dont les clés sont des chaînes de caractères,
  • renvoie le dictionnaire d défini de la façon suivante :
    • Les clés de d sont celles de d1 et celles de d2 réunies.
    • Si une clé est présente dans les deux dictionnaires d1 et d2, sa valeur associée dans le dictionnaire d est la somme de ses valeurs dans les dictionnaires d1 et d2.
    • Si une clé n’est présente que dans un seul des deux dictionnaires, sa valeur associée dans le dictionnaire d est la même que sa valeur dans le dictionnaire où elle est présente.

On pourra consulter le jeu de tests si besoin.

Entrée[ ]:
Entrée[ ]:
Solution 
def fusion_de_votes(d1, d2):
    d = {}
    
    #on recopie les données de d1 dans d
    for k, v in d1.items():
        d[k] = v
      
    #On intègre les données de d2 dans d en faisant attention aux clefs déjà présentes
    for k, v in d2.items():
        if k in d.keys():
            d[k] = d[k] + v
        else:
            d[k] = v
        
    return d

Question 4 :

On s'intéresse au nombre total de votes d'un dictionnaire.

Compléter le code de la fonction total_votes qui :

  • prend en paramètre un dictionnaire d1 dont les clefs sont des chaînes de caractères et dont les valeurs sont des entiers positifs,
  • renvoie un entier correspondant à la somme de toutes les valeurs du dictionnaire.

On pourra consulter le jeu de tests si besoin.

Entrée[ ]:
Entrée[ ]:
Solution

Avec un parcours par valeurs (le plus naturel) :

def total_votes(d):
    s = 0
    for v in d.values():
        s = s + v
    return s

Avec un parcours par clefs :

def total_votes(d):
    s = 0
    for k in d:
        s = s + d[k]
    return s

ou 

def total_votes(d):
    s = 0
    for k in d.keys():    #<---- différence ici
        s = s + d[k]
    return s

Question 5 :

On s'intéresse aux vainqueurs d'un vote.

Compléter le code de la fonction vainqueurs_vote qui :

  • prend en paramètre un dictionnaire d1 non vide dont les clefs sont des chaînes de caractères et dont les valeurs sont des entiers positifs,
  • renvoie un tableau (de type list) contenant la clef ou les clefs associée(s) à la valeur maximale du dictionnaire, clefs qui seront triées par ordre croissant.

On pourra consulter le jeu de tests si besoin.

Remarque : pour le tri on pourra utiliser la méthode sort :

>>> S = ['A', 'B', 'S', 'D', 'F']
>>> S.sort()
>>> S
['A', 'B', 'D', 'F', 'S']
Entrée[ ]:
Entrée[ ]:
Solution

Avec un parcours par paires clef:valeur (le plus naturel) :

def vainqueur_vote(d):
    nb_votes_max = 0
    prenoms_max = []
    
    for prenom, nb_votes in d.items():
        if nb_votes > nb_votes_max:
            nb_votes_max = nb_votes
            prenoms_max = [prenom]
        elif nb_votes == nb_votes_max:
            prenoms_max.append(prenom)
            
    return prenoms_max

Avec un parcours des clefs :

def vainqueur_vote(d):
    nb_votes_max = 0
    prenoms_max = []
    
    for prenom in d.keys():
        if d[prenom] > nb_votes_max:
            nb_votes_max = d[prenom]
            prenoms_max = [prenom]
        elif d[prenom] == nb_votes_max:
            prenoms_max.append(prenom)
            
    return prenoms_max

ou

def vainqueur_vote(d):
    nb_votes_max = 0
    prenoms_max = []
    
    for prenom in d:                   #<--- différence ici
        if d[prenom] > nb_votes_max:
            nb_votes_max = d[prenom]
            prenoms_max = [prenom]
        elif d[prenom] == nb_votes_max:
            prenoms_max.append(prenom)
            
    return prenoms_max

Question 6 :

On considère au plus 26 personnes A, B, C, D, E, F ... qui peuvent s'envoyer des messages avec deux règles à respecter :

  • chaque personne ne peut envoyer des messages qu'à la même personne (éventuellement elle-même),
  • chaque personne ne peut recevoir des messages qu'en provenance d'une seule personne (éventuellement elle-même).

Voici un exemple - avec 6 personnes - de « plan d'envoi des messages » qui respecte les règles ci-dessus, puisque chaque personne est présente une seule fois dans chaque colonne :

  • A envoie ses messages à E
  • E envoie ses messages à B
  • B envoie ses messages à F
  • F envoie ses messages à A
  • C envoie ses messages à D
  • D envoie ses messages à C

Et le dictionnaire correspondant à ce plan d'envoi est le suivant :

plan_a = {'A':'E', 'B':'F', 'C':'D', 'D':'C', 'E':'B', 'F':'A'}

Sur le plan d'envoi plan_a des messages ci-dessus, il y a deux cycles distincts : un premier cycle avec A, E, B, F et un second cycle avec C et D.

En revanche, le plan d’envoi plan_b ci-dessous :

plan_b = {'A':'C', 'B':'F', 'C':'E', 'D':'A', 'E':'B', 'F':'D'}

comporte un unique cycle : A, C, E, B, F, D. Dans ce cas, lorsqu’un plan d’envoi comporte un unique cycle, on dit que le plan d’envoi est cyclique.

Pour savoir si un plan d'envoi de messages comportant N personnes est cyclique, on peut utiliser l'algorithme ci-dessous :

On part de la personne A et on inspecte les N – 1 successeurs dans le plan d'envoi :

  • Si un de ces N – 1 successeurs est A lui-même, on a trouvé un cycle de taille inférieure ou égale à N – 1. Il y a donc au moins deux cycles et le plan d'envoi n'est pas cyclique.
  • Si on ne retombe pas sur A lors de cette inspection, on a un unique cycle qui passe par toutes les personnes : le plan d'envoi est cyclique.

Compléter la fonction suivante en respectant la spécification.

Remarque : la fonction python len permet d'obtenir la longueur d'un dictionnaire.

Entrée[ ]:
Entrée[ ]: