Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Discussion: Les Arbres Binaires

  1. #1
    Invité de passage
    Femme Profil pro
    Etudiante
    Inscrit en
    septembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Etudiante

    Informations forums :
    Inscription : septembre 2012
    Messages : 5
    Points : 0
    Points
    0

    Par défaut Les Arbres Binaires

    Bonjour,
    J'ai un exercice dans lequel je dois réaliser une procédure imprimer qui imprimer l'arbre a sous forme préfixé.
    Voici l'énoncé exact :

    imprimer imp a : imprime l'arbre a sous forme préfixée complètement parenthésée en utilisant l'imprimeur imp pour imprimer les étiquettes des noeuds de l'arbre.
    L'arbre vide est imprimé par le couple de parenthèses ().
    de type 'a -> unit) -> 'a t -> unit

    seulement, je ne sais pas de quel type sont les étiquettes de l'arbre.


    J'ai pensé à diverses méthodes mais qui n'ont jamais aboutis.

    Je vous demande alors de l'aide (juste me mettre sur la piste svp) .
    Merci

  2. #2
    Membre émérite
    Avatar de Cacophrene
    Profil pro Phrene Caco
    Inscrit en
    janvier 2009
    Messages
    533
    Détails du profil
    Informations personnelles :
    Nom : Phrene Caco

    Informations forums :
    Inscription : janvier 2009
    Messages : 533
    Points : 951
    Points
    951

    Par défaut

    Bonsoir,

    je ne sais pas de quel type sont les étiquettes de l'arbre.
    On te demande de créer une fonction imp dont on te donne la signature :

    val imp : ('a -> unit) -> 'a t -> unit

    Tu peux en déduire que ta fonction va recevoir deux paramètres en entrée : une fonction de type 'a -> unit qui affiche une valeur de type quelconque 'a (ce type désigne donc les étiquettes de ton arbre binaire) et un arbre binaire, de type 'a t.

    Je te donne la piste suivante :

    type 'a t = Leaf | Node of 'a t * 'a * 'a t

    À toi de voir ce que tu peux en faire pour écrire la fonction imp !

    Cordialement,
    Cacophrène

  3. #3
    Invité de passage
    Femme Profil pro
    Etudiante
    Inscrit en
    septembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Etudiante

    Informations forums :
    Inscription : septembre 2012
    Messages : 5
    Points : 0
    Points
    0

    Par défaut

    Ce que je ne comprends pas c'est quelle est l'argument que doit prendre imp?

    vu que la fonction imprimer doit être de la forme : imprimer imp a , logiquement imp prend a en argument, mais dans ce cas là imp serait de type :
    'a t -> unit, non?
    alors que imp doit être de type 'a -> unit.



    J'ai vraiment du mal........

  4. #4
    Membre Expert Avatar de prgasp77
    Homme Profil pro Yankel Scialom
    Ingénieur en systèmes embarqués
    Inscrit en
    juin 2004
    Messages
    1 083
    Détails du profil
    Informations personnelles :
    Nom : Homme Yankel Scialom
    Âge : 27
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : juin 2004
    Messages : 1 083
    Points : 1 388
    Points
    1 388

    Par défaut

    Il faut comprendre que le but est de diviser en deux le problème. Afficher un arbre est en effet deux problèmes : son parcourt d'une part et l'impression de ses feuilles d'autre part. La fonction imprimer s'occupe de la première partie, et la fonction imp de la seconde : imprimer imp tree parcourt l'arbre tree et pour chacune de ses feuilles leaf appelle imp leaf.

    Donc,
    • imp a pour signature 'a -> unit (imprime une feuille de l'arbre) ;
    • imprimer a pour signature ('a -> unit) -> 'a t -> unit (appelle la fonction donnée en argument pour chacune des feuilles de leaf).


    Pour résumer, appeler imprimer en fournissant la fonction print_int et l'abre Node ( (Leaf 3), 5 (Node (Leaf 0, 42, Leaf 7)) ) sera équivalent à l'appel successif de :
    Code ocaml :
    1
    2
    3
    4
    5
    6
    print_int 5 ;
    print_int 3 ;
    print_int 42 ;
    print_int 0 ;
    print_int 7

    Ça va mieux ?


    Edit : oui j'ai pris une représentation étrange pour mon type d'arbre .

  5. #5
    Invité de passage
    Femme Profil pro
    Etudiante
    Inscrit en
    septembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Etudiante

    Informations forums :
    Inscription : septembre 2012
    Messages : 5
    Points : 0
    Points
    0

    Par défaut

    En fait, ce que je ne comprends pas c'est :
    pour la fonction imp, de dois me servir du Printf, mais de quel type seront les étiquettes? (dois -je mettre printf "%c" ? ou printf "%d"? etc.....)

    (c'est probablement bête comme question, mais j'ai vraiment du mal sur cette question précise )

  6. #6
    Membre Expert Avatar de prgasp77
    Homme Profil pro Yankel Scialom
    Ingénieur en systèmes embarqués
    Inscrit en
    juin 2004
    Messages
    1 083
    Détails du profil
    Informations personnelles :
    Nom : Homme Yankel Scialom
    Âge : 27
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : juin 2004
    Messages : 1 083
    Points : 1 388
    Points
    1 388

    Par défaut

    On ne te demande pas de coder imp, mais imprimer. C'est l'utilisateur de la fonction imprimer qui fournira la bonne fonction imp en fonction du type de l'arbre qu'il veut utiliser.

    Tu dois comprendre que tu fais de la programmation fonctionnelle, les fonctions sont des arguments.

  7. #7
    Membre émérite
    Avatar de Cacophrene
    Profil pro Phrene Caco
    Inscrit en
    janvier 2009
    Messages
    533
    Détails du profil
    Informations personnelles :
    Nom : Phrene Caco

    Informations forums :
    Inscription : janvier 2009
    Messages : 533
    Points : 951
    Points
    951

    Par défaut

    Bonjour,

    Un petit coup de pouce supplémentaire avec le squelette de la fonction imprimer. C'est une illustration de ce que te disais prgasp77 à propos de scinder le problème en deux sous-problèmes parcours/affichage. À toi de remplacer les points de suspension par du code. Courage, tu y es presque !

    Code :
    1
    2
    3
    4
    let rec imprimer imp = function
      | Leaf -> ...
      | Node (left, x, right) -> ...
    Cordialement,
    Cacophrène

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •