Partage
  • Partager sur Facebook
  • Partager sur Twitter

Exercice et algorithm

    26 novembre 2021 à 17:51:21

    J'allais écrire une connerie ...
    Puisque tu as plusieurs fils, je pensais à un dictionnaire:
    -
    class Noeud:
        def __init__(self, pere=None, fils={}, valeur=None):
            self.pere = pere
            self.fils = fils
            self.valeur = valeur
    On peut savoir le nombre de fils, ajouter ou supprimer un fils, descendre dans l'arbre, etc.
    Pour le dessin, je suppose qu'on devra faire un parcours en largeur.

    En fait, c'est plutôt un parcours en profondeur qui serait souhaitable. On veut savoir la largeur maximum du dessin en terme de nombre de "cellules" à dessiner.
    Au début, on associe la valeur 0 à tous les noeuds de l'arbre.
    On se rend jusqu'aux feuilles (noeud sans fils). on leur associe la valeur 1.
    On doit aditionner les valeurs de tous ses fils à chaque noeud.
    On devrait pouvoir faire remonter jusqqu'à la racine le plus grand nombre d'éléments par niveau.
    Ça devrait pouvoir se faire facilement de façon récursive Et un dictionnaire ne sera pas approprié. Une liste suffira.
    def somme(node):
        return sum(somme(n) for n in node.fils) or 1

    -
    Edité par PierrotLeFou 26 novembre 2021 à 19:29:07

    • Partager sur Facebook
    • Partager sur Twitter

    Le Tout est souvent plus grand que la somme de ses parties.

      27 novembre 2021 à 8:37:33

      J'ai fait l'exercice avec un parcours en profondeur (je pensais au départ le faire en largeur mais je me suis rendu compte que j'avais vite besoin de connaître le nombre de lignes), par contre la partie dessin est un peu prise de tête.

      • Partager sur Facebook
      • Partager sur Twitter
        27 novembre 2021 à 17:37:50

        Le problème est que les sous-arbres n'ont pas forcément tous la même profondeur.
        J'ai prévu un espace pour les feuilles qui ne sont pas au niveau le plus bas.
        Ça ne devrait pas être trop compliqqué si on n'a qu'un caractère associé à chaque noeud ou feuille.
        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

        Exercice et algorithm

        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
        • Editeur
        • Markdown