Aller au contenu

Ep 44

le document

l'algorithme

Issue de : 23-NSI-25⚓

EXERCICE 1⚓

Écrire une fonction enumere qui prend en paramĂštre une liste L et renvoie un dictionnaire d dont les clĂ©s sont les Ă©lĂ©ments de L avec pour valeur associĂ©e la liste des indices de l’élĂ©ment dans la liste L.

Exemple :

🐍 Script Python
>>> enumere([1, 1, 2, 3, 2, 1])
{1: [0, 1, 5], 2: [2, 4], 3: [3]}
RĂ©ponse

Complétez le code ci-dessous

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

Solution

###
def enumere(L):bksl-nl d = {}bksl-nl for i in range(len(L)):bksl-nl if L[i] in d:bksl-nl d[L[i]].append(i)bksl-nl else:bksl-nl d[L[i]] = [i]bksl-nl return dbksl-nlbksl-nltry:bksl-nlbksl-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⚓

Un arbre binaire est implémenté par la classe Arbre donnée ci-dessous.

Les attributs fg et fd prennent pour valeurs des instances de la classe Arbre ou None.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec 
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit

def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre != None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
    return liste

La fonction rĂ©cursive parcours renvoie la liste des Ă©tiquettes des nƓuds de l’arbre implĂ©mentĂ© par l’instance arbre dans l’ordre du parcours en profondeur infixe Ă  partir d’une liste vide passĂ©e en argument.

ComplĂ©ter le code de la fonction insere, prĂ©sentĂ© page suivante, qui prend en argument un arbre binaire de recherche arbre reprĂ©sentĂ© ainsi et une Ă©tiquette cle, non prĂ©sente dans l’arbre, et qui :

  • renvoie une nouvelle feuille d’étiquette cle s’il est vide ;
  • renvoie l’arbre aprĂšs l’avoir modifiĂ© en insĂ©rant cle sinon ;
  • garantit que l’arbre ainsi complĂ©tĂ© soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insĂ©rant successivement des nƓuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche reprĂ©sentĂ© ci-dessous :

image

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche
    représenté par arbre.
    Retourne l'arbre modifié."""
    if arbre == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        if ...: 
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = ... 
        return arbre

Exemple :

🐍 Script Python
>>> a = Arbre(5)
>>> insere(a, 2)
>>> insere(a, 7)
>>> insere(a, 3)
>>> parcours(a, [])
[2, 3, 5, 7]
>>> insere(a, 1)
>>> insere(a, 4)
>>> insere(a, 6)
>>> insere(a, 8)
>>> parcours(a, [])
[1, 2, 3, 4, 5, 6, 7, 8]
RĂ©ponse

Complétez le code ci-dessous

###
class Noeud:bksl-nl """Classe représentant un noeud d'un arbre binaire"""bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette, gauche, droit):bksl-nl """Crée un noeud de valeur etiquette avec bksl-nl gauche et droit comme fils."""bksl-nl self.etiquette = etiquettebksl-nl self.gauche = gauchebksl-nl self.droit = droitbksl-nlbksl-nldef parcours(arbre, liste):bksl-nl """parcours récursivement l'arbre en ajoutant les étiquettesbksl-nl de ses noeuds à la liste passée en argument en ordre infixe."""bksl-nl if arbre != None:bksl-nl parcours(arbre.gauche, liste)bksl-nl liste.append(arbre.etiquette)bksl-nl parcours(arbre.droit, liste)bksl-nl return listebksl-nlbksl-nldef insere(arbre, cle):bksl-nl """insere la cle dans l'arbre binaire de recherchebksl-nl représenté par arbre.bksl-nl Retourne l'arbre modifié."""bksl-nl if arbre == None:bksl-nl return Noeud(cle, None, None) # creation d'une feuillebksl-nl else:bksl-nl if ...: bksl-nl arbre.gauche = insere(arbre.gauche, cle)bksl-nl else:bksl-nl arbre.droit = ... bksl-nl return arbrebksl-nl

Solution

###
class Noeud:bksl-nl """Classe reprĂ©sentant un noeud d'un arbre binaire"""bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette, gauche, droit):bksl-nl """CrĂ©e un noeud de valeur etiquette avec bksl-nl gauche et droit comme fils."""bksl-nl self.etiquette = etiquettebksl-nl self.gauche = gauchebksl-nl self.droit = droitbksl-nlbksl-nldef parcours(arbre, liste):bksl-nl """parcours rĂ©cursivement l'arbre en ajoutant les Ă©tiquettesbksl-nl de ses noeuds Ă  la liste passĂ©e en argument en ordre infixe."""bksl-nl if arbre != None:bksl-nl parcours(arbre.gauche, liste)bksl-nl liste.append(arbre.etiquette)bksl-nl parcours(arbre.droit, liste)bksl-nl return listebksl-nlbksl-nldef insere(arbre, cle):bksl-nl """insere la cle dans l'arbre binaire de recherchebksl-nl reprĂ©sentĂ© par arbre.bksl-nl Retourne l'arbre modifiĂ©."""bksl-nl if arbre == None:bksl-nl return Noeud(cle, None, None) # creation d'une feuillebksl-nl else:bksl-nl if arbre.gauche is not None: bksl-nl arbre.gauche = insere(arbre.gauche, cle)bksl-nl else:bksl-nl arbre.droit = insere(arbre.droit, cle) bksl-nl return arbrebksl-nlbksl-nltry:bksl-nlbksl-nl a = insere(None, 5)bksl-nl a = insere(a, 2)bksl-nl a = insere(a, 7)bksl-nl a = insere(a, 3)bksl-nl assert parcours(a, []) == [5, 2, 7, 3]bksl-nl a = insere(a, 1)bksl-nl a = insere(a, 4)bksl-nl a = insere(a, 6)bksl-nl a = insere(a, 8)bksl-nl assert parcours(a, []) == [5, 2, 7, 3, 1, 4, 6, 8]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-nlbksl-nl