2022, Amérique du Nord, sujet 1, exercice 4

Thème : Arbres binaires et leurs algorithmes associés

La fédération de badminton souhaite gérer ses compétitions à l'aide d'un logiciel.

Pour ce faire, une structure arbre de compétition a été définie récursivement de la façon suivante : un arbre de compétition est soit l'arbre vide, noté ø, soit un triplet composé d'une chaine de caractères appelée valeur, d'un arbre de compétition appelé sous-arbre gauche et d'un arbre de compétition appelé sous-arbre droit.

On représente graphiquement un arbre de compétition de la façon suivante :

L'arbre de l'introduction

Pour alléger la représentation d'un arbre de compétition, on ne notera pas les arbres vides, l'arbre précédent sera donc représenté par l'arbre \(A\) suivant :

L'arbre \(A\), le précédent simplifié

Note : nous avons ajouté des identifiants unique pour chaque noeud de \(A\).

Cet arbre se lit de la façon suivante :

• 4 participants se sont affrontés : Joris, Kamel, Carine et Abdou. Leurs noms apparaissent en bas de l'arbre, ce sont les valeurs de feuilles de l'arbre.
• Au premier tour, Kamel a battu Joris et Carine a battu Abdou.
• En finale, Kamel a battu Carine, il est donc le vainqueur de la compétition.

Pour s'assurer que chaque finaliste ait joué le même nombre de matchs, un arbre de compétition a toutes ses feuilles à la même hauteur.

Les quatre fonctions suivantes pourront être utilisées :

• La fonction racine qui prend en paramètre un arbre de compétition arb et renvoie la valeur de la racine.

  Exemple : en reprenant l'exemple d'arbre de compétition présenté ci-dessus, racine(A) vaut "Kamel".

• La fonction gauche qui prend un arbre de compétition arb et renvoie son sous-arbre gauche.

  Exemple : en reprenant l'exemple d'arbre de compétition présenté ci-dessus, gauche(A) vaut l'arbre représenté graphiquement ci-après :

  

• La fonction droit qui prend un arbre de compétition arb et renvoie son sous-arbre droit.

  Exemple : en reprenant l'exemple d'arbre de compétition présenté ci-dessus, droit(A) vaut l'arbre représenté graphiquement ci-après :

  

• La fonction est_vide qui prend un arbre de compétition arb et renvoie True si l'arbre est vide et False sinon.

  Exemple : en reprenant l'exemple d'arbre de compétition présenté ci-dessus, est_vide(A) vaut False.

Pour toutes les questions de l'exercice, on suppose que tous les joueurs d'une même compétition ont un prénom différent.

Remarque

Cette première partie prologue présente l'avantage d'être complète et de rappeler à la fois le vocabulaire et les fonctions de l'interface. L'inconvénient est que cela fait beaucoup à lire avant même de commencer la première question.

On considère l'arbre de compétition \(B\) suivant :

L'arbre de compétition \(B\)

Note : Cet arbre va servir pour toutes les questions suivantes. Les identifiants des noeuds ne font pas partie du sujet original.

Questions 1

Question 1a

Indiquer la racine de cet arbre puis donner l'ensemble des valeurs des feuilles de cet arbre.

Réponse

• La racine de l'arbre \(B\) est le noeud identifié 15 : c'est là une ambiguité du sujet qui n'offre pas la possibilité de distinguer les noeuds dont plusieurs partagent la même étiquette.
• Les valeurs des feuilles sont les 8 chaines de caractères : 'Marc', 'Léa', 'Claire', 'Théo', 'Marie', 'Louis', 'Anne' et 'Kévin'.

Question 1b

Proposer une fonction Python vainqueur prenant pour argument un arbre de compétition arb ayant au moins un joueur. Cette fonction doit renvoyer la chaine de caractères constituée du nom du vainqueur du tournoi.

Exemple : vainqueur(B) vaut 'Léa'

Réponse

def vainqueur(arb):
    return racine(arb)

Question 1c

Proposer une fonction Python finale prenant pour argument un arbre de compétition arb ayant au moins deux joueurs. Cette fonction doit renvoyer le tableau des deux chaines de caractères qui sont les deux compétiteurs finalistes.

Exemple : finale(B) vaut ['Léa', 'Louis']

Remarque

Il y a une petite ambiguité dans la question : on ne précise pas l'ordre des finalistes. En se basant sur l'exemple on peut supposer qu'on récupère d'abord le nom du finaliste du sous-arbre gauche.

Réponse

def finale(arb):
    return [racine(gauche(arb)), racine(droit(arb))]

Questions 2

Question 2a

Proposer une fonction Python occurrences ayant pour paramètres un arbre de compétition abr et le nom d'un joueur nom et qui renvoie le nombre d'occurrences (d'apparitions) du joueur nom dans l'arbre de compétition arb.

Exemple : occurrences(B, "Anne") vaut 2

Réponse

def occurrences(arb, nom):
    tmp = 0
    if est_vide(arb):
        return 0
    else: 
        if racine(arb) == nom:
            tmp = 1
        return tmp + occurrences(gauche(arb), nom) + occurrences(droit(arb), nom)

Question 2b

Proposer une fonction Python a_gagne ayant pour paramètres un arbre de compétition abr et le nom d'un joueur nom et qui renvoie le booléen True si le joueur nom a gagné au moins un match dans la compétition représentée par l'arbre de compétition arb.

Exemple : a_gagne(B, "Louis") vaut True

Réponse

def a_gagne(arb, nom):
    return occurrences(arb, nom) > 1

Justification : chaque joueur apparait au moins une fois, en feuille de l'arbre de compétition ; gagner ne serait-ce que son premier match fait apparaitre le nom une deuxième fois.

Questions 3

On souhaite programmer une fonction Python nombre_matchs qui prend pour arguments un arbre de compétition arb et le nom d'un joueur nomet qui renvoie le nombre de matchs joués par le joueur nom dans la compétition représentée par l'arbre de compétition arb.

Exemple : nombre_matchs(B, 'Léa') doit valoir 3 et nombre_matchs(B, 'Marc') doit valoir 1.

Question 3a

Expliquer pourquoi les instructions suivantes renvoient une valeur erronée. On pourra pour cela identifier le noeud de l'arbre qui provoque une erreur.

def nombre_matchs(arb, nom):
    """arbre_competition, str -> int"""
    return occurrences(arb, nom)

Réponse

Si on fait abstraction de la racine, chaque noeud à un frère qui est l'opposant dans un match. Ainsi, chaque apparition est bien un match joué, sauf pour la racine qui représente le ou la gagnant.e du tournoi.

Question 3b

Proposer une correction pour la fonction nombre_matchs.

Réponse

def nombre_matchs(arb, nom):
    """arbre_competition, str -> int"""
    occ = occurrences(arb, nom)
    if vainqueur(arb, nom):
        return occ - 1
    else:
        return occ 

Question 4

Question 4

Recopier et compléter la fonction liste_joueurs qui prend pour argument un arbre de compétition arb et qui renvoie un tableau contenant les participants au tournoi, chaque nom ne devant figurer qu'une seule fois dans le tableau.

L'opération + de la ligne 8 permet de concaténer deux tableaux.

Exemple : Si L1 = [4, 6, 2] et L2 = [3, 5, 1], l'instruction L1 + L2 va renvoyer le tableau [4, 6, 2, 3, 5, 1]

def liste_joueurs(arb):
    """arbre_competition -> tableau"""
    if est_vide(arb):
        return ...
    elif ... and ... :
        return [racine(arb)]
    else:
        return ... + liste_joueurs(droit(arb))

Remarque

Cette question est un peu trop mâchée pour être une dernière question d'exercice. Il aurait fallu laisser le candidat rédiger la quasi totalité de la fonction.

On note aussi une petite imprécision dans l'énoncé : confusion entre instruction et expression ; L1 + L2 est une expression qui s'évalue au tableau [4, 6, 2, 3, 5, 1].

Réponse

def liste_joueurs(arb):
    """arbre_competition -> tableau"""
    if est_vide(arb):
        return []
    elif est_vide(gauche(arb)) and est_vide(droit(arb)):
        return [racine(arb)]
    else:
        return liste_joueurs(gauche(arb)) + liste_joueurs(droit(arb))

Conclusion

Sujet assez simple, qui comporte quelques maladresses (relevées dans les Remarques) et avec quelques lourdeurs dans les énoncés. Par exemple :

renvoie le nombre de matchs joués par le joueur nom dans la compétition représentée par l'arbre de compétition arb.