Exercice 1 - Arbres · Bac Numérique et Sciences Informatiques Amérique du Nord 2022 (jour 2)

Cet exercice porte sur les listes, les arbres binaires de recherche et la programmation orientée objet.

Lors d'une compétition de kayak, chaque concurrent doit descendre le même cours d'eau en passant dans des portes en un minimum de temps. Si le concurrent touche une porte, il se voit octroyé une pénalité en secondes. Son résultat final est le temps qu'il a mis pour descendre le cours d'eau auquel est ajouté l'ensemble des pénalités qu'il a subies.

Un gestionnaire de course de kayak développe un programme Python pour gérer les résultats lors d'une compétition.

Dans ce programme, pour modéliser les concurrents et leurs résultats, une classe Concurrent est définie avec les attributs suivants:

nom de type Str qui représente le pseudonyme du compétiteur;

temps de type Float qui est le temps mis pour réaliser le parcours en secondes;

penalites de type Int qui est le nombre de secondes de pénalité cumulées octroyées au concurrent;

temps_tot de type Float qui correspond au temps total, c'est-à-dire au temps mis pour réaliser le parcours auquel on a ajouté les pénalités.

On suppose que tous les concurrents ont des temps différents dans cet exercice.

Le code Python incomplet de la classe Concurrent est donné ci-dessous:

class Concurrent:

def __init__(self, pseudo, temps, penalite):

self.nom = pseudo

self.temps = temps

self.penalite =...

self.temps_tot =...

4. Pour simplifier le stockage des résultats, on décide de stocker les objets de la classe Concurrent dans un arbre binaire de recherche. Chaque nœud de cet arbre est donc un objet Concurrent.

Dans cet arbre binaire de recherche, en tout nœud:

le concurrent enfant à gauche est plus rapide que le nœud;

le concurrent enfant à droite est moins rapide que le nœud.

Pour implémenter la structure d'arbre binaire de recherche, on dispose d'une classe Arbre munie, entre autres, d'une méthode ajout qui prend en paramètre un objet c de type Concurrent et qui modifie l'arbre binaire sur lequel elle s'applique, en y ajoutant le concurrent c tout en maintenant la propriété d'arbre binaire de recherche.

On ajoute dans un arbre vide successivement les concurrents de la liste resultats en partant de la tête de la liste (soit, dans le cas présent, c6, puis c5, puis c4,...).

Dessiner l'arbre binaire de recherche obtenu. On rappelle le temps total de chaque concurrent:

Concurrent

c6

c5

c4

c3

c2

c1

temps_tot

93,45

94,12

136,32

90,54

93,73

99,67