Discussion :

[kespy13]

actuellement etudiant
je cherche un algorithme pas forcement avec une tres bonne complexité
qui supprime les occurences d'un element dans une liste.
mais il ya quelques inconvenient :
- il n'y pas de relation d'ordre entre les elements de ma liste, je peut tres bien bien avoir comme liste en parametre (a 1 b r 3 5 3 c 1 r)
- ma fonction n'a qu'un seul parametre : une liste et me renvoit une liste
- je ne peut pas utiliser de fonction auxilliaire (calcule de taille, i éme element, ....)


merci bcp

[fearyourself]

Ta fonction doit pouvoir accepter deux paramètres car si tu ne peux pas savoir quel élément enlever, cela risque de rendre la fonction compliquée...

[kespy13]

justement le but et n'avoir qu'un seul parametre, sinon l'algorithme serait "banale", c'est toutes la complexité de l'exercice

[fearyourself]

D'accord, je viens de comprendre, tu veux enlever les répétitions dans une liste. Si c'est le cas et que la complexité n'est pas importante.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Soit L la liste de départ
Soit S une liste vide
Pour chaque élément i de la liste L
   Pour chaque élément j de la liste L
      Si i==j alors
           On n'ajoute pas cet élément à la liste, on sort de cette boucle interne
   Fin Pour
   Si on a parcouru toute la liste, l'élément i est unique
          On ajoute l'élément i à L
   Fin Si
Fin Pour

[kespy13]

le probleme, j'ai oublier de le preciser mais ma fonction doit etre recursive.
je pensez comparer le premier element de ma liste avec tous les autres et supprimer un element identiques;
puis faire la meme choses avec le deuxieme, ainsoi de suites
mais le probleme c'est que cet fonction ne repondrez pas aux autres conditions(plus haut)

[Zenol]

Si il faut la rendre récursive, tu peut faire :
Prendre premier element : comparer a toute la liste et suprimer les doublets
Rapeller la fonction avec la nouvelle liste et en métent le premier element de la liste en dernier.

Bon, entre nous, sans recursivitée c'est beaucoup plus rapide, masi si c'est un exercice...

[Tellmarch]

Si il faut la rendre récursive, tu peut faire :
Bon, entre nous, sans recursivitée c'est beaucoup plus rapide, masi si c'est un exercice...

Euh une liste c'est une structure de donnée naturellement récursive, et tu ne peux pas implémenter ton algo facilement de façon itérative...

Donc non c'est pas plus éfficace en iteratif je pense.


Et ta façon de "récursifier" ton algo est absurde '_'


kespy, t'as pas du tout le droit à définir des fonctions auxiliaires?

[Zenol]

Une liste(Je pense au std::list) n'est pas récursive!
Mais bon, il y a plusieurs type de liste, alors si tu pouvais présiser...

[Trap D]

Si il faut la rendre récursive, tu peut faire :
Bon, entre nous, sans recursivitée c'est beaucoup plus rapide, masi si c'est un exercice...

Euh une liste c'est une structure de donnée naturellement récursive, et tu ne peux pas implémenter ton algo facilement de façon itérative...

Donc non c'est pas plus éfficace en iteratif je pense.


Et ta façon de "récursifier" ton algo est absurde '_'


kespy, t'as pas du tout le droit à définir des fonctions auxiliaires?

Lorsque la récursivité est terminale, il me semble que certains compilateurs "dérécursifient" justement pour transformer en programmes itératifs .
Il faut aussi je pense distinguer entre les langages naturellement récursifs, types LISP, PROLOG et les langages comme C, qui sont plus efficaces en itératif qu'en récursif.
La question se pose donc, en quel langage vas-tu implémenter cet algo ?
[edit] si j'en crois ce que j'ai vu sur un autre thread de ce forum en Scheme donc du récursif absolument [/edit]

[Rafy]

eheheh Même sujet de DM ?
http://www.developpez.net/forums/vie...590753#2590753

[Tellmarch]

Lorsque la récursivité est terminale, il me semble que certains compilateurs "dérécursifient" justement pour transformer en programmes itératifs .

Oui je sais bien, ocaml ou haskell par exemple, mais ça ne correspond pas du tout à ce que fait JC_Master... sa récursification est totalement absurde....

Il faut aussi je pense distinguer entre les langages naturellement récursifs, types LISP, PROLOG et les langages comme C, qui sont plus efficaces en itératif qu'en récursif.
La question se pose donc, en quel langage vas-tu implémenter cet algo ?
[edit] si j'en crois ce que j'ai vu sur un autre thread de ce forum en Scheme donc du récursif absolument [/edit]

oui c'est du scheme, mais de toute façon c'est forcement une structure récursive vu l'énoncé (interdiction d'utiliser une fonction auxiliaire pour accéder au n-iem élement...)

donc JC_Master, oui c'est bien récursif.

[Trap D]

Pour l'exo, as-tu droit au prédicat delete (qui existe en Lisp ?, tout au moins dans le mien), auquel cas ça simplifie pas mal le problème.

[Zenol]

A donc désoler je ne conais pas le scheme, donc je crain ne pas pouvoir t'aider. Mais juste pour savoir, tes listes quand tu les dit récursive, c'est que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
list<element,
  list<truc,
    list<machin,
      list<bidule,
      null>
    >
  >
>

[Tellmarch]

en fait je ne connais pas le c++ donc je ne sais pas ce que sont exactement les std::list, mais en général en algorithique le mot liste est utilisé pour une liste chainée (donc une structure naturellement récursive), par oposition aux tableaux qui se pretent bien à la programmation itérative.

plus de détails : http://fr.wikipedia.org/wiki/Liste

[Zenol]

Ok c'est bien ce que j'ai noter avent. Le premier élément de la liste contien une donnée + un lien vers un autre élément.

[Trap D]

Après pas mal d'essais, j'ai pu le faire en Scheme avec if not null? cons let while set! list append car et cdr.
As-tu droit à ces mot-clés ?
Dans ce cas, tu reconstruis ta liste en concaténant le premier élément de la liste passée en argument avec le retour du rappel de ta fonction à laquelle tu auras passé en argument le résultat d'une boucle locale définie avec un let, la boucle testant une liste intermédiaire intialisée avec le cdr de la liste initiale. La boucle construit, avec set!, une liste secondaire intialisée à (), à laquelle tu ajoutes les car de la liste intermédiaire s'ils sont différents du car de la liste initiale passée en argument de la fonction. Le let renvoie la liste secondaire.
ouf
merci de m'avoir lu jusque là !

[Zenol]

J'ai lut, mais par contre je n'ai aps comprit >_<

[Trap D]

Ça veut dire ça en Scheme, version, DrScheme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (ote_les_occurences l)
  (if  (not (null? l))
   (let ((x (car l)) (y (cdr l)))
      (cons x (ote_les_occurences
                  (let ((z y) (u ()))
                       (while (not (null? z))
                           (if (not(eq? x (car z)))
                               (set! u (append u (list(car z))))
                           )
                           (set! z (cdr z))
                       )
                       u
   )  )       )   )
   ()
) )

Personnellement, je préfère nettement cette version LISP, avec une fonction interne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
(defun ote_les_occurences_2 (l)
  (if  l
   (let ((x (car l)) (y (cdr l)))
      (cons x (ote_les_occurences_2
                  (labels ( (ote_une_occurence_2  (x l) 
                             (if l
                               (if (eq x (car l))
                                   (ote_une_occurence_2  x (cdr l))
                                   (cons (car l) (ote_une_occurence_2  x (cdr l)))
                      )  ) )  )
                      (ote_une_occurence_2  x y))                   
) ) ) )

[Tellmarch]

la deuxieme version est clairement mieux, mais il a pas le droit de définir de version locale apparement >_<
enfin personnellement je trouve cette contrainte absurde.

La premiere version fait appel à append, il n'a meme pas le droit d'utiliser une fonction d'acces au i eme élément, ça serait étonnant que ça soit autorisé je pense....
bon apres je parle pas le scheme donc je peux pas vérifier le premier algo '_'

[Trap D]

Après discussion et échange de messages, on est arrivé à ce résultat en Scheme, avec une fonction externe

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (g l) 
   (if (null? l)
       l
       (cons (car l) (g (test l)))
)   ) 
 
(define (test l)
  (if (null? (cdr l))
      (cdr l)
      (if (eq? (car l) (cadr l))
          (test (cons (car l) (cddr l)))
          (cons (cadr l) (test (cons (car l) (cddr l))))
)  )  )

enfin, je suppose, car je n'ai pas eu de nouvelles...
La fonction test vire les occurences du car de la liste dans le cdr de cette liste.
Le fait de n'avoir qu'un seul arguement à la fonction test n'apporte rien, ce n'est qu'un artifice de calcul.