Aller au contenu

Ep 29

▶ TĂ©lĂ©charger le sujet en pdf.

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

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

image

L’arbre ci-dessus sera donc implĂ©mentĂ© de la maniĂšre suivante :

🐍 Script Python
    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 :

image

RĂ©ponse

Complétez le code ci-dessous

###
# Mettez votre code icibksl-nlbksl-nlclass Arbre:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette):bksl-nl self.v = etiquettebksl-nl self.fg = Nonebksl-nl self.fd = Nonebksl-nlbksl-nl

Solution

###
class Arbre:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette):bksl-nl self.v = etiquettebksl-nl self.fg = Nonebksl-nl self.fd = Nonebksl-nl bksl-nldef taille(a):bksl-nl if a is None:bksl-nl return 0bksl-nl else:bksl-nl return 1 + taille(a.fg) + taille(a.fd)bksl-nlbksl-nldef hauteur(a):bksl-nl if a is None:bksl-nl return 0bksl-nl else:bksl-nl return 1 + max(hauteur(a.fg), hauteur(a.fd))bksl-nlbksl-nla = Arbre(0)bksl-nla.fg = Arbre(1)bksl-nla.fd = Arbre(2)bksl-nla.fg.fg = Arbre(3)bksl-nla.fd.fg = Arbre(4)bksl-nla.fd.fd = Arbre(5)bksl-nla.fd.fg.fd = Arbre(6)bksl-nlbksl-nltaille(a)bksl-nlhauteur(a)bksl-nlbksl-nl

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

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.

Exemple :

🐍 Script Python
    >>> 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]

RĂ©ponse

Complétez le code ci-dessous

###
def ajoute(indice, element, liste):bksl-nl nbrepy-undelts = len(liste)bksl-nl L = [0 for i in range(nbrepy-undelts + 1)]bksl-nl if ...:bksl-nl for i in range(indice):bksl-nl L[i] = ...bksl-nl L[...] = ...bksl-nl for i in range(indice + 1, nbrepy-undelts + 1):bksl-nl L[i] = ...bksl-nl else:bksl-nl for i in range(nbrepy-undelts):bksl-nl L[i] = ...bksl-nl L[...] = ...bksl-nl return Lbksl-nlbksl-nl

Solution

###
def ajoute(indice, element, liste):bksl-nl nbrepy-undelts = len(liste)bksl-nl L = [0 for i in range(nbrepy-undelts + 1)]bksl-nl if indice < nbrepy-undelts:bksl-nl for i in range(indice):bksl-nl L[i] = liste[i]bksl-nl L[indice] = elementbksl-nl for i in range(indice + 1, nbrepy-undelts + 1):bksl-nl L[i] = liste[i-1]bksl-nl else:bksl-nl for i in range(nbrepy-undelts):bksl-nl L[i] = liste[i]bksl-nl L[nbrepy-undelts] = element bksl-nl return Lbksl-nlbksl-nl