Aller au contenu

Ep 24

le document

l'algorithme

Issue de : aucun⚓

EXERCICE 1⚓

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.

Exemple :

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

RĂ©ponse

Complétez le code ci-dessous

###
# Mettez votre code icibksl-nlbksl-nl

Solution

###
def parcourspy-undlargeur(abr):bksl-nl chemin = []bksl-nl file = [abr]bksl-nl bksl-nl while len(file) != 0:bksl-nl noeud = file.pop(0)bksl-nl chemin.append(noeud[1])bksl-nl bksl-nl if noeud[0] is not None:bksl-nl file.append(noeud[0])bksl-nl if noeud[2] is not None:bksl-nl file.append(noeud[2])bksl-nl return cheminbksl-nltry:bksl-nl arbre = ( ( (None, 1, None), 2, (None, 3, None) ), 4, ( (None, 5, None), 6, (None, 7, None) ) )bksl-nl assert parcourspy-undlargeur(arbre) == [4, 2, 6, 1, 3, 5, 7]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 considÚre un tableau 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.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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[...]

Exemple :

🐍 Script Python
>>> 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
RĂ©ponse

Complétez le code ci-dessous

###
def sommepy-undmax(tab):bksl-nl n = len(tab)bksl-nl sommespy-undmax = [0]py-strnbksl-nl sommespy-undmax[0] = tab[0]bksl-nl # on calcule la plus grande somme se terminant en ibksl-nl for i in range(1,n):bksl-nl if ... + ... > ...: bksl-nl sommespy-undmax[i] = ... bksl-nl else:bksl-nl sommespy-undmax[i] = ... bksl-nl # on en déduit la plus grande somme de celles-cibksl-nl maximum = 0bksl-nl for i in range(1, n):bksl-nl if ... > ...: bksl-nl maximum = ibksl-nlbksl-nl return sommespy-undmax[...]bksl-nl

Solution

###
def sommepy-undmax(tab):bksl-nl n = len(tab)bksl-nl sommespy-undmax = [0]py-strnbksl-nl sommespy-undmax[0] = tab[0]bksl-nl # on calcule la plus grande somme se terminant en ibksl-nl for i in range(1,n):bksl-nl if tab[i-1] + tab[i] >= sommespy-undmax[i]: bksl-nl sommespy-undmax[i] = sommespy-undmax[i-1] + tab[i] bksl-nl else:bksl-nl sommespy-undmax[i] = 0bksl-nl # on en dĂ©duit la plus grande somme de celles-cibksl-nl maximum = 0bksl-nl for i in range(1, n):bksl-nl if sommespy-undmax[i] > maximum :bksl-nl maximum = ibksl-nl return sommespy-undmax[maximum]bksl-nlbksl-nltry:bksl-nl assert sommepy-undmax([1, 2, 3, 4, 5]) == 15bksl-nl assert sommepy-undmax([1, 2, -3, 4, 5]) == 9bksl-nl assert sommepy-undmax([1, 2, -2, 4, 5]) == 10bksl-nl assert sommepy-undmax([1, -2, 3, 10, -4, 7, 2, -5]) == 18bksl-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-nlbksl-nl