difficultés avec petit programme lisp pour palindrome

Question

Salut tout J'essaye d'écrire une fonction de lisp en utilisant clisp v2.47 qui prend un mot et retourne vrai si c'est un palindrome sinon il retournera faux. En passant, ce qui vaut la peine d'être mentionné, c'est que je suis nouveau à lisp, donc je n'ai pas d'expérience dans l'écriture de code lisp.

Voici mon code:

(defun palindrome(L) 
    (cond 
     ((equal L '()) T )  
     ((equal (car (L)) (last (L))) 
      (palindrome (cdr (reverse (cdr (L)))))) 
     (t nil))) 

Quand je le coller dans clisp il est bien, mais quand je viens pour l'exécuter que je reçois cette erreur que je ne sais pas comment résoudre:

[2]> (setq M '(bob)) 
(BOB) 

[3]> (palindrome M) 

*** - EVAL: undefined function L 
The following restarts are available: 
USE-VALUE  :R1  Input a value to be used instead of (FDEFINITION 'L). 
RETRY   :R2  Retry 
STORE-VALUE :R3  Input a new value for (FDEFINITION 'L). 
ABORT   :R4  Abort main loop 
Break 1 [4]> 

Toute aide serait très appréciée car je suis vraiment pressé de finir ce programme.

Merci à tous

Answer 1

Tout ce que vous mettez dans le premier élément d'une liste est traitée en fonction lorsque la liste est évaluée. Essayez de supprimer certains excès parens:

(defun palindrome(L) 
    (cond 
     ((equal L '()) T ) 
     ((equal (car L) (last L)) 
      (palindrome (cdr (reverse (cdr L))))) 
     nil)) 

Answer 2

L'appel (last (L)) ne calcule pas le dernier élément de la liste L. Il appelle la fonction nommée L sans aucun argument, s'attend à obtenir une liste en tant que valeur renvoyée, et calcule la dernière cellule de cette liste. (car (last L)) va calculer le dernier élément d'une liste. En Lisp, les parenthèses ne sont pas pour grouper vos instructions de code. Ils signifient une application fonctionnelle à la place.

(a b c d) 

moyens, "appeler une fonction a avec des arguments b, c, d".

(a) 

signifie "appeler une fonction a". Ainsi, votre code ne définit aucune fonction nommée L

Il utilise un paramètre nommé L, mais dans Common LISP, les noms de fonction et les noms de valeur sont deux espaces de noms différents.

[11]> 
(defun palindrome(L) 
    (cond 
     ((null L) T ) 
     ((equal (car L) (car (last L))) 
      (palindrome (cdr (reverse (cdr L))))))) 
PALINDROME 
[12]> (palindrome '(bob)) 
T 

modifier: Après sur la plus belle idée de wvxvw, voici un meilleur code pour elle, qui ne traverse pas la liste tant:

(defun palindrome (x) 
    (do ((x x (cdr x)) 
     (y x (cddr y)) 
     (z() (cons (car x) z))) 
     ((null (cdr y)) 
     (equal z (if y (cdr x) x))))) 

Answer 3

Ce n'est pas vraiment un bon algo que vous utilisez. Vous allez inverser et aller au dernier élément de la liste trop de fois (les deux reverse et last ont la vitesse O (n)). Vous appellerez inverser n/2 fois et durer n/2 fois, rendant le temps de fonction global O (n^2). Ci-dessous un algo qui fait la même

(defun palindrome-p (x) 
    (let ((half-length (floor (/ (length x) 2)))) 
    (do ((i x (cdr x)) 
     (j 0 (1+ j))) 
     (nil) 
     (when (= j half-length) 
     (labels ((compare (head tail) 
        (cond 
        ((or (null head) (null tail)) t) 
        ((not (equal (car head) (car tail))) nil) 
        (t (compare (cdr head) (cdr tail)))))) 
      (return (compare x (reverse i)))))))) 

mais en O (2n + n/2) le temps comme il est le pire des cas. Je sais, il n'est pas très "scientifique" de mettre une constante à côté de n ici, mais c'est pour illustrer que si le temps est linéaire, vous devrez visiter tous les nœuds deux fois - la première fois pour calculer la longueur listes. le n/2 est d'appel inverse avant de comparer.

Notez qu'il existe une fonction de palindrome naïve très straight-forward:

(defun naive-palindrome-p (x) 
    (equal x (reverse x))) 

Mais si nous sommes d'accord sur mon O() anti-scientifique, alors celui-ci est O (2n) (une fois que nous regardons à travers la liste entière pour l'inverser, la deuxième fois que nous regardons toute la liste pour comparer les résultats.Cette fonction sera plus performante que la première dans le pire des cas, mais la première fonctionnera mieux dans le meilleur des cas.En outre, il n'est pas rare pour que les implémentations Lisp stockent la longueur de la liste au lieu de la calculer, ce qui peut vous donner presque la moitié de la réduction de vitesse dans la première fonction

Answer 4

(defun palindrome (L)

(cond

((égal L «()) T)

((égal (voiture L) (voiture (dernière L))) (palindrome (CDR (inverse (cdr l)))))

(T NIL)

)

)