Sujet n°29

Sujet original

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

Exercice n°1

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.

class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

Exemples

L’arbre ci-contre sera donc implémenté de la manière suivante :

>>> a = Arbre(1) 
>>> a.fg = Arbre(4)
>>> a.fd = Arbre(0)
>>> a.fd.fd = Arbre(7)

Écrire une fonction récursive taille prenant en paramètre une instance a de la classe Arbre et qui renvoie la taille de l’arbre que cette instance implémente.

Écrire de même une fonction récursive hauteur prenant en paramètre une instance a de la classe Arbre et qui renvoie la hauteur de l’arbre que cette instance implémente.

Si un arbre a un seul nœud, sa taille et sa hauteur sont égales à 1. S’il est vide, sa taille et sa hauteur sont égales à 0.

Tester les deux fonctions sur l’arbre représenté ci-dessous :

Une solution

class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

def taille(a):
    '''
    a - Arbre, un arbre quelconque
    Sortie: int, taille de l'arbre a, c'est-à-dire son nombre de noeuds
    '''
    if a is None:
        return 0
    elif a.fg is None and a.fd is None:
        return 1
    else:
        return 1+taille(a.fg) + taille(a.fd)

def hauteur(a):
    '''
    a - Arbre, un arbre quelconque
    Sortie: int, hauteur de l'arbre a
    '''
    if a is None:
        return 0
    elif a.fg is None and a.fd is None:
        return 1
    else:
        return 1+max(hauteur(a.fg), hauteur(a.fd))


if __name__ == '__main__':
    # Exemples de l'énoncé
    a = Arbre(1)
    a.fg = Arbre(4)
    a.fd = Arbre(0)
    a.fd.fd = Arbre(7)
    print(taille(a) == 4)
    print(hauteur(a) == 3)

    b = Arbre(0)
    b.fg = Arbre(1)
    b.fg.fg = Arbre(3)
    b.fd = Arbre(2)
    b.fd.fd = Arbre(5)
    b.fd.fg = Arbre(4)
    b.fd.fg.fd = Arbre(6)
    print(taille(b) == 7)
    print(hauteur(b) == 4)

Exercice n°2

La méthode insert de la classe list permet d’insérer un élément dans une liste à un indice donné.

Le but de cet exercice est, sans utiliser cette méthode, d’écrire une fonction ajoute réalisant cette insertion en produisant une nouvelle liste.

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.

Cette fonction ajoute prend en paramètres trois variables indice, element et liste et renvoie une liste L dans laquelle les éléments sont ceux de la liste liste avec, en plus, l’élément element à l’indice indice.
On considère que les variables indice et element sont des entiers positifs et que les éléments de liste sont également des entiers positifs.
Les éléments de la liste liste, dont les indices sont supérieurs ou égaux à indice apparaissent décalés vers la droite dans la liste L.
Si indice est supérieur ou égal au nombre d’éléments de la liste liste, l’élément element est ajouté dans L après tous les éléments de la liste liste.

Exemples

>>> ajoute(1, 4, [7, 8, 9]) 
[7, 4, 8, 9] 

>>> ajoute(3, 4, [7, 8, 9]) 
[7, 8, 9, 4] 

>>> ajoute(4, 4, [7, 8, 9]) 
[7, 8, 9, 4] 

Compléter et tester le code ci-dessous :

def ajoute(indice, element, liste): 
    nbre_elts = len(liste) 
    L = [0 for i in range(nbre_elts + 1)] 
    if ...: 
        for i in range(indice): 
            L[i] = ... 
        L[...] = ... 
        for i in range(indice + 1, nbre_elts + 1): 
            L[i] = ... 
    else: 
        for i in range(nbre_elts): 
            L[i] = ... 
        L[...] = ... 
    return L 

Commentaires sur le code original

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

Une solution

def ajoute(indice, element, liste):
    nbre_elts = len(liste)
    L = [0 for i in range(nbre_elts + 1)]
    if indice < nbre_elts:
        for i in range(indice):
            L[i] = liste[i]
        L[indice] = element
        for i in range(indice + 1, nbre_elts + 1):
            L[i] = liste[i-1]
    else:
        for i in range(nbre_elts):
            L[i] = liste[i]
        L[nbre_elts] = element
    return L


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(ajoute(1, 4, [7, 8, 9]) == [7, 4, 8, 9])
    print(ajoute(3, 4, [7, 8, 9]) == [7, 8, 9, 4])
    print(ajoute(4, 4, [7, 8, 9]) == [7, 8, 9, 4])

    # Exemples supplémentaires
    print(ajoute(0, 4, [7, 8, 9]) == [4, 7, 8, 9])
    print(ajoute(5, 4, []) == [4])