Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction ajoute_dictionnaires qui prend en paramètres deux dictionnaires d1 et d2 dont les clés sont des nombres et 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 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.

Exemples :

>>> ajoute_dictionnaires({1: 5, 2: 7}, {2: 9, 3: 11})
{1: 5, 2: 16, 3: 11}
>>> ajoute_dictionnaires({}, {2: 9, 3: 11})
{2: 9, 3: 11}
>>> ajoute_dictionnaires({1: 5, 2: 7}, {})
{1: 5, 2: 7}

Exercice 2

EXERCICE 2 (10 points)

On considère une piste carrée qui contient 4 cases par côté. Les cases sont numérotées de 0 inclus à 12 exclu comme ci-dessous :

[Figure : grille carrée de 4 cases sur 4 ; les cases du pourtour sont numérotées dans le sens des aiguilles d’une montre et les quatre cases centrales sont vides.]

L’objectif de l’exercice est d’implémenter le jeu suivant :

Au départ, le joueur place son pion sur la case 0. A chaque coup, il lance un dé équilibré à six faces et avance son pion d’autant de cases que le nombre indiqué par le dé (entre 1 et 6 inclus) dans le sens des aiguilles d’une montre.

Par exemple, s’il obtient 2 au premier lancer, il pose son pion sur la case 2 puis s’il obtient 6 au deuxième lancer, il le pose sur la case 8, puis s’il obtient à nouveau 6, il pose le pion sur la case 2.

Le jeu se termine lorsque le joueur a posé son pion sur toutes les cases de la piste.

Compléter la fonction nombre_coups ci-dessous de sorte qu’elle renvoie le nombre de lancers aléatoires nécessaires pour terminer le jeu.

from random import randint

def nombre_coups():
    '''Simule un jeu de plateau avec 12 cases et renvoie le nombre
    nécessaire de coups pour visiter toutes les cases.'''
    nombre_cases = 12
    # indique si une case a été vue
    cases_vues = [ False ] * nombre_cases
    nombre_cases_vues = 1
    cases_vues[0] = True
    case_en_cours = 0
    n = ...
    while ... < ...:
        x = randint(1, 6)
        case_en_cours = (case_en_cours + ...) % ...
        if ...:
            cases_vues[case_en_cours] = True
            nombre_cases_vues = ...
        n = ...
    return n

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• d1 et d2 sont des dictionnaires dont les clés sont des entiers et les valeurs des entiers
• 0 <= len(d1) <= 10^3 et 0 <= len(d2) <= 10^3
• d1 et d2 peuvent être vides
• -10^6 <= cle <= 10^6 pour toute clé cle de d1 ou de d2
• -10^6 <= valeur <= 10^6 pour toute valeur de d1 ou de d2
• la fonction renvoie un dictionnaire ; l’ordre de ses clés n’est pas imposé

Exercice 2

Contraintes :

• nombre_coups ne prend aucun paramètre et ne lit aucune entrée
• la piste comporte exactement 12 cases, numérotées de 0 à 11
• chaque lancer de dé donne un entier compris entre 1 et 6 inclus
• le pion part de la case 0, qui est déjà considérée comme visitée
• la valeur renvoyée est un entier aléatoire supérieur ou égal à 11

Solution - Sujet 26

Exercice 1 - ajoute_dictionnaires

L’idée. On fabrique un dictionnaire tout neuf, d. On y recopie d’abord tout d1. Puis on parcourt d2 : si la clé est déjà dans d, on ajoute sa valeur à celle qui s’y trouve déjà ; sinon on installe la clé avec sa valeur. À la fin, d contient bien la réunion des clés, avec les sommes là où il fallait.

Un exemple. Pour {1: 5, 2: 7} et {2: 9, 3: 11} : on recopie 1: 5 puis 2: 7. Ensuite la clé 2 de d2 est déjà là, donc 7 + 9 = 16 ; la clé 3 est nouvelle, donc 3: 11. Résultat : {1: 5, 2: 16, 3: 11}.

def ajoute_dictionnaires(d1, d2):
    d = {}
    for cle in d1:
        d[cle] = d1[cle]
    # une cle deja copiee voit sa valeur augmentee, une cle nouvelle est ajoutee
    for cle in d2:
        if cle in d:
            d[cle] = d[cle] + d2[cle]
        else:
            d[cle] = d2[cle]
    return d

d part vide et grossit au fur et à mesure : on ne modifie jamais d1 ni d2, et c’est important car celui qui appelle la fonction peut vouloir les réutiliser ensuite. Le test if cle in d est exactement ce qui sépare les deux cas de l’énoncé : clé commune (on additionne) ou clé nouvelle (on recopie). Si un des deux dictionnaires est vide, la boucle correspondante ne tourne pas du tout et le résultat est simplement une copie de l’autre.

Exercice 2 - nombre_coups

L’idée. On relance le dé tant qu’il reste des cases à découvrir. La piste est un cercle de 12 cases : avancer de x cases depuis case_en_cours s’écrit (case_en_cours + x) % 12, le % ramenant tout seul de la case 11 à la case 0. À chaque tour on marque la case d’arrivée comme vue, mais on n’augmente le compteur de cases vues que si elle n’avait pas déjà été visitée. Et dans tous les cas on compte le lancer.

Un exemple. Au départ le pion est sur la case 0, déjà vue, donc nombre_cases_vues vaut 1. Un 2 mène à la case 2, nouvelle : 2 cases vues. Un 6 mène à la case 8, nouvelle : 3 cases vues. Un nouveau 6 mène à (8 + 6) % 12 = 2, déjà vue : le compteur de cases vues ne bouge pas, alors que n vaut déjà 3.

from random import randint

def nombre_coups():
    '''Simule un jeu de plateau avec 12 cases et renvoie le nombre
    nécessaire de coups pour visiter toutes les cases.'''
    nombre_cases = 12
    # indique si une case a été vue
    cases_vues = [ False ] * nombre_cases
    nombre_cases_vues = 1
    cases_vues[0] = True
    case_en_cours = 0
    n = 0
    while nombre_cases_vues < nombre_cases:
        x = randint(1, 6)
        case_en_cours = (case_en_cours + x) % nombre_cases
        if not cases_vues[case_en_cours]:
            cases_vues[case_en_cours] = True
            nombre_cases_vues = nombre_cases_vues + 1
        n = n + 1
    return n

Deux compteurs bien distincts : n compte les lancers de dé, nombre_cases_vues compte les cases différentes déjà touchées. La boucle s’arrête quand les 12 cases sont vues, d’où while nombre_cases_vues < nombre_cases : c’est un < et non un <=, car dès que le compteur atteint 12 il n’y a plus rien à découvrir. Le test if not cases_vues[case_en_cours] empêche de compter deux fois la même case, comme dans l’exemple ci-dessus avec le retour sur la case 2. Enfin n = n + 1 est placé en dehors du if, à la fin du tour : un lancer compte même s’il ne fait rien découvrir. Comme la case 0 est déjà visitée avant la boucle, il reste 11 cases à trouver et la fonction renvoie donc toujours au moins 11.