Exercice 4 · Bac Numérique et Sciences Informatiques Amérique du Nord 2021 (jour 1)

Cet exercice porte sur les 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é $\emptyset$, soit un triplet composé d'une chaîne 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:

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:

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 en paramètre un arbre de compétition arb et renvoie son sous-arbre gauche.

Exemple: gauche(A) vaut l'arbre représenté graphiquement ci-après:

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

Exemple: droit(A) vaut l'arbre représenté graphiquement ci-dessous:

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

Exemple: 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.

1.

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

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

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

Exemple: vainqueur(B) vaut "Lea"

(c) 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 chaînes de caractères qui sont les deux compétiteurs finalistes.

Exemple: finale(B) vaut ["Lea", "Louis"]

2.

(a) Proposer une fonction Python occurrences ayant pour paramètre un arbre de compétition arb 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.

(b) Proposer une fonction Python a_gagne prenant pour paramètres un arbre de compétition arb 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

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 nom et 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, "Lea") doit valoir 3 et nombre_matchs(B, "Marc") doit valoir 1.

(a) 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)

(b) Proposer une correction pour la fonction nombre_matchs.

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 + à 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))