Aller au contenu

Club d'Informatique⚓︎

D'après 2022, Nouvelle-Calédonie, J1, Ex. 4

Un club de passionnés d'informatique fonctionne de la façon suivante : pour être membre du club, à l'exception du fondateur ou de la fondatrice, il faut être parrainé. De plus, chaque membre peut parrainer au maximum deux personnes.

Dans ce club, on distingue trois profils de membres :

  • membre or : le membre a parrainé deux personnes ;
  • membre argent : le membre a parrainé une seule personne ;
  • membre bronze : le membre n'a parrainé personne.

On peut modéliser ce fonctionnement de parrainage à l'aide d'un arbre binaire dont les étiquettes sont les pseudonymes des membres du club. Lorsque deux personnes ont été parrainées, celle qui a été parrainée en premier apparait comme racine du sous-arbre à gauche tandis que l'autre est racine du sous-arbre à droite.

On donne ci-dessous l'arbre \(P\) représentant les membres du club issus des parrainages de AnneB, fondatrice du club. Par exemple, Sophia a parrainé Malik2 avant AstridM.

arbre du club

On munit la structure de données ArbreBinaire des opérations suivantes :

Interface de la structure ArbreBinaire

🐍 Script Python
def est_vide(arbre: ArbreBinaire) -> bool:
    """renvoie True si arbre est vide, False sinon"""

def racine(arbre: ArbreBinaire) -> str:
    """renvoie l'étiquette du nœud racine de arbre"""

def gauche(arbre: ArbreBinaire) -> ArbreBinaire:
    """renvoie le sous-arbre à gauche de arbre"""

def droite(arbre: ArbreBinaire) -> ArbreBinaire:
    """renvoie le sous-arbre à droite de arbre"""

1) On appelle feuille, un nœud qui ne possède pas de successeurs ou dit autrement dont l'arbre dont il est la racine possède deux sous-arbres vides. On définit la hauteur d'un arbre binaire non vide comme la longueur (en nombre de nœuds) du plus long chemin allant de la racine à une feuille. Un arbre vide a une hauteur égale à \(0\).

1.a) Indiquer la hauteur de l'arbre \(P\)

Réponse

L'arbre binaire \(P\) a une hauteur de \(4\) (par exemple en considérant le chemin qui va de la racine 'AnneB' jusqu'à la feuille 'Marc', on dénombre bien \(4\) nœuds, aucun autre chemin en dénombre plus).

1.b) Recopier et compléter la définition de la fonction récursive hauteur qui prend un arbre binaire en paramètre et renvoie la hauteur de cet arbre. On pourra utiliser la fonction max renvoyant la valeur maximale entre deux valeurs.

hauteur
1
2
3
4
5
6
7
def hauteur(arbre):
    if ...... :
        return 0
    else:
        hauteur_a_gauche = hauteur(gauche(arbre))
        hauteur_a_droite = ......
        return 1 + ......
Réponse
hauteur
1
2
3
4
5
6
7
def hauteur(arbre):
    if est_vide(arbre) :
        return 0
    else:
        hauteur_a_gauche = hauteur(gauche(arbre))
        hauteur_a_droite = hauteur(droite(arbre))
        return 1 + max(hauteur_a_gauche, hauteur_a_droite)

1.c) Indiquer le type de la valeur renvoyée par la fonction hauteur

Réponse

Il s'agit d'un entier (type int)

2) La fonction membres ci-dessous prend un arbre binaire et une liste_membres en paramètres et ajoute, dans un certain ordre, les étiquettes de l'arbre à la liste_membres.

membres
1
2
3
4
5
def membres(arbre, liste_membres):
    if not est_vide(arbre):
        liste_membres.append(racine(arbre))
        membres(gauche(arbre), liste_membres)
        membres(droite(arbre), liste_membres)

2.a) En supposant la liste membres_p initialement vide, écrire la valeur de cette liste après l'appel membres(arbre_p, membres_p)arbre_p référence l'arbre \(P\).

Réponse
🐍 Console Python
>>> membres_p
['AnneB', 'Pedro', 'FredB', 'Sophia', 'Malik2', 'Marc', 'AstridM', 'KevinH', 'Nico']

2.b) Indiquer le nom du type de parcours d'arbre binaire réalisé par la fonction membres.

Réponse

Il s'agit d'un parcours préfixe (on traite la racine avant de traiter les sous-arbres à gauche et à droite).

3) Dans cette question, on s'intéresse aux profils des membres (or, argent ou bronze).

3.a) Indiquer les étiquettes des feuilles de l'arbre \(P\).

Réponse

Les feuilles sont : 'FredB', 'Marc', 'KevinH' et 'Nico'

3.b) À partir des propositions suivantes, indiquer le profil des membres dont les pseudonymes sont les étiquettes des feuilles.

  • Réponse A : membre or
  • Réponse B : membre argent
  • Réponse C : membre bronze
  • Réponse D : on ne peut pas savoir
Réponse

Puisqu'il s'agit des feuilles, cela signifie que ces nœuds n'ont pas de successeurs et donc que les membres associés n'ont parrainé personne. La bonne réponse est donc la C : membre bronze.

3.c) Écrire la fonction profil qui prend un arbre binaire non vide en paramètre et renvoie le profil du membre dont le pseudonyme est l'étiquette de la racine de l'arbre sous la forme d'une chaine de caractères : 'or', 'argent' ou 'bronze'. Par exemple, l'appel profil(arbre_p) doit renvoyer 'or'qui correspond au profil du membre 'AnneB', racine de \(P\).

Réponse
profil
1
2
3
4
5
6
7
8
9
def profile(arbre):
    if est_vide(gauche(arbre)):
        # l'énoncé indique que le sous arbre à droite sera vide
        return 'bronze'
    elif est_vide(droite(arbre)):
        # ici le sous arbre à gauche est non vide
        return 'argent'
    else:
        return 'or'

Autre solution, consistant à compter le nombre de sous-arbres non vides qui correspond au nombre de personnes parrainées. On en déduit le profil :

profil version 2
1
2
3
4
5
6
7
8
def profile(arbre):
    les_profiles = ('bronze', 'argent', 'or')
    nb_parraines = 0
    if not est_vide(gauche(arbre)):
        nb_parraines += 1
    if not est_vide(droite(arbre)):
        nb_parraines += 1
    return les_profils[nb_parraines]

4) Afin d'obtenir un tableau dont chaque élément est un tuple contenant le pseudonyme d'un membre et son profil, on propose la fonction membres_profils définie ci-dessous :

membres_profils
1
2
3
4
5
def membres_profils(arbre, liste_membres_profils):
    if not est_vide(arbre):
        liste_membres_profils.append((racine(arbre), profil(A))
        membres_profils(gauche(arbre), liste_membres_profils)
        membres_profils(droite(arbre), liste_membres_profils)

On appelle cette fonction sur un arbre arbre_2 et on obtient ceci :

🐍 Console Python
>>> liste_2 = []
>>> membres_profils(arbre_2, liste_2)
>>> liste_2
[('LeaC', 'or'), ('Ali', 'bronze'), ('Tom45', 'argent'), ('Vero', 'bronze')]

Dessiner un arbre possible pouvant correspondre à l'arbre_2.

Réponse

Comme pour la question 2b, on a à faire à un parcours préfixe donc 'LeaC' est la racine de l'arbre_2. Ensuite à gauche on a 'Ali' qui est une feuille (membre bronze). À droite on tombe sur 'Tom45' qui a parrainé un seul membre : 'Vero'.

arbre 2

5) Chaque année, les membres versent une cotisation en fonction de leur profil.

  • membre or : cotisation de 20 €
  • membre argent : cotisation de 30 €
  • membre bronze : cotisation de 40 €

Écrire une fonction cotisation qui prend un arbre binaire et renvoie le total des cotisations reçues par le club dont arbre modélise les relations de parrainage. On pourra utiliser la fonction membres_profils de la question précédente.

Réponse

On commence par définir un dictionnaire des tarifs de cotisations :

🐍 Script Python
tarifs = {'or': 20, 'argent': 30, 'bronze': 40}
cotisations
1
2
3
4
5
6
7
def cotisations(arbre):
    total = 0
    liste_membres_profils = []
    membres_profils(arbre, liste_membres_profils)
    for _, profil in liste_membres_profils:
        total += tarifs[profil]
    return total

On peut aussi faire sans la fonction membres_profils :

cotisations version 2
1
2
3
4
5
6
7
def cotisations(arbre):
    if est_vide(arbre):
        return 0
    else:
        a_gauche = cotisations(gauche(arbre))
        a_droite = cotisations(droite(arbre))
        return tarifs[profil(a)] + a_gauche + a_droite