Exercice 1

EXERCICE 1 (10 points)

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud représenté par un triplet (g, x, d) où x est l’étiquette du nœud et g et d sont les sous-arbres gauche et droit.

On souhaite écrire une fonction parcours_largeur qui prend en paramètre un arbre binaire et qui renvoie la liste des étiquettes des nœuds de l’arbre parcourus en largeur.

Exemples :

>>> arbre = ( ( (None, 1, None), 2, (None, 3, None) ),
              4,
              ( (None, 5, None), 6, (None, 7, None) ) )
>>> parcours_largeur(arbre)
[4, 2, 6, 1, 3, 5, 7]

Exercice 2

EXERCICE 2 (10 points)

On considère un tableau non vide de nombre entiers, positifs ou négatifs, et on souhaite déterminer la plus grande somme possible de ses éléments consécutifs.

Par exemple, dans le tableau [1, -2, 3, 10, -4, 7, 2, -5], la plus grande somme est 18 obtenue en additionnant les éléments 3, 10, -4, 7, 2.

Pour cela, on va résoudre le problème par programmation dynamique. Si on note tab le tableau considéré et i un indice dans ce tableau, on se ramène à un problème plus simple : déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i.

Si on connait la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i-1, on peut déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i :

• soit on obtient une plus grande somme en ajoutant tab[i] à cette somme précédente ;
• soit on commence une nouvelle somme à partir de tab[i].

Compléter la fonction somme_max ci-dessous qui réalise cet algorithme.

def somme_max(tab):
    n = len(tab)
    sommes_max = [0]*n
    sommes_max[0] = tab[0]
    # on calcule la plus grande somme se terminant en i
    for i in range(1,n):
        if ... + ... > ...: 
            sommes_max[i] = ... 
        else:
            sommes_max[i] = ... 
    # on en déduit la plus grande somme de celles-ci
    maximum = 0
    for i in range(1, n):
        if ... > ...: 
            maximum = i

    return sommes_max[...] 

Exemples :

>>> somme_max([1, 2, 3, 4, 5])
15
>> somme_max([1, 2, -3, 4, 5])
9
>>> somme_max([1, 2, -2, 4, 5])
10
>>> somme_max([1, -2, 3, 10, -4, 7, 2, -5])
18

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

Exercice 1

Contraintes :

• arbre est soit None, soit un triplet (g, x, d) dont g et d sont eux-mêmes des arbres binaires
• l’arbre comporte au plus 1000 nœuds
• les étiquettes x sont des entiers avec -10^9 <= x <= 10^9, non nécessairement distincts
• l’arbre vide est possible : parcours_largeur(None) renvoie []
• les étiquettes sont renvoyées niveau par niveau, de la racine vers les feuilles, et de gauche à droite dans chaque niveau

Exercice 2

Contraintes :

• tab est une liste d’entiers non vide : 1 <= len(tab) <= 10^4
• -10^4 <= tab[i] <= 10^4
• la somme porte sur au moins un élément : les sous-tableaux vides ne sont pas considérés
• si tous les éléments de tab sont négatifs, la réponse est le plus grand élément du tableau (par exemple -2 pour [-5, -2, -9])

Correction

Exercice 1 - parcours en largeur d’un arbre binaire

L’idée. Parcourir en largeur, c’est visiter l’arbre niveau par niveau : d’abord la racine, puis ses deux enfants, puis les enfants de ceux-ci. Pour tenir cet ordre, on utilise une file d’attente : on y met la racine, puis on répète toujours le même geste. On sort le nœud entré le premier, on note son étiquette, et on ajoute ses deux sous-arbres à la fin de la file. Comme on ajoute à la fin et qu’on retire au début, les nœuds ressortent exactement dans l’ordre des niveaux.

Un petit exemple. Avec l’arbre de l’énoncé, la file contient d’abord [4]. On sort 4, on ajoute ses deux sous-arbres : la file devient [2, 6]. On sort 2, on ajoute 1 et 3 : la file devient [6, 1, 3]. Et ainsi de suite, ce qui donne bien [4, 2, 6, 1, 3, 5, 7].

def parcours_largeur(arbre):
    if arbre is None:
        return []
    etiquettes = []
    file = [arbre]
    while len(file) > 0:
        # On retire toujours le nœud entré le premier : c'est ce qui donne
        # l'ordre niveau par niveau, de gauche à droite
        gauche, x, droit = file.pop(0)
        etiquettes.append(x)
        if gauche is not None:
            file.append(gauche)
        if droit is not None:
            file.append(droit)
    return etiquettes

Explications. file contient des arbres non vides qui restent à traiter, et etiquettes la réponse en construction. file.pop(0) retire et renvoie le premier élément de la liste : c’est ce qui fait de la liste une file, et non une pile. La ligne gauche, x, droit = ... ouvre le triplet en une fois et donne un nom à chacune de ses trois parties. On teste is not None avant d’ajouter un sous-arbre pour ne jamais mettre un arbre vide dans la file, sinon pop(0) essaierait plus tard d’ouvrir None en triplet. Enfin, le if du début traite le cas de l’arbre vide, qui doit renvoyer la liste vide. La boucle s’arrête quand la file est vide, c’est-à-dire quand tous les nœuds ont été visités : chaque nœud entre une fois et sort une fois.

Exercice 2 - la plus grande somme d’éléments consécutifs

L’idée. On ne cherche pas directement la réponse, on remplit d’abord le tableau sommes_max, où sommes_max[i] est la plus grande somme d’éléments consécutifs qui se termine à l’indice i. Pour la calculer, on n’a que deux possibilités, celles que l’énoncé décrit : soit on prolonge la meilleure somme qui se terminait en i-1 en lui ajoutant tab[i], soit cette somme précédente ne nous aide pas et on repart de zéro avec tab[i] seul. On garde la plus grande des deux. La réponse est ensuite la plus grande valeur de tout ce tableau.

Un petit exemple. Pour [1, 2, -2, 4, 5], on obtient sommes_max = [1, 3, 1, 5, 10] : en indice 2 la somme retombe à 1 car 3 + (-2) = 1, puis elle remonte. La plus grande valeur est 10, en dernière position.

def somme_max(tab):
    n = len(tab)
    sommes_max = [0]*n
    sommes_max[0] = tab[0]
    # on calcule la plus grande somme se terminant en i
    for i in range(1,n):
        if sommes_max[i-1] + tab[i] > tab[i]:
            sommes_max[i] = sommes_max[i-1] + tab[i]
        else:
            sommes_max[i] = tab[i]
    # on en déduit la plus grande somme de celles-ci
    maximum = 0
    for i in range(1, n):
        if sommes_max[i] > sommes_max[maximum]:
            maximum = i

    return sommes_max[maximum]

Explications. La première boucle applique le choix décrit plus haut. Le test sommes_max[i-1] + tab[i] > tab[i] revient à se demander si la somme précédente est positive : si elle l’est, la prolonger fait mieux ; sinon on recommence à tab[i].

Attention au piège de la seconde boucle : maximum n’est pas une somme, c’est un indice. C’est visible dans le squelette de l’énoncé, qui écrit maximum = i puis return sommes_max[...]. On le fait donc partir de 0, c’est-à-dire de la case sommes_max[0], et on compare sommes_max[i] à sommes_max[maximum]. Si on l’avait traité comme une somme initialisée à 0, la fonction renverrait 0 sur un tableau entièrement négatif, ce qui est faux : la somme doit porter sur au moins un élément, donc pour [-5, -2, -9] la réponse attendue est -2, le plus grand élément. Avec la version ci-dessus, sommes_max vaut [-5, -2, -11] et on renvoie bien -2.

Les deux boucles partent de l’indice 1 parce que la case 0 est déjà remplie et sert de point de départ. Un tableau d’un seul élément fonctionne donc aussi : les deux boucles ne tournent pas et on renvoie sommes_max[0], soit tab[0].