Scheme : fonction intersection

Scheme : fonction intersection - Divers - Programmation

Marsh Posté le 15-05-2009 à 17:49:25    

Bonjour, je débute le langage scheme et je galère !!!  :pt1cable:  
je n'arrive pas à faire la fonction intersection qui calcule l'intersection de deux ensemble A et B, ainsi que la différence .... quelqu'un pourrait m'aider?
merci d'avance

Reply

Marsh Posté le 15-05-2009 à 17:49:25   

Reply

Marsh Posté le 15-05-2009 à 19:13:23    

Quel est ton problème?


---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 16-05-2009 à 09:14:09    

Quelles sont les fonctions à ta disposition pour écrire l'algo ?
As-tu une idée de la manière de procéder, en dehors de tout langage ?

Reply

Marsh Posté le 16-05-2009 à 11:44:22    

Je connais : car, cdr , cons , cond, null? , list?
Dans un autre langage j'aurais fait une boucle si en comparant les deux ensemble mais la en scheme je comprend pas la logique ...

Message cité 1 fois
Message édité par lisee26 le 16-05-2009 à 11:46:53
Reply

Marsh Posté le 16-05-2009 à 11:47:25    

il faut peut etre utiliser la fonction minimum?

Reply

Marsh Posté le 16-05-2009 à 12:10:26    

lisee26 a écrit :

Je connais : car, cdr , cons , cond, null? , list?


Je te suggère de lire R5RS et de te renseigner sur if (et cond, mais cond ne devrait pas être nécessaire pour ton besoin), eq?, eqv? peuvent suffire mais tu devrais probablement regarder du côté de memv si tu veux te simplifier la vie

lisee26 a écrit :

Dans un autre langage j'aurais fait une boucle si en comparant les deux ensemble mais la en scheme je comprend pas la logique ...


http://mitpress.mit.edu/sicp/full- [...] _sec_1.2.1

 

Accessoirement, si tu apprends le Scheme tu devrais probablement lire le reste de SICP.


Message édité par masklinn le 16-05-2009 à 12:10:47

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 16-05-2009 à 12:28:04    

merci pour tes liens je vais les lire tout de suite !
 
moi j'avais eu comme idée de condenser les deux ensembles avec cond et de les trier mais après je bloque  
 
j'ai oublié de préciser que ce sont des ensembles d'entiers et chaque élément apparait une seule fois dans la lsite

Reply

Marsh Posté le 16-05-2009 à 12:40:22    

lisee26 a écrit :

moi j'avais eu comme idée de condenser les deux ensembles avec cond et de les trier mais après je bloque


Bof, je suggèrerais d'itérer sur le premier et pour chaque élément de regarder s'il est dans le 2e. Ca donne grosso merdo du O(m*n), ce qui me semble correct.

 

S'il y est tu stockes dans le car d'une dotted pair, s'il n'y est pas tu le stockes dans le cdr de ta pair. De cette manière, tu as l'intersection dans le car de ta paire et la différence dans le cdr


Message édité par masklinn le 16-05-2009 à 12:41:03

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 16-05-2009 à 12:47:36    

aie je comprend rien .. je débute vraiment donc pas facile
itérer avec do? Mais en scheme on peut pas ?
 
Pour l'union j'avais fait ça :
 
(define (union A B)
  (cond ((null? A) B)
           ((null? B) A)
            (else (cons (car A) (cons (car B) (union (cdr A) (cdr B)))))))

Reply

Marsh Posté le 16-05-2009 à 13:03:18    

lisee26 a écrit :

itérer avec do? Mais en scheme on peut pas ?


CF le lien vers SICP, en scheme (et dans la majorité des langages fonctionnels) l'itération sur une collection se fait soit via récursion soit en utilisant une HoF (qui planque la récursion)

lisee26 a écrit :


Pour l'union j'avais fait ça :

 

(define (union A B)
  (cond ((null? A) B)
           ((null? B) A)
            (else (cons (car A) (cons (car B) (union (cdr A) (cdr B)))))))


Si a et b ont un élément commun, on se retrouve avec un duplicat dans le résultat. Je doute fort que ça puisse être considéré comme un résultat correct.

 

Je suis désolé de te dire qu'avec un truc pareil, tu aurais pu te simplifier la tache et écrire simplement

Code :
  1. (define union append)


Message édité par masklinn le 16-05-2009 à 13:06:22

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 16-05-2009 à 13:03:18   

Reply

Marsh Posté le 16-05-2009 à 13:06:38    

Bon ben j'

Reply

Marsh Posté le 16-05-2009 à 13:39:42    

lol j'avais oublié append ... la c'est pareil on se retrouve avec un duplicat dans le résultat ?
tu l'ecrirais comment toi l'uinon?

Reply

Marsh Posté le 16-05-2009 à 13:42:44    

lisee26 a écrit :

lol j'avais oublié append ... la c'est pareil on se retrouve avec un duplicat dans le résultat ?


Oui, mais l'ordre est différent (au lieu d'avoir a1, b1, a2, b2, a3, b3, ... append renvoie a1, a2, a3, ..., b1, b2, b3, b4, ...)

lisee26 a écrit :

tu l'ecrirais comment toi l'uinon?


Pour chaque élément de b,
    s'il est dans a, ne rien faire
    s'il n'est pas dans a, le conser à a

 

En récursif, ça donne:

 

union entre a et b
    si b est vide, renvoyer a
    si car b est dans a, renvoyer l'union de a et cdr b
    sinon renvoyer l'union du cons de car b et a et de cdr b

 

et ça a l'avantage d'être tail-rec


Message édité par masklinn le 16-05-2009 à 15:54:33

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed