Publicité
+ Répondre à la discussion
Page 1 sur 3 123 DernièreDernière
Affichage des résultats 1 à 20 sur 43
  1. #1
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut [Ocaml] Eliminer les doublons dans une ('a * 'b)list

    Bonsoir,
    j'essaye comme le titre l'indique de supprimer les doublons dans une liste de pairs.
    J'ai essayé sans trop de succés.
    Merci de votre aide.
    Dark3

  2. #2
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    si tu montrais ton code, on essaierait de le corriger... mais on ne va pas te le faire


    l'algo simple serait de cette forme :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    L = liste
    res = Liste vide
    tant que L non vide faire
        a = tete de L
        si a n'appartient pas à queue de L 
        alors ajoute a dans res
        L = queue de L
    fait
    renvoyer res
    bien entendu le traitement doit être récursif avec une filtrage... mais c'est à toi de le coder
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  3. #3
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut

    Bonsoir,
    oui effectivement je n'avais pas mis mon code dsl :
    Code :
    1
    2
    3
    4
    let rec enleve l = match l with
      []->[]
    | (a,b)::(c,d)::l' -> if a=c && b=d then (a,b)::(enleve l') else (a,b)::(c,d)::(enleve l');;
    Dans ce code il manque le fait de tester les elements avec chaque autre pair dans la liste, c'est à dire que si les elements identiques ne sont pas consécutifs, ma fonction ne marche pas.
    Je prefererai avoir une solution fonctionnel.
    Merci de votre aide.
    Dark3

  4. #4
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Citation Envoyé par Dark3
    Je prefererai avoir une solution fonctionnel.

    j'ai fait exprès de ne pas te donner la version fonctionnelle, ce qui aurait été équivalent à te donner le programme déjà coder... traduis toi-même


    nb: on se moque du type de l'élément, ocaml réussira à déterminer l'égalité... donc fait comme si on avait une liste d'éléments d'un type quelconque
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  5. #5
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut

    Je comprend bien l'algo, mais je ne saisis pas comment tester l'appartenance d'un element dans la liste de retour si celle si n'est pas déclaré et n'est créer qu'avec la recursivité (a:enleve l))
    Merci de ton aide en tout cas (c bientot l'exam de caml :/)
    Dark3

  6. #6
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Code :
    1
    2
    3
    4
    5
    6
    7
    let rec appartient e l =
       match l with
          [] -> false
         |a::_ where a=e -> true
         |_::q -> appartient e q
    ;;
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #7
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    étant donné que ce n'est qu'un bloc utile, je te le donne... même si avec un peu de reflexion, tu aurais du y arriver (ou alors tu as de gros soucis à te faire pour ton exam !!!)


    Code :
    1
    2
    3
    4
    5
    6
    7
    let rec appartient e l =
       match l with
          [] -> false
         |a::_ when a=e -> true
         |_::q -> appartient e q
    ;;
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  8. #8
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut

    Non je pense que tu n'as pas compris ce que j'ai voulu dire.
    Cette fonction appartient ne me pose pas de problème.
    Ce que je ne comprend pas c'est comment peut on tester l'appartenance d'un element dans une liste sans définir de liste auxiliaire, et que la liste de retour n'est défini qu'avec la récursivité.
    Ou alors dans ce cas on est obligé de le faire comme celà.
    Pour ma part j'aurai penser à l'utilisation d'un List.map avec une fonction à appliquer bien choisi à chaque element de la liste, mais je manque de pratique avec ce genre de fonctions.
    Dark3

  9. #9
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Code :
    1
    2
    3
    4
    5
    let rec elimine_doublon l =
       match l with
          [] -> []
         |a::q -> if (appartient a q) then elimine_doublon q else a::(elimine_doublon q)
    ;;

    je fais avoir du mal à croire que tu aies cherché...


    maintenant, ai-je glissé une erreur dans le code ? fais-nous la preuve de la fonction... juste pour t'en assurer (et vérifier que tu as compris )
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  10. #10
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut

    Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
    Je ne te demandais pas la solution mais juste un peu d'aide comme ce forum nous le propose quand on a un souci.
    Bref, sans doute un malentendu.
    Dark3

  11. #11
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Citation Envoyé par Dark3
    Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
    sans doute, il est tard et j'ai eu une très mauvaise semaine...



    Citation Envoyé par Dark3
    Je ne te demandais pas la solution mais juste un peu d'aide comme ce forum nous le propose quand on a un souci.

    j'ai bien compris que tu cherchais de l'aide. d'ailleurs, tu avais commencé à coder quelque chose... je t'avais l'algo itératif qui permettait de trouver le résultat (le récursif aurait été une traduction du caml en pseudo-code), je voyais mal comment t'aider plus


    maintenant, reprends cette fonction et fais nous les preuves de terminaison et de correction... ça t'aidera à en cerner les détails (j"attends la réponse dans 1 heure )
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  12. #12
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut

    Et bien on fait pas vraiment ça en cours donc je sais pas vraiment ce que tu attends.
    Pour la terminaison :
    Etant donné les differents matching il est clair que l'on va parcourir toute la liste donné en argument et on arrivera à la liste vide qui renvoi quelque chose.
    Pour la correction je ne sais pas ce que ce terme signifie en algorithmie.
    Dark3

  13. #13
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Citation Envoyé par Dark3
    Pour la terminaison :
    Etant donné les differents matching il est clair que l'on va parcourir toute la liste donné en argument et on arrivera à la liste vide qui renvoi quelque chose.
    pas mal, c'est l'idée... j'aurais préféré que tu dises que :
    1) la longueur de l'argument passé en paramètre lors des appels récursifs est strictement décroissante.
    2) toute suite d'entiers naturels strictement décroissante converge (car strictement monotone et minorée par 0).
    3) la limite de la suite est 0 (à faire)
    4) 0 est le cas de terminaison de la fonction, donc ça termine...

    Citation Envoyé par Dark3
    Pour la correction je ne sais pas ce que ce terme signifie en algorithmie.
    Dark3

    je veux que tu prouves que le résultat renvoyé est bien celui qu'on attend
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  14. #14
    Invité de passage
    Inscrit en
    juin 2007
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 11
    Points : 2
    Points
    2

    Par défaut

    Pour la correction :
    Si la liste est vide on renvoie la liste vide, c'est bien le resultat attendu, sinon :
    On recherche si l'element appartient au reste de la liste si c'est le cas on continue sur le reste de la liste sans rajouter d'élement, ce qui va supprimer le doublon au fur et à mesure sinon on rajouter l'element à la liste de retour.
    Dark3

  15. #15
    Inactif
    Inscrit en
    juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 48

    Informations forums :
    Inscription : juillet 2005
    Messages : 1 958
    Points : 2 205
    Points
    2 205

    Par défaut

    Citation Envoyé par Dark3
    Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
    [...]
    Dark3
    Moi je trouve qu'il fait un excellent travail comme aide.

    Tu veux venir icite pour être assistant ??

  16. #16
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Citation Envoyé par Garulfo
    Moi je trouve qu'il fait un excellent travail comme aide.

    il était tard, et j'étais énervé... donc j'ai répondu un peu vite, et donné la solution au bout de quelques minutes de reflexion. j'aurais du lui en faire baver un peu plus

    Citation Envoyé par Garulfo
    Tu veux venir icite pour être assistant ??
    gni ?
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  17. #17
    alex_pi
    Invité(e)

    Par défaut Petite précision tatillonne

    Citation Envoyé par gorgonite
    Code :
    1
    2
    3
    4
    5
    let rec elimine_doublon l =
       match l with
          [] -> []
         |a::q -> if (appartient a q) then elimine_doublon q else a::(elimine_doublon q)
    ;;
    Si je puis me permettre, cette fonction à le gros désavantage de ne pas être "tail-recursive" (c'est à dire de ne renvoyer directement le résultat de l'appel récursif) ce qui est généralement considéré comme mauvais lorsqu'on explore une structure de taille arbitraire. En effet, on peut se retrouver avec un stack-overflow alors qu'on ne manque pas de mémoire. La version suivante est peut être un tout petit peu plus lente, mais tail recursive :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    let rec contient e = function
      | [] -> false
      | t::q when t = e -> true
      | _::q -> contient e q
    
    let elimine_doublon l = 
      let rec aux acc = function
        | [] -> List.rev acc
        | t::q when contient t acc -> aux acc q
        | t::q -> aux (t::acc) q in
      aux [] l
    (J'appelle contient sur l'accumulateur, car dans le cas où la liste contient effectivement des répétitions, il est plus petit que la liste elle même)

  18. #18
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Citation Envoyé par alex_pi
    Si je puis me permettre, cette fonction à le gros désavantage de ne pas être "tail-recursive" (c'est à dire de ne renvoyer directement le résultat de l'appel récursif) ce qui est généralement considéré comme mauvais lorsqu'on explore une structure de taille arbitraire. En effet, on peut se retrouver avec un stack-overflow alors qu'on ne manque pas de mémoire.

    avec les optimisations d'un compilateur non... suffit qu'elle soit primitive

    l'écriture telle que tu le fais sera en revanche bien plus performant dans la boucle d'interprétation
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  19. #19
    alex_pi
    Invité(e)

    Par défaut

    Citation Envoyé par gorgonite
    avec les optimisations d'un compilateur non... suffit qu'elle soit primitive

    l'écriture telle que tu le fais sera en revanche bien plus performant dans la boucle d'interprétation
    Euh... non Test fait avec
    Code :
    1
    2
    3
    4
    let rec recopie = function
      | [] -> []
      | t::q -> t::(recopie q)
    versus
    Code :
    1
    2
    3
    4
    5
    6
    let rec recopie_tail l = 
      let rec aux acc = function
        | [] -> List.rev acc
        | t::q -> aux (t::acc) q in
        aux [] l
    Pour une liste de 2000000 éléments, la version non tail recursive (compilée avec ocamlopt) lance Fatal error: exception Stack_overflow alors que la version tail recursive passe sans soucis

  20. #20
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 162
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 162
    Points : 18 669
    Points
    18 669

    Par défaut

    Citation Envoyé par alex_pi
    Pour une liste de 2000000 éléments, la version non tail recursive (compilée avec ocamlopt) lance Fatal error: exception Stack_overflow alors que la version tail recursive passe sans soucis


    pas cool... pourtant l'optimisation existe belle et bien, j'avais pensé qu'elle serait déjà dans ocaml
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 3 123 DernièreDernière

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
  •