2

こんにちはすべて私はclispv2.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 関数名と値名は 2 つの異なる名前空間です。

[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

それはあなたが使っている本当に良いアルゴではありません。逆にして、リストの最後の要素に何度も移動します（両方ともreverseO last（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の横に定数を置くことはあまり「科学的」ではありませんが、時間は線形ですが、すべてのノードに2回アクセスする必要があることを示しています。1回目は長さを計算し、2回目は比較します。リスト。n / 2は、比較する前にリバースを呼び出すことによるものです。

非常に単純なナイーブパリンドローム関数があることに注意してください。

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

しかし、私の反科学的なO（）に同意すると、これはO（2n）になります（リスト全体を調べて逆にすると、2回目にリスト全体を調べて結果を比較します。この関数は、次のように実行されます。最悪の場合は最初のものよりも優れていますが、最良の場合は最初のものの方がパフォーマンスが高くなります。また、Lisp実装では、リストの長さを計算する代わりに保存することも珍しくありません。これにより、最初の関数。

于 2012-05-04T09:17:42.217 に答える
0

(defun 回文( L )

(条件

((等しい L '()) T )

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

(T NIL)

)

)

于 2012-05-04T21:41:34.280 に答える