Sujet n°12

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

Commentaire sur le sujet original

Exceptionnellement, le fichier joint au sujet comporte un code à compléter reproduit ci-dessous :

class ABR:
    def __init__(self, g0, v0, d0):
        self.gauche = g0
        self.cle = v0
        self.droit = d0

    def __repr__(self):
        if self is None:
            return ''
        else:
            return '(' + (self.gauche).__repr__() + ',' + str(self.cle) + ',' +(self.droit).__repr__() + ')'

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


def ajoute(cle, a):
    pass

Pour télécharger l'original du fichier à compléter, cliquer ici.

On considère la classe ABR, dont le constructeur est le suivant :

def __init__(self, g0, v0, d0):
    self.gauche = g0
    self.cle = v0
    self.droit = d0

Exemple

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

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

Dans tout le code, None correspondra à un arbre vide.

La classe ABR dispose aussi d’une méthode de représentation, qui affiche entre parenthèses le contenu du sous arbre gauche, puis la clé de l’arbre, et enfin le contenu du sous arbre droit. Elle s’utilise en console de la manière suivante :

>>> abr1
((None,0,None),1,(None,2,(None,3,(None,4,None))))

Écrire une fonction récursive ajoute(cle,a) 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é.

Exemples

>>> a = ajoute(4, abr1)
>>> a
((None,0,None),1,(None,2,(None,3,(None,4,None))))

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

>>> ajoute(2, abr1)
((None,0,None),1,(None,2,(None,3,None)))

Une solution

class ABR:
    def __init__(self, g0, v0, d0):
        self.gauche = g0
        self.cle = v0
        self.droit = d0

    def __repr__(self):
        if self is None:
            return ''
        else:
            return '(' + (self.gauche).__repr__() + ',' + str(self.cle) + ',' +(self.droit).__repr__() + ')'

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


def ajoute(cle, a):
    if a == None:
        return ABR(None, cle, None)
    elif cle == a.cle:
        return a
    elif cle < a.cle:
        return ABR(ajoute(cle, a.gauche), a.cle, a.droit)
    else:
        return ABR(a.gauche, a.cle, ajoute(cle, a.droit))


if __name__ == '__main__':
    # Exemples de l'énoncé
    a = ajoute(4, abr1)
    print(str(a) == "((None,0,None),1,(None,2,(None,3,(None,4,None))))" )

    a = ajoute(-5, abr1)
    print(str(a) == "(((None,-5,None),0,None),1,(None,2,(None,3,None)))" )

    a = ajoute(2, abr1)
    print(str(a) == "((None,0,None),1,(None,2,(None,3,None)))" )


    # Exemples supplémentaires
    a = ajoute(0.5, abr1)
    print(str(a) == "((None,0,(None,0.5,None)),1,(None,2,(None,3,None)))")

    a = ajoute(1.5, abr1)
    print(str(a) == "((None,0,None),1,((None,1.5,None),2,(None,3,None)))")

    a = ajoute(2.5, abr1)
    print(str(a) == "((None,0,None),1,(None,2,((None,2.5,None),3,None)))")

Exercice n°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.

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 empaquete un ensemble d’objets dont les masses sont contenues dans la liste liste_masses.

Commentaires

Ici, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.

def empaqueter(liste_masses, c):
    n = len(liste_masses)
    nb_boites = 0
    boites = [0]*n
    for masse in ... :
        i=0
        while i <= nb_boites and boites[i] + ... > c:
            i = i + 1
        if i == nb_boites + 1:
            ...
        boites[i] = ...
    return ...

Commentaire sur le code original

Pour télécharger l'original du fichier à compléter, cliquer ici.

Exemple

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

Une solution

def empaqueter(liste_masses, c):
    n = len(liste_masses)
    nb_boites = 0
    boites = [0]*n
    for masse in liste_masses :
        i=0
        while i <= nb_boites and boites[i] + masse > c:
            i = i + 1
        if i == nb_boites + 1:
            nb_boites = nb_boites + 1
        boites[i] = boites[i] + masse
    return nb_boites+1




if __name__ == '__main__':
    # Exemple de l'énoncé
    print(empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11) == 5)

    # Exemples supplémentaires
    print(empaqueter([7], 11) == 1)
    print(empaqueter([1 ,1, 1, 1, 1, 1, 1, 11], 11) == 2)
    print(empaqueter([1, 2, 3, 4, 5, 6, 7], 8) == 5)