Correspondance de Schröder (2)

Suite de l'exercice précédent

Dans l'exercice précédent, on a construit une fonction qui renvoie un chemin pour un arbre de Schröder donné.

Ici, il s'agit de la fonction réciproque, ce qui établit une correspondance entre arbre de Schröder et chemin de Schröder.

L'objectif de l'exercice est de construire une fonction telle que chemin_vers_arbre(chemin) renvoie la description d'un arbre de Schröder du chemin passé en paramètre avec sa description.

Exemples

• donne

🐍 Console Python

>>> chemin_vers_arbre([(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)])
[[[], []], [], []]

• donne

🐍 Console Python

>>> chemin_vers_arbre([(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)])
[[], [[], []], []]

• donne

🐍 Console Python

>>> chemin_vers_arbre([(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)])
[[], [[], [[], []], [], [], []], []]

###

Lancer# testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]bksl-nl) == [[[], []], [], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]bksl-nl) == [[], [[], []], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]bksl-nl) == [[], [[], [[], []], [], [], []], []]bksl-nlbksl-nl# autres testsbksl-nlbksl-nldef arbrepy-undverspy-undchemin(arbre):bksl-nl def parcourspy-undprefixe(arbre, chemin):bksl-nl ipy-undpremier = 0bksl-nl ipy-unddernier = len(arbre) - 1bksl-nl for i, souspy-undarbre in enumerate(arbre):bksl-nl if i == ipy-undpremier:bksl-nl chemin.append((1, 1))bksl-nl elif i == ipy-unddernier:bksl-nl chemin.append((1, -1))bksl-nl else:bksl-nl chemin.append((2, 0))bksl-nl parcourspy-undprefixe(souspy-undarbre, chemin)bksl-nl bksl-nl chemin = []bksl-nl parcourspy-undprefixe(arbre, chemin)bksl-nl return cheminbksl-nlbksl-nldef gen(n):bksl-nl if n == 1:bksl-nl yield []bksl-nl returnbksl-nl for i in range(1, n - 1):bksl-nl for gauche in gen(i):bksl-nl for droite in gen(n - i):bksl-nl arbre = [gauche]bksl-nl arbre.extend(droite)bksl-nl yield arbrebksl-nl for droite in gen(n - i - 1):bksl-nl arbre = [gauche, droite]bksl-nl yield arbrebksl-nlbksl-nlfor n in range(15):bksl-nl for arbre in gen(n):bksl-nl chemin = arbrepy-undverspy-undchemin(arbre)bksl-nl assert cheminpy-undverspy-undarbre(chemin) == arbre, str(arbre)bksl-nlbksl-nl Valider ∞/∞ TéléchargerTéléverser RechargerSauvegarder

def cheminpy-undverspy-undarbre(chemin):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]bksl-nl) == [[[], []], [], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]bksl-nl) == [[], [[], []], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]bksl-nl) == [[], [[], [[], []], [], [], []], []]bksl-nlbksl-nlbksl-nldef cheminpy-undverspy-undarbre(chemin):bksl-nl arbre = []bksl-nl noeud = arbrebksl-nl pile = []bksl-nl for dx, dy in chemin:bksl-nl if dy == +1:bksl-nl pile.append(noeud)bksl-nl else:bksl-nl noeud = pile[-1]bksl-nl if dy == -1:bksl-nl pile.pop()bksl-nl noeud.append([])bksl-nl noeud = noeud[-1]bksl-nl return arbrebksl-nlbksl-nl# testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (1, 1), (1, -1), (2, 0), (1, -1)]bksl-nl) == [[[], []], [], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (2, 0), (1, 1), (1, -1), (1, -1)]bksl-nl) == [[], [[], []], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre(bksl-nl [(1, 1), (2, 0), (1, 1), (2, 0), (1, 1), (1, -1), (2, 0), (2, 0), (1, -1), (1, -1)]bksl-nl) == [[], [[], [[], []], [], [], []], []]bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl

A

Z

Indice 1

On pourra créer une fonction telle que ajout_feuille_droite(arbre, niveau) ajoute une feuille à arbre totalement à droite, à la profondeur niveau.

Indice 2

On pourra utiliser une pile qui recense les ouvertures de niveau.

Indice 3

Cet exercice n'est pas simple du tout. Bon courage !!!