Ep 23

Issue de : 23-NSI-12⚓︎

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é.

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

🐍 Script Python

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 l’arbre a inchangé.

Résultats à obtenir :

🐍 Script Python

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

Réponse

Complétez le code ci-dessous

###

# Mettre votre code icibksl-nlbksl-nl

Solution

###

def insertionpy-undabr(a, cle):bksl-nl if a == None:bksl-nl return (None, cle, None)bksl-nl else:bksl-nl valeur = a[1]bksl-nl if cle > valeur:bksl-nl return (a[0], valeur, insertionpy-undabr(a[2], cle))bksl-nl elif cle < valeur:bksl-nl return (insertionpy-undabr(a[0], cle), valeur, a[2])bksl-nl return abksl-nlbksl-nln0 = (None,0, None)bksl-nln3 = (None,3, None)bksl-nln2 = (None,2, n3)bksl-nlabr1 = (n0, 1, n2)bksl-nlbksl-nltry:bksl-nl assert insertionpy-undabr(abr1, 4) == ((None,0,None),1,(None,2,(None,3,(None,4,None))))bksl-nl assert insertionpy-undabr(abr1, -5) == (((None,-5,None),0,None),1,(None,2,(None,3,None)))bksl-nl assert insertionpy-undabr(abr1, 2) == ((None,0,None),1,(None,2,(None,3,None)))bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

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.

🐍 Script Python
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 ...

🐍 Script Python

>>> 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

Réponse

Complétez le code ci-dessous

###

def empaqueter(listepy-undmasses, c):bksl-nl n = len(listepy-undmasses)bksl-nl nbpy-undboites = 0bksl-nl boites = [0]py-strnbksl-nl for masse in ... :bksl-nl i = 0bksl-nl while i <= nbpy-undboites and boites[i] + ... > C:bksl-nl i = i + 1bksl-nl if i == nbpy-undboites + 1:bksl-nl ...bksl-nl boites[i] = ...bksl-nl return ...bksl-nlbksl-nl

Solution

###

def empaqueter(listepy-undmasses, c):bksl-nl """Renvoie le nombre minimal de boîtes nécessaires pourbksl-nl empaqueter les objets de la liste listepy-undmasses, sachantbksl-nl que chaque boîte peut contenir au maximum c kilogrammes"""bksl-nl n = len(listepy-undmasses)bksl-nl nbpy-undboites = 0bksl-nl boites = [ 0 for py-und in range(n) ]bksl-nl for masse in listepy-undmasses :bksl-nl i = 0bksl-nl while i < nbpy-undboites and boites[i] + masse > c: bksl-nl i = i + 1bksl-nl if i == nbpy-undboites:bksl-nl nbpy-undboites = nbpy-undboites + 1bksl-nl boites[i] = boites[i] + massebksl-nl return nbpy-undboitesbksl-nlbksl-nltry:bksl-nl assert empaqueter([1, 2, 3, 4, 5], 10) == 2bksl-nl assert empaqueter([1, 2, 3, 4, 5], 5) == 4bksl-nl assert empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11) == 5bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl