Ep 01

Téléchargement du sujet :

le document

l'algorithme

Issue de : 23-NSI-33

EXERCICE 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.

Par exemple, l’arbre :

est stocké dans

🐍 Script Python

arbre = {
        '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 non vide 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 :

🐍 Script Python

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

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

# Mettre votre code icibksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

arbre = {'F':['B','G'], bksl-nl 'B':['A','D'], bksl-nl 'A':['',''], bksl-nl 'D':['C','E'], bksl-nl 'C':['',''], bksl-nl 'E':['',''], bksl-nl 'G':['','I'], bksl-nl 'I':['','H'], bksl-nl 'H':['','']}bksl-nlbksl-nldef taille(arbre, lettre):bksl-nl if lettre == '':bksl-nl return 0bksl-nl return 1 + taille(arbre, arbre[lettre][0]) + taille(arbre, arbre[lettre][1])bksl-nlbksl-nltaille(arbre, 'F')bksl-nlbksl-nl# Testez votre algorithmebksl-nltry:bksl-nl assert taille(arbre, 'F') == 9bksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

---

---

EXERCICE 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.

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

Exemple :

🐍 Script Python

>>> 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.

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def echange(tab, i, j):bksl-nl '''Echange les éléments d'indice i et j dans le tableau tab.'''bksl-nl temp = ... bksl-nl tab[i] = ... bksl-nl tab[j] = ...bksl-nl bksl-nldef tripy-undselection(tab):bksl-nl '''Trie le tableau tab dans l'ordre croissantbksl-nl par la méthode du tri par sélection.'''bksl-nl N = len(tab)bksl-nl for k in range(...): bksl-nl imin = ... bksl-nl for i in range(..., N): bksl-nl if tab[i] < ...: bksl-nl imin = ibksl-nl echange(tab, ..., ...) bksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def echange(tab, i, j):bksl-nl '''Echange les éléments d'indice i et j dans le tableau tab.'''bksl-nl temp = tab[i] bksl-nl tab[i] = tab[j]bksl-nl tab[j] = tempbksl-nlbksl-nldef tripy-undselection(tab):bksl-nl '''Trie le tableau tab dans l'ordre croissantbksl-nl par la méthode du tri par sélection.'''bksl-nl N = len(tab)bksl-nl for k in range(N):bksl-nl imin = kbksl-nl for i in range(k+1, N):bksl-nl if tab[i] < tab[imin] :bksl-nl imin = ibksl-nl echange(tab, k, imin)bksl-nlbksl-nltab = [41, 55, 21, 18, 12, 6, 25]bksl-nltripy-undselection(tab)bksl-nlbksl-nl# Testez votre algorithmebksl-nltry:bksl-nl assert tab == [6, 12, 18, 21, 25, 41, 55]bksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

---

---