Discussion :

[jahol]

Bonjour Tout le monde
Je suis confronté à un problème concernant la double récursion sur une liste.

Je dois créer une fonction qui renvoie la dernière occurence d'une lettre qu'on recherche suivie du reste de la liste.
For example:

(function 'z '((a z)c d))
(Z)


(function 'x '((a (x x)) x c x d e))
(x d e)

La logique de mon développement est la suivante.
Je regarde si l'élément recherché figure dans (last liste), et si c'est le cas je renvoie la bonne réponse;

Mais si c pas le cas que fais je?
Comment parcourir la liste dans l'autre sens(Existe t'il une fonction qui renvoie previous d'un élément d'une liste, ou je dois la créer)?

Voilà j'espère avoir été clair. Je pense que je dois utiliser la double récursion pour résoudre ce problème, mais je suis toujours dans le brouillard.

Merci de votre aide

[Garulfo]

Bonjour Tout le monde[...]

Salut,

Bon avant tout, il y a une balise code à utiliser pour présenter du code.
Ensuite, ton problème est d'ordre algorithmique et non de l'ordre de la mise en pratique en lisp. Car visiblement, tu n'as pas trouvé la réponse.

Je regarde si l'élément recherché figure dans (last liste), et si c'est le cas je renvoie la bonne réponse;

Pas exactement: tu regardes s'il y a une réponse dans la suite de la liste. Pas juste si l'élément y est. Mais il te manque des morceaux (cf. après).

Mais si c pas le cas que fais je?
Comment parcourir la liste dans l'autre sens(Existe t'il une fonction qui renvoie previous d'un élément d'une liste, ou je dois la créer)?

C'est là ton erreur: ta fonction ne commence pas en plein milieu de la liste mais au début.

Il manque un morceau dans l'étape qui tu avais trouvé. Notamment tu sembles ignorer complètement la cellule de tête de ta liste. Comment espères-tu trouver quoique ce soit ?

Il faut donc que tu te demandes quoi faire, en fonction de la cellule de tête. Si elle contient la valeur recherché, que fais-tu ?
Et sinon, que fais-tu ?

Là tu as deux cas exhaustif. Dans le « que fais-tu ? » tu utiliseras la queue de ta liste.

Réfléchis à ça, et reviens nous voir en cas de besoin.

[jack-ft]

Bonjour Tout le monde
Je suis confronté à un problème concernant la double récursion sur une liste.

Je dois créer une fonction qui renvoie la dernière occurence d'une lettre qu'on recherche suivie du reste de la liste.
For example:

Code :

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

1
2
3
4
5
6
(function 'z '((a z)c d))
(Z)
 
 
(function 'x '((a (x x)) x c x d e))
(x d e)

La logique de mon développement est la suivante.
Je regarde si l'élément recherché figure dans (last liste), et si c'est le cas je renvoie la bonne réponse;

Mais si c pas le cas que fais je?
Comment parcourir la liste dans l'autre sens(Existe t'il une fonction qui renvoie previous d'un élément d'une liste, ou je dois la créer)?

Voilà j'espère avoir été clair. Je pense que je dois utiliser la double récursion pour résoudre ce problème, mais je suis toujours dans le brouillard.

Merci de votre aide

Bonjour,

est-ce que tu peux expliciter la logique (ou les spécifications de la fonction)?

Pourquoi est-ce que (x d e) est plus que (x x) la dernière occurrence de x dans ((a (x x)) x c x d e)?
Car on pourrait dire que (x x) est plus en queue, car de longueur 2, que (x d e) qui est de longueur 3 !

Tes exemples semblent indiquer que la "liste" à explorer est en fait plus un arbre qu'une liste. (pour moi, une liste est plutôt une séquence d'éléments (tous plus ou moins du même type), alors qu'un arbre est plutôt un groupe de noeuds, branches et feuilles raccordés ensemble).

Du coup, tu peux t'interroger sur la manière de parcourir cet arbre.


Sinon, une manière "simple" de résoudre un problème par récurrence est la suivante:

imagine que tu possèdes déjà une fonction "foo" qui soit capable de trouver la dernière occurrence d'un élément dans un arbre.
Comment pourrais-tu créer une nouvelle fonction "bar" pour trouver la dernière occurrence d'un élément dans un arbre en te servant de "foo", mais évidemment sans la triviale implémentation:

Code :

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

(defun bar (x arbre) (foo x arbre))

Bonne continuation

)jack(

[jahol]

Salut Garulfo et jack-t et Merci.

J'ai essayé de pousser un tout p'tit peu la réflexion avec votre aide.
J'utilise bien une liste (qui peut etre représentée sous forme d'arbre binaire !).

@Jack-t la spécifications de la fonction est de trouver la dernière occurence d'un élément recherché dans une liste ainsi que le reste de la liste.


J'ai une solution qui (je reconnais) n'est pas optimale:
Je regarde si l'élément recherché est présent en début de liste, si c'est le cas je vérifie sa présence dans le reste de la liste.
Que fais je?
- Si l'élement recherché est trouvé et n'est pas présent dans le reste de la liste , alors je construis la liste finale(résultat).
- Si ce dernier est présent , je rappelle la fonction.

Etant donné que c'est la dernière occurence qui m'interesse, je commence par executer le reste de la liste. Si je n'ai aucun résultat ,j'execute le début de la liste.

Solution non optimale parce qu'il y a une partie du code qui est executée deux fois.

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
16
17
18
19
20
21
 
(defun f1 (x l)
                   (cond 
                      ((endp l) '())
                      ((atom (first l))
                       (if (eq x (first l))
                           (if (member x (rest l))
                               (f1 x (rest l))
                               (cons x (rest l))
                               )
                           (f1 x (rest l))))
                    ((eq (f1 x (rest l)) nil) (f1 x (first l)))
                    (t (f1 x (rest l)))))
 
(defun F2 (x l)
  (let ((rep (f1 x l)))
  (if (eq rep nil) 
      l
      rep)
    )
  )

[dividee]

Vu les exemples du premier post et le code du précédent, il me semble plutôt que la spécification serait:
Renvoyer le plus petit sous-arbre d'un arbre binaire (l) contenant la dernière occurrence d'un atome donné (x) dans un parcours ordonné de cet arbre (ou l'arbre complet si l'atome n'y figure pas (cf. fonction f2)).

Si c'est bien ça, il me semble que le test "member x (rest l)" est non seulement inutile, mais incorrect, car il ne trouverait pas les occurrences de x dans les sous-arbres de gauches de (rest l).

Etant moi-même débutant en LISP, je propose ceci, mais je ne sais pas si cette utilisation assez idiomatique de AND et OR est conseillée en pratique:

Code :

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

1
2
3
4
5
6
7
8
9
(defun f1 (x l)
  (and l
       (or (f1 x (cdr l))
	   (if (atom (car l))
	       (if (eql x (car l)) l)
	       (f1 x (car l))))))
 
(defun f2 (x l)
  (or (f1 x l) l))

[jack-ft]

Salut Garulfo et jack-t et Merci.

J'ai essayé de pousser un tout p'tit peu la réflexion avec votre aide.
J'utilise bien une liste (qui peut etre représentée sous forme d'arbre binaire !).

@Jack-t la spécifications de la fonction est de trouver la dernière occurence d'un élément recherché dans une liste ainsi que le reste de la liste.

Bonjour,

si la spécification est bien de trouver la dernière occurrence d'un élément recherché dans une liste (et non un arbre) ainsi que le reste de la liste,
alors la réponse est vraiment simple:

Code :

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

1
2
3
 
(defun f1 (x l)
  (member x l)

Easy, isn't it?

J'ai une solution qui (je reconnais) n'est pas optimale:
Je regarde si l'élément recherché est présent en début de liste, si c'est le cas je vérifie sa présence dans le reste de la liste.
Que fais je?
- Si l'élement recherché est trouvé et n'est pas présent dans le reste de la liste , alors je construis la liste finale(résultat).
- Si ce dernier est présent , je rappelle la fonction.

Etant donné que c'est la dernière occurence qui m'interesse, je commence par executer le reste de la liste. Si je n'ai aucun résultat ,j'execute le début de la liste.

Je crois que ce serait vraiment plus simple si tu essayais de "penser" et t'exprimer avec un arbre (qui a dit "je préfère un crayon"?).

Code :

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

1
2
3
4
5
Un arbre binaire est 
    ou bien une feuille 
    ou bien un noeud (ou racine) avec 
           un arbre gauche 
        et un arbre droit.

Parfois l'arbre binaire peut être simplifié et ne contient pas vraiment de racine.

Solution non optimale parce qu'il y a une partie du code qui est executée deux fois.

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
16
17
18
19
20
21
 
(defun f1 (x l)
                   (cond 
                      ((endp l) '())
                      ((atom (first l))
                       (if (eq x (first l))
                           (if (member x (rest l))
                               (f1 x (rest l))
                               (cons x (rest l))
                               )
                           (f1 x (rest l))))
                    ((eq (f1 x (rest l)) nil) (f1 x (first l)))
                    (t (f1 x (rest l)))))
 
(defun F2 (x l)
  (let ((rep (f1 x l)))
  (if (eq rep nil) 
      l
      rep)
    )
  )

Pourquoi veux-tu retourner l si f1 ne trouve rien?

Bizarre, cette peur du vide...

et je suis d'accord avec dividee (voir plus loin).

Vu les exemples du premier post et le code du précédent, il me semble plutôt que la spécification serait:
Renvoyer le plus petit sous-arbre d'un arbre binaire (l) contenant la dernière occurrence d'un atome donné (x) dans un parcours ordonné de cet arbre (ou l'arbre complet si l'atome n'y figure pas (cf. fonction f2)).

Ah!!!! OUI!

Je préfère!

encore que:
- j'aimerais savoir ce que tu entends par "le plus petit". S'il y a une occurrence quelque part dans le car et une autre dans le cdr, comment définis-tu le plus petit?
- j'aimerais savoir de quel parcours ordonné il s'agit (j'en connais plusieurs (notamment les 6 classiques: GRD, DRG, RGD, RDG, GDR, DGR (j'ai d'ailleurs un peu de mal à en imaginer d'autres...)))
- je préfèrerais retourner nil plutôt que l'arbre complet si l'atome n'y figure pas (comme fait la fonction "member") sinon on ne distingue pas bien (f2 'x '(x y)) de (f2 'z '(x y)).

Si c'est bien ça, il me semble que le test "member x (rest l)" est non seulement inutile, mais incorrect, car il ne trouverait pas les occurrences de x dans les sous-arbres de gauches de (rest l).

Tout à fait exact, mon cher Watson!

Etant moi-même débutant en LISP, je propose ceci, mais je ne sais pas si cette utilisation assez idiomatique de AND et OR est conseillée en pratique:

Code :

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

1
2
3
4
5
6
7
8
9
(defun f1 (x l)
  (and l
       (or (f1 x (cdr l))
	   (if (atom (car l))
	       (if (eql x (car l)) l)
	       (f1 x (car l))))))
 
(defun f2 (x l)
  (or (f1 x l) l))

C'est beaucoup mieux et l'usage de "or" dans "f1" me convient tout à fait.

L'usage du "and" me convient moins bien. Dans ce cas, je prèfére "cond" "when" "unless" ou "if".

Mais, à mon humble avis, on peut faire encore un petit peu mieux et un peu plus simple...

As-tu essayé ceci:

Code :

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

(f1 'x '(a . b))

Et ceci:

Code :

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

1
2
(let ((x '(a)))
   (f1 x (list x)))

Et que disent les specs pour ceci:

Code :

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

(f1 'x 'x)

et ceci:

Code :

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

(f1 'x '(a . x))

Encore un petit effort...

)jack(

[dividee]

Bonjour jack-ft,

Oui je me suis embrouillé avec la définition d'un arbre. Comme je suis fainéant je vais essayer de changer la spec plutôt que le code
J'avais d'abord pensé à un arbre n-aire, mais comme j'avais un peu de mal à formuler ce que devait être la valeur de retour, je suis passé à un arbre binaire, et j'ai perdu quelques plumes au passage.
En fait, je pensais à l'encodage d'un arbre n-aire en arbre binaire, et à sa représentation sous forme de cons cell, telle qu'indiquée ici.
Pour le parcours, il n'y a que deux ordres possibles: GD ou DG, vu que la racine ne contient pas d'info. J'aurais du préciser qu'il s'agissait de la dernière occurrence dans un parcours GD (ou de façon équivalente, de la première occurrence dans un parcours DG).

Donc la spec devient:

"Rechercher la première occurrence d'un atome donné dans le parcours droite-gauche d'un arbre n-aire de hauteur >=1 donné, et retourner un nouvel arbre n-aire composé d'une racine ayant pour fils l'atome trouvé et ses frères droits (ou NIL si l'atome n'est pas trouvé)."

Du coup:

Code :

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

(f1 'x '(a . b))

et

Code :

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

(f1 'x '(a . x))

sortent de la spec car ne correspondent pas à la représentation d'un arbre n-aire.

Code :

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

1
2
(let ((x '(a)))
   (f1 x (list x)))

Celle-là sortait déjà précédemment de la spec car x n'est pas un atome

Code :

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

(f1 'x 'x)

cf. hauteur >=1 dans la spec (oui je sais c'est petit).

Et voilà, maintenant ce n'est plus le code qui est faux mais l'appelant qui ne respecte pas les préconditions

[Garulfo]

[...]
si la spécification est bien de trouver la dernière occurrence d'un élément recherché dans une liste (et non un arbre) ainsi que le reste de la liste,
alors la réponse est vraiment simple:

Code :

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

1
2
3
 
(defun f1 (x l)
  (member x l)

Easy, isn't it?

Pas vraiment, car tu oublies que si un prof pose cette question, c'est qu'il veut voir le code faisant ça

On apprends à coder les fonctions pour les comprendre et comprendre les principes. Après on utilise celle qui existe (et on évite de les recoder pour rien).

Mais d'après dividee, il semble que la solution soit plutôt une forme de member pour un arbre et non une liste effectivement.

J'interviendrais bien. Mais il me semble que Jack-ft est bien assez locace et plus de blahblah pourrait t'embrouiller