Sujet n°33

Sujet original

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

Exercice n°1

Un arbre binaire de caractères est stocké sous la forme d’un dictionnaire où les clés sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clé, la liste des caractères des fils gauche et droit du nœud.

Commentaires

Dans cet énoncé, 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

L'arbre : est stocké dans :

a = {'F':['B', 'G'], 'B':['A', 'D'], 'A':['', ''],
     'D':['C', 'E'], 'C':['', ''], 'E':['', ''],
     'G':['', 'I'], 'I':['', 'H'], 'H':['', '']}

Écrire une fonction récursive taille prenant en paramètres un arbre binaire arbre sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de l’arbre, et qui renvoie la taille de l’arbre à savoir le nombre total de nœuds.

On observe que, par exemple, arbre[lettre][0], respectivement arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement droit, de l’arbre arbre de sommet lettre.

Exemple

Avec l'arbre a précédent, on obtient :

>>> taille(a, 'F')
9

Une solution

def taille(arbre, lettre):
    """
    arbre - dict, dictionnaire représentant un arbre binaire dont les nœuds
            sont des caractères
    lettre - str, un caractère
    Sortie: int - taille (nombre de noeuds) de l'arbre
    """
    if arbre[lettre] == ['', '']:
        return 1
    elif arbre[lettre][0] == '':
        return 1 + taille(arbre, arbre[lettre][1])
    elif arbre[lettre][1] == '':
        return 1 + taille(arbre, arbre[lettre][0])
    else:
        return 1 + taille(arbre, arbre[lettre][0]) + taille(arbre, arbre[lettre][1])



if __name__ == '__main__':
    # Exemple de l'énoncé
    a = {'F':['B', 'G'], 'B':['A', 'D'], 'A':['', ''],
        'D':['C', 'E'], 'C':['', ''], 'E':['', ''],
        'G':['', 'I'], 'I':['', 'H'], 'H':['', '']}
    print(taille(a, 'F') == 9)

    # Exemples supplémentaires
    b = {'37':['41', '2'], '41':['', '3'], '3':['5', '23'],
        '2':['7', '11'], '7':['', ''], '11':['19', ''],
        '5':['', ''], '23':['', ''], '19':['', '']}
    print(taille(b, '37') == 9)

Exercice n°2

On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt le sous- tableau des éléments non rangés et on place le plus petit élément en première position de ce sous-tableau.

Exemple avec le tableau t = [41, 55, 21, 18, 12, 6, 25].

Étape 1 : on parcourt tous les éléments du tableau, on permute le plus petit élément avec le premier. Le tableau devient :
t = [6, 55, 21, 18, 12, 41, 25].

Étape 2 : on parcourt tous les éléments sauf le premier, on permute le plus petit élément trouvé avec le second. Le tableau devient :
t = [6, 12, 21, 18, 55, 41, 25].

Et ainsi de suite.

Le code de la fonction tri_selection qui implémente cet algorithme est donné ci-dessous :

def tri_selection(tab): 
    N = len(tab) 
    for k in range(...): 
        imin = ... 
        for i in range(... , N): 
            if tab[i] < ... : 
                imin = i 
        ... , tab[imin] = tab[imin] , ...

Commentaire sur le code original

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

Compléter le code de cette fonction de façon à obtenir :

Exemple

>>> liste = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(liste)
>>> liste
[6, 12, 18, 21, 25, 41, 55]

On rappelle que l’instruction :

a, b = b, a

échange les contenus de a et de b.

Une réponse

def tri_selection(tab):
    N = len(tab)
    for k in range(N):
        imin = k
        for i in range(k, N):
            if tab[i] < tab[imin] :
                imin = i
        tab[k], tab[imin] = tab[imin], tab[k]


if __name__ == '__main__':
    # Exemple de l'énoncé
    liste = [41, 55, 21, 18, 12, 6, 25]
    tri_selection(liste)
    print(liste == [6, 12, 18, 21, 25, 41, 55])

    # Exemples supplémentaires
    t = [11, 6, 5, 1, 4, 8, 9, 10, 3]
    tri_selection(t)
    print(t == [1, 3, 4, 5, 6, 8, 9, 10, 11])

    t = [5, 4, 3, 2, 1]
    tri_selection(t)
    print(t == [1, 2, 3, 4, 5])