2

大家好，我正在尝试使用 clisp v2.47 编写一个 lisp 函数，该函数接受一个单词，如果它是回文则返回 true，否则将返回 false。顺便说一句，值得一提的是我是 lisp 新手，所以我没有编写 lisp 代码的经验。

这是我的代码：

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

当我将它粘贴到 clisp 中时它很好，但是当我开始运行它时，我得到了这个我不知道如何修复的错误：

[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]>

任何帮助将不胜感激，因为我真的很急于完成这个程序。

谢谢大家

4

4 回答 4

4

该调用(last ( L ))不计算列表的最后一个元素L。它调用L没有任何参数的函数，期望得到一个列表作为返回值，并计算该列表的最后一个单元格。(car (last L))将计算列表的最后一个元素。

在 Lisp 中，括号不用于对代码语句进行分组。相反，它们表示功能应用程序。

(a b c d)

意思是“调用a带参数的函数b, c, d”。

(a)

意思是“调用一个函数a”。

因此，您的代码没有定义任何名为L. 它使用一个名为 的参数L，但在 Common LISP 中，函数名和值名是两个不同的命名空间。

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

编辑：遵循wvxvw最好的想法，这里有一个更好的代码，它不会过多地遍历列表：

(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)))))
于 2012-05-03T16:24:19.683 回答
3

在评估列表时，您放入列表的第一个元素中的任何内容都会被视为函数。尝试删除一些多余的括号：

(defun palindrome( L )   
    (cond 
        ((equal L '()) T  ) 
        ((equal (car L) (last L)) 
            (palindrome (cdr (reverse (cdr L)))))
        nil))
于 2012-05-03T15:21:20.330 回答
1

这不是你正在使用的一个很好的算法。您将多次反转并转到列表的最后一个元素（两者都reverse具有lastO(n) 速度）。您将调用反向 n/2 次和最后 n/2 次，使整个函数时间为 O(n^2)。下面是一个做同样的算法

(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))))))))

但在 O(2n+n/2) 时间内，这是最坏的情况。我知道，这里在n旁边放一个常数不是很“科学”，但它是为了说明虽然时间是线性的，但您需要访问所有节点两次-第一次计算长度，第二次比较列表。n/2 是在比较之前调用 reverse 。

请注意，有一个非常直接的朴素回文函数：

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

但是如果我们同意我的反科学 O()，那么这个就是 O(2n)（一次我们查看整个列表来反转它，第二次我们查看整个列表来比较结果。这个函数将执行在最坏的情况下比第一个更好，但在最好的情况下，第一个会表现得更好。此外，Lisp 实现存储列表的长度而不是计算它并不少见，这可能会使您的速度降低近一半第一个功能。

于 2012-05-04T09:17:42.217 回答
0

（defun回文（L）

（ 条件

(((等于 L '()) T )

((equal (car L) (car(last L))) (回文 (cdr (reverse (cdr L)))))

(无)

)

)

于 2012-05-04T21:41:34.280 回答