Exercice 1

Dans cet exercice, on considère des arbres binaires de recherche qui sont :

• soit l’arbre vide identifié par None ;
• soit un nœud, contenant une clé et deux sous-arbres gauche et droit et représenté par un triplet (g, v, d) où g et d sont les sous-arbres gauche et droit et v la clé.

flowchart TD
    n1((1)) --> n0((0))
    n1 --> n2((2))
    n2 --> n3((3))

[Figure : schéma de l’arbre binaire de recherche abr1. La racine porte la clé 1 ; son sous-arbre gauche est le nœud de clé 0 (sans enfants) et son sous-arbre droit est le nœud de clé 2, dont le sous-arbre droit est le nœud de clé 3 (sans enfants). L’arbre est légendé abr1.]

Ainsi, l’arbre binaire de recherche abr1 ci-dessus est créé par le code python ci-dessous

n0 = (None, 0, None)
n3 = (None, 3, None)
n2 = (None, 2, n3)
abr1 = (n0, 1, n2)

Écrire une fonction récursive insertion_abr(a, cle) qui prend en paramètres une clé cle et un arbre binaire de recherche a , et qui renvoie un arbre binaire de recherche dans lequel cle a été insérée.

Dans le cas où cle est déjà présente dans a, la fonction renvoie un arbre identique à a.

Résultats à obtenir :

>>> insertion_abr(abr1, 4)
((None,0,None),1,(None,2,(None,3,(None,4,None))))
>>> insertion_abr(abr1, -5)
(((None,-5,None),0,None),1,(None,2,(None,3,None)))
>>> insertion_abr(abr1, 2)
((None,0,None),1,(None,2,(None,3,None)))

Exercice 2

On dispose d’un ensemble d’objets dont on connaît, pour chacun, la masse. On souhaite ranger l’ensemble de ces objets dans des boites identiques de telle manière que la somme des masses des objets contenus dans une boîte ne dépasse pas la capacité c de la boîte. On souhaite utiliser le moins de boîtes possibles pour ranger cet ensemble d’objets.

Pour résoudre ce problème, on utilisera un algorithme glouton consistant à placer chacun des objets dans la première boîte où cela est possible.

Par exemple, pour ranger dans des boîtes de capacité c = 5 un ensemble de trois objets dont les masses sont représentées en Python par la liste [1, 5, 2], on procède de la façon suivante :

• Le premier objet, de masse 1, va dans une première boite.
• Le deuxième objet, de masse 5, ne peut pas aller dans la même boite que le premier objet car cela dépasserait la capacité de la boite. On place donc cet objet dans une deuxième boîte.
• Le troisième objet, de masse 2, va dans la première boîte.

On a donc utilisé deux boîtes de capacité c = 5 pour ranger les 3 objets.

Compléter la fonction Python empaqueter(liste_masses, c) suivante pour qu’elle renvoie le nombre de boîtes de capacité c nécessaires pour empaqueter un ensemble d’objets dont les masses sont contenues dans la liste liste_masses. On supposera que toutes les masses sont inférieures ou égales à c.

def empaqueter(liste_masses, c):
    """Renvoie le nombre minimal de boîtes nécessaires pour
    empaqueter les objets de la liste liste_masses, sachant
    que chaque boîte peut contenir au maximum c kilogrammes"""
    n = len(liste_masses)
    nb_boites = 0
    boites = [ 0 for _ in range(n) ]
    for masse in ...: 
        i = 0
        while i < nb_boites and boites[i] + ... > c: 
            i = i + 1
        if i == nb_boites:
            ...
        boites[i] = ... 
    return ... 

Exemples :

>>> empaqueter([1, 2, 3, 4, 5], 10)
2
>>> empaqueter([1, 2, 3, 4, 5], 5)
4
>>> empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11)
5

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• a est soit None, soit un triplet (g, v, d) où g et d sont eux-mêmes des arbres de cette forme
• 0 <= nombre de nœuds de a <= 10^3
• les clés de a sont des entiers deux à deux distincts et a vérifie la propriété d’arbre binaire de recherche : toute clé de g est strictement inférieure à v, toute clé de d est strictement supérieure à v
• -10^9 <= v <= 10^9 pour toute clé v de a, et -10^9 <= cle <= 10^9
• la hauteur de a ne dépasse pas 100
• cle peut être déjà présente dans a
• la valeur renvoyée est un arbre de la même forme (None ou triplet), comparé par égalité de tuples

Exercice 2

Contraintes :

• liste_masses est une liste d’entiers et 0 <= len(liste_masses) <= 10^3
• 1 <= c <= 10^4
• 1 <= liste_masses[i] <= c : toutes les masses sont inférieures ou égales à c
• l’ordre des masses dans liste_masses fait partie de l’entrée et ne doit pas être modifié
• la valeur attendue est le nombre de boîtes obtenu en plaçant chaque objet, dans l’ordre de la liste, dans la première boîte pouvant l’accueillir ; ce nombre n’est pas toujours le minimum théorique
• la valeur renvoyée est un entier

Corrigé

Exercice 1 - insertion dans un arbre binaire de recherche

L’idée. Dans un arbre binaire de recherche, toutes les clés du sous-arbre gauche sont plus petites que la clé du nœud, et toutes celles du sous-arbre droit sont plus grandes. Pour insérer une clé, il n’y a donc qu’un seul endroit possible : on compare cle à la clé v du nœud courant, on descend à gauche si elle est plus petite, à droite si elle est plus grande, et on recommence. Quand on arrive sur l’arbre vide None, c’est la place de la nouvelle clé : on y crée le nœud (None, cle, None). Si on rencontre cle en chemin, elle est déjà présente et on renvoie l’arbre sans rien changer.

Un petit exemple. Avec abr1 = ((None, 0, None), 1, (None, 2, (None, 3, None))) et cle = 4 : 4 est plus grand que 1, on va à droite ; 4 est plus grand que 2, on va à droite ; 4 est plus grand que 3, on va à droite ; là l’arbre est vide, on crée (None, 4, None).

def insertion_abr(a, cle):
    # Arbre vide : c'est ici que la nouvelle clé prend sa place
    if a is None:
        return (None, cle, None)
    g, v, d = a
    if cle < v:
        return (insertion_abr(g, cle), v, d)
    if cle > v:
        return (g, v, insertion_abr(d, cle))
    # cle == v : la clé est déjà là, on renvoie l'arbre inchangé
    return a

Quelques explications. La fonction ne modifie pas l’arbre reçu : elle en reconstruit un. À chaque appel, on renvoie un triplet dans lequel un seul des deux sous-arbres a été recalculé, l’autre étant recopié tel quel. g, v et d sont simplement les trois morceaux du nœud courant, récupérés d’un coup avec g, v, d = a. Le cas d’arrêt de la récursion est a is None : c’est le seul endroit où un nouveau nœud est créé. Le dernier return a traite le cas cle == v et garantit qu’une clé déjà présente n’est jamais insérée une deuxième fois.

Exercice 2 - empaqueter

L’idée. On range les objets un par un, dans l’ordre de la liste. On retient dans boites la masse déjà placée dans chaque boîte (boites[i] pour la boîte numéro i) et dans nb_boites le nombre de boîtes déjà ouvertes. Pour un objet de masse masse, on parcourt les boîtes ouvertes depuis la première et on s’arrête sur la première où il rentre, c’est-à-dire où boites[i] + masse ne dépasse pas c. Si aucune ne convient, on ouvre une boîte de plus.

Un petit exemple. Pour [1, 5, 2] avec c = 5 : l’objet de masse 1 ouvre la boîte 0, qui contient alors 1 ; l’objet de masse 5 ne rentre pas dans la boîte 0 car 1 + 5 > 5, on ouvre donc la boîte 1 ; l’objet de masse 2 rentre dans la boîte 0 car 1 + 2 <= 5. On a utilisé 2 boîtes.

def empaqueter(liste_masses, c):
    """Renvoie le nombre minimal de boîtes nécessaires pour
    empaqueter les objets de la liste liste_masses, sachant
    que chaque boîte peut contenir au maximum c kilogrammes"""
    n = len(liste_masses)
    nb_boites = 0
    boites = [ 0 for _ in range(n) ]
    for masse in liste_masses:
        i = 0
        # On avance tant que la boîte i est trop pleine pour accueillir l'objet
        while i < nb_boites and boites[i] + masse > c:
            i = i + 1
        # Sortie sans avoir trouvé de boîte : il faut en ouvrir une nouvelle
        if i == nb_boites:
            nb_boites = nb_boites + 1
        boites[i] = boites[i] + masse
    return nb_boites

Quelques explications. La boucle while peut s’arrêter pour deux raisons : soit elle a trouvé une boîte où l’objet rentre, soit elle a dépassé la dernière boîte ouverte et alors i vaut nb_boites. C’est exactement ce que teste le if juste après. Comme boites a été remplie de 0 au départ, la case de la boîte que l’on vient d’ouvrir contient bien 0, et la ligne boites[i] = boites[i] + masse fonctionne aussi bien pour une boîte ancienne que pour une boîte neuve. Il n’y a jamais plus de boîtes que d’objets, donc la liste boites de taille n est toujours assez grande.

Attention. Cet algorithme glouton ne donne pas toujours le nombre de boîtes le plus petit possible. Pour [7, 6, 3, 4, 8, 5, 9, 2] avec c = 11, il renvoie 5 alors qu’un rangement en 4 boîtes existe. C’est bien 5 qui est attendu : le sujet demande la stratégie « première boîte possible », et pas l’optimum théorique.