Aller au contenu

Ep 41

le document

l'algorithme

Issue de : 23-NSI-29⚓

EXERCICE 1⚓

Un arbre binaire est soit vide, reprĂ©sentĂ© en Python par la valeur None, soit un nƓud, contenant une Ă©tiquette et deux sous-arbres gauche et droit et reprĂ©sentĂ© par une instance de la classe Noeud donnĂ©e ci-dessous.

🐍 Script Python
1
2
3
4
5
class Noeud:
    def __init__(self, etiquette, gauche, droit):
        self.v = etiquette
        self.gauche = gauche
    self.droit = droit

image

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

🐍 Script Python
1
2
3
a = Noeud(1, Noeud(4, None, None),
             Noeud(0, None,
                      Noeud(7, None, None)))

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

On considùre que la hauteur d’un arbre vide est -1 et la taille d’un arbre vide est 0.

🐍 Script Python
>>> hauteur(a)
2
>>> taille(a)
4
>>> hauteur(None)
-1
>>> taille(None)
0
>>> hauteur(Noeud(1, None, None))
0
>>> taille(Noeud(1, None, None))
1
RĂ©ponse

Complétez le code ci-dessous

###
# Mettez votre code icibksl-nlclass Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette, gauche, droit):bksl-nl self.v = etiquettebksl-nl self.gauche = gauchebksl-nl self.droit = droitbksl-nlbksl-nla = Noeud(1, Noeud(4, None, None),bksl-nl Noeud(0, None,bksl-nl Noeud(7, None, None)))bksl-nl

Solution

###
class Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette, gauche, droit):bksl-nl self.v = etiquettebksl-nl self.gauche = gauchebksl-nl self.droit = droitbksl-nlbksl-nldef taille(a):bksl-nl if a is None:bksl-nl return 0bksl-nl else:bksl-nl return 1 + taille(a.gauche) + taille(a.droit)bksl-nlbksl-nldef hauteur(a):bksl-nl if a is None:bksl-nl return -1bksl-nl else:bksl-nl return 1 + max(hauteur(a.gauche), hauteur(a.droit))bksl-nlbksl-nla = Noeud(1, Noeud(4, None, None),bksl-nl Noeud(0, None,bksl-nl Noeud(7, None, None)))bksl-nlbksl-nltry:bksl-nl assert hauteur(a) == 2bksl-nl assert taille(a) == 4bksl-nl assert hauteur(None) == -1bksl-nl assert taille(None) == 0bksl-nl assert hauteur(Noeud(1, None, None)) == 0bksl-nl assert taille(Noeud(1, None, None)) == 1bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl

EXERCICE 2⚓

On rappelle que les tableaux sont représentés par des listes en Python du type list.

Le but de cet exercice est d’écrire une fonction ajoute qui prend en paramĂštres trois arguments indice, element et tab et renvoie un tableau tab_ins dans lequel les Ă©lĂ©ments sont ceux du tableau tab 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 tab sont également des entiers.

En réalisant cette insertion, Les éléments du tableau tab dont les indices sont supérieurs ou égaux à indice apparaissent décalés vers la droite dans le tableau tab_ins.

Si indice est Ă©gal au nombre d’élĂ©ments du tableau tab, l’élĂ©ment element est ajoutĂ© dans tab_ins aprĂšs tous les Ă©lĂ©ments du tableau tab.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def ajoute(indice, element, tab):
    '''Renvoie un nouveau tableau obtenu en insérant
    element Ă  l'indice indice dans le tableau tab.'''
    nbre_elts = len(tab)
    tab_ins = [0] * (nbre_elts + 1)
    for i in range(indice):
        tab_ins[i] = ... 
    tab_ins[...] = ... 
    for i in range(indice + 1, nbre_elts + 1):
        tab_ins[i] = ... 
    return tab_ins

Exemple :

🐍 Script Python
>>> ajoute(1, 4, [7, 8, 9])
[7, 4, 8, 9]
>>> ajoute(3, 4, [7, 8, 9])
[7, 8, 9, 4]
>>> ajoute(0, 4, [7, 8, 9])
[4, 7, 8, 9]

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-nltry:bksl-nl assert ajoute(1, 4, [7, 8, 9]) == [7, 4, 8, 9]bksl-nl assert ajoute(3, 4, [7, 8, 9]) == [7, 8, 9, 4]bksl-nl assert ajoute(0, 4, [7, 8, 9]) == [4, 7, 8, 9]bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl