Aller au contenu

Sujet n°27

Sujet original

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

Exercice n°1

Dans cet exercice, un arbre binaire de caractères est stocké sous la forme d’un dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clef, 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 : arbre est stocké dans le dictionnaire :

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 pourra distinguer les 4 cas où les deux « fils » du nœud sont '', le fils gauche seulement est '', le fils droit seulement est '', aucun des deux fils n’est ''.

Exemple

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

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

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
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__':
    a = {'F':['B', 'G'], 'B':['A', 'D'], 'A':['', ''],
        'D':['C', 'E'], 'C':['', ''], 'E':['', ''],
        'G':['', 'I'], 'I':['', 'H'], 'H':['', '']}

    print(taille(a, 'F'))

    b = {'37':['41', '2'], '41':['', '3'], '3':['5', '23'],
        '2':['7', '11'], '7':['', ''], '11':['19', ''],
        '5':['', ''], '23':['', ''], '19':['', '']}

    print(taille(b, '37'))

Exercice n°2

On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt depuis le début du tableau tous les éléments non rangés et on place en dernière position le plus grand élément.

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 grand élément avec le dernier. Le tableau devient :
    t = [41, 25, 21, 18, 12, 6, 55].

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

  • Et ainsi de suite.

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

1
2
3
4
5
6
7
8
9
def tri_iteratif(tab):
    for k in range(..., 0, -1):
        imax = ...
        for i in range(0, ...):
            if tab[i] > ... :
                imax = i
        if tab[imax] > ... :
            ..., tab[imax] = tab[imax], ...
    return tab
Commentaire sur le code original

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

Compléter le code qui doit donner :

Exemple

>>> tri_iteratif([41, 55, 21, 18, 12, 6, 25])
[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
 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
def tri_iteratif(tab):
    for k in range(len(tab)-1, 0, -1):
        imax = k
        for i in range(0, k):
            if tab[i] > tab[imax] :
                imax = i
        if tab[imax] > tab[k] :
            tab[k], tab[imax] = tab[imax], tab[k]
    return tab



if __name__ == '__main__':
    from random import randint
    t = [41, 55, 21, 18, 12, 6, 25]
    print(t)
    print(tri_iteratif(t) == [6, 12, 18, 21, 25, 41, 55])
    print()

    t = [11, 6, 5, 1, 4, 8, 9, 10, 3]
    print(t)
    print(tri_iteratif(t) == [1, 3, 4, 5, 6, 8, 9, 10, 11])
    print()

    t = [randint(0, 15) for _ in range(8)]
    print(t)
    print(tri_iteratif(t))