Contexte

Les listes chainées sont implémentées à l'aide des classes Node et LinkedList dont les implémentations sont fournies ci-dessous :

class Node:
    """ Represents a Node in a LinkedList data structure. """

    def __init__(self, cargo=None, next=None):
        """
        Creates a new Node object.
        @pre:  -
        @post: A new Node object has been initialised.
            A node can contain a cargo and a reference to another node.
            If none of these are given, the node is initialised with
            empty cargo (None) and no reference (None).
        """
        self.cargo = cargo
        self.next = next

class LinkedList :
    """ Represents a linked list datastructure. """

    def __init__(self):
        """
        Initialises a new LinkedList object.
        @pre:  -
        @post: A new empty LinkedList object has been initialised.
            It has 0 length, contains no nodes and its head refers to None.
        """
        self.length = 0
        self.head = None

    def add_in_order(self, cargo):
        """
        Adds a new Node with the given cargo in the linked list so that it remains sorted.
        @pre:  self is a (possibly empty) LinkedList.
        @post: A new Node object is created with the given cargo.
            This new Node is added to the linked list.
            The length counter has been incremented by 1.
            The linked list is sorted.
        """
        ...

La méthode add_in_order est fournie et prête à l’emploi. Vous pouvez l’utiliser directement dans vos tests et votre code, sans avoir à l’implémenter vous-même. L'implémentation est cependant cachée.

Objectifs

Vous devez implémenter la fonction moyenne_ponderee(notes_etudiant, credits_cours) où :

• notes_etudiant est une instance de LinkedList contenant des tuples (code_cours, note), où

  • code_cours est une chaîne de caractères (comme "LINFO1101") identifiant un cours ;
  • note est un entier compris entre 0 et 20.

• credits_cours est une instance de LinkedList contenant des tuples (code_cours, credits), où

  • code_cours est une chaine de caractères identifiant un cours ;
  • credits est un entier compris entre 1 et 30.

Les deux listes sont triés alphanumériquement en ordre croissant par code_cours et chaque cours apparaît au plus une fois dans chaque liste.

On garantit également que tout cours présent dans notes_etudiant est également présent dans credits_cours. Autrement dit, la liste des cours suivis par l'étudiant est un sous-ensemble de la liste des cours existants.

La fonction moyenne_ponderee(notes_etudiant, credits_cours) doit calculer et retourner la moyenne des notes de l'étudiant, pondérée avec les crédits de chaque cours qu'il a suivi. Si la liste notes_etudiant est vide, alors la fonction moyenne_ponderee doit retourner None.

Plus formellement, si pour un cours \(c\) on définit :

• \(C\) l'ensemble des cours apparaissant dans notes_etudiant,
• \(\text{note}(c)\) la note obtenue par l'étudiant pour ce cours (dans notes_etudiant),
• \(\text{credits}(c)\) le nombre de crédits associés à ce cours (dans credits_cours),

alors la moyenne pondérée des notes de l'étudiant peut être définie comme :

Autrement dit, seuls les cours effectivement suivis par l’étudiant (présents dans notes_etudiant) interviennent dans le calcul de la moyenne.

Exemple

Voici un exemple de comportement attendu :

credits_cours = LinkedList()
credits_cours.add_in_order(("LINFO1101", 5))
credits_cours.add_in_order(("LESPO1118", 5))
credits_cours.add_in_order(("LANGL1181", 2))
credits_cours.add_in_order(("LINFO1311", 5))
credits_cours.add_in_order(("LINFO1111", 7))

# credits_cours = ("LANGL1181", 2) -> ("LESPO1118", 5) -> ("LINFO1101", 5) -> ("LINFO1111", 7) -> ("LINFO1311", 5)

notes_etudiant = LinkedList()
notes_etudiant.add_in_order(("LINFO1101", 15))
notes_etudiant.add_in_order(("LANGL1181", 12))
notes_etudiant.add_in_order(("LINFO1111", 6))

# notes_etudiant = ("LANGL1181", 12) -> ("LINFO1101", 15) -> ("LINFO1111", 6)

print(moyenne_ponderee(notes_etudiant, credits_cours)) # Imprime 10.0714...

# Explication : moyenne_ponderee = (12 x 2 + 15 x 5 + 6 x 7) / (2 + 5 + 7) = 10.0714...