Aller au contenu

Sujet n°25

Sujet original

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

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

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.

Exemple

>>>  enumere([1, 1, 2, 3, 2, 1]) 
{1: [0, 1, 5], 2: [2, 4], 3: [3]}
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def enumere(L):
    """
    L - list
    Sortie: dict, dictionnaire qui, à chaque élément de L,
            associe le tableau des indice où trouver cet élément dans L
    """
    d = dict()
    for i in range(len(L)):
        if L[i] in d.keys():
            d[L[i]].append(i)
        else:
            d[L[i]] = [i]
    return d


if __name__ == '__main__':
    # Exemple de l'énoncé
    print(enumere([1, 1, 2, 3, 2, 1]) == {1: [0, 1, 5], 2: [2, 4], 3: [3]})

    # Exemples supplémentaires
    print(enumere([1, 1, 0, 0, 0, 1, 1]) == {0: [2, 3, 4], 1: [0, 1, 5, 6]})
    print(enumere([0, 1]) == {0: [0], 1: [1]})
    print(enumere([1, 0]) == {0: [1], 1: [0]})

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Arbre: 
    def __init__(self, etiquette): 
        self.v = etiquette 
        self.fg = None 
        self.fd = None 

def parcours(arbre, liste): 
    if arbre != None: 
        parcours(arbre.fg, liste) 
        liste.append(arbre.v) 
        parcours(arbre.fd, 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 qui insère un nœud d’étiquette cle en feuille de l’arbre implémenté par l’instance arbre selon la spécification indiquée et de façon 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 :

arbre

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def insere(arbre, cle): 
    """ arbre est une instance de la classe Arbre qui implémente 
        un arbre binaire de recherche. 
    """ 
    if ...: 
        if ...: 
            insere(arbre.fg, cle) 
        else: 
            arbre.fg = Arbre(cle) 
    else: 
        if ...: 
            insere(arbre.fd, cle) 
        else: 
            arbre.fd = Arbre(cle)
Commentaire sur le code original

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

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

def parcours(arbre, liste):
    if arbre != None:
        parcours(arbre.fg, liste)
        liste.append(arbre.v)
        parcours(arbre.fd, liste)
    return liste

def insere(arbre, cle):
    """ arbre est une instance de la classe Arbre qui implémente
        un arbre binaire de recherche.
    """
    if cle < arbre.v:
        if arbre.fg is not None:
            insere(arbre.fg, cle)
        else:
            arbre.fg = Arbre(cle)
    else:
        if arbre.fd is not None:
            insere(arbre.fd, cle)
        else:
            arbre.fd = Arbre(cle)




if __name__ == '__main__':
    # Exemple de l'énoncé
    a = Arbre(5)
    a.fg = Arbre(2)
    a.fg.fd = Arbre(3)
    a.fd = Arbre(7)
    insere(a, 1)
    insere(a, 4)
    insere(a, 6)
    insere(a, 8)
    print(parcours(a, []) == [1, 2, 3, 4, 5, 6, 7, 8])

    # Exemple supplémentaire
    a = Arbre(8)
    a.fg = Arbre(2)
    a.fg.fd = Arbre(6)
    a.fd = Arbre(9)
    for i in range(4, 15, 3):
        insere(a, i)
    print(parcours(a, []) == [2, 4, 6, 7, 8, 9, 10, 13])