3

LISP の問題を解決しようとしていますが、この問題に何日も悩まされています。

"wheres-waldo と呼ばれる関数を書いてください。この関数は、Lisp オブジェクト (つまり、cons から構築されたデータ構造) を引数として取り、存在する場合は、このオブジェクトからシンボル waldo を抽出する Lisp 式を返します"

例えば、

例: (wheres-waldo '(エマーソン・ラルフ・ウォルド)) = 

OUTPUT: (FIRST (REST (REST '(EMERSON RALPH WALDO))))

例: (wheres-waldo '(メンター (ラルフ・ワルド・エマーソン) (ヘンリー・デビッド・ソロー))) =

OUTPUT: (FIRST (REST (FIRST (REST 
                 '(MENTOR (RALPH WALDO EMERSON)
                          (HENRY DAVID THOREAU))))))

たとえば、いくつかの再帰を書きました。

(defun wheres-waldo(lispOBJ)
    (cond ((null lispOBJ) nil)
    (equalp (first lispOBJ) waldo)
    ( t (***stuck here how to write recursion for this***))
)

http://ai.eecs.umich.edu/people/wellman/courses/eecs492/f94/MP1.html wheres-waldoからこの質問を見つけました。どんな助けでも大歓迎です。ありがとうございました。

4

4 に答える 4

3

あなたのアプローチの主な問題は、最初の要素がワルドに等しい場合、どのように答えを生成すると思いますか? Waldo がいる可能性のあるパスは多数ある可能性があるため、どのパスにいるのかを反復で示す方法が必要であり、行き止まりにある場合はバックトラックする必要があります。

(defun wheres-waldo (o)
  (labels                                          ; labels is to make local functions 
   ((aux (cur acc)                                 ; define loacl function aux with args cur and acc
      (or                                          ; or stops at the first non NIL value
       (and (eq cur 'waldo) acc)                   ; if (eq cur 'waldo) we return acc 
       (and (consp cur)                            ; (else) if object is a cons 
            (or                                    ; then one of the followin
             (aux (car cur) (list 'first acc))     ; answer might be in the car
             (aux (cdr cur) (list 'rest acc))))))) ; or the cdr of the cons 
    (aux o (list 'quote o))))                      ; call aux with original object and the same object quoted. (list 'quote x) ==> 'x (as data)

ご覧のとおり、主な作業はaux、パスと引用符データを示すオブジェクトとアキュムオレータを持つことによって行われます。見つかっwaldoた場合、結果はアキュムレータです。

wald が複数の場所に存在する場合、常にcar最初に実行されるため、必ずしも最短の回答ではなく、最初に見つかった回答になります。

and私はここで/を使いorます。これらは に似てifいますが、返されるのは式の値です。たとえば、 is が最後の true 値に評価されるため、(and (eq cur 'waldo) acc)必ず返すaccようにします。NIL 値が 1 つある場合は、フォームの結果になります。すべての式が にマウントされている場合、最初の true 値 ( 以外のすべて) または NILに評価されます。リンクの演習 2 では、同様の方法で関数を書き直す必要がありました。curwaldoandorNILNIL

于 2014-02-22T22:24:21.673 に答える
1

もう少し一般的な問題に取り組み、その問題を目前の特定の問題に特化する方法を見つけた方が簡単な場合もあります。この場合、何らかの構造体と、その構造体のサブ構造体にアクセスできるいくつかのアクセサーが渡されます。検索する要素と検索するものが与えられた場合、その要素が要素であるかどうかを確認し、要素である場合はそれまでのパスを (適切な形式で) 返し、そうでない場合はそれがアクセサで分解できる構造があれば、分解した部分をそれぞれ試してみてください。

(defun find-element (element structure structure-p accessors &key (test 'eql))
  (labels ((fe (thing path)
             "If THING and ELEMENT are the same (under TEST), then 
              return PATH.  Otherwise, if THING is a structure (as 
              checked with STRUCTURE-P),  then iterate through 
              ACCESSORS and recurse on the result of each one
              applied to THING."
             (if (funcall test thing element)
                 ;; return from the top level FIND-ELEMENT
                 ;; call, not just from FE.
                 (return-from find-element path)
                 ;; When THING is a structure, see what 
                 ;; each of the ACCESSORS returns, and 
                 ;; make a recursive call with it.
                 (when (funcall structure-p thing)
                   (dolist (accessor accessors)
                     (fe (funcall accessor thing)
                         (list* accessor path)))))))
    ;; Call the helper function 
    ;; with an initial empty path
    (fe structure '())))

これにより、必要なアクセサーのシーケンスが、構造体に適用する必要がある順序とは逆の順序で返されます。例えば：

(find-element 'waldo '(ralph waldo emerson) 'consp '(car cdr))
;=> (CAR CDR)

(car (cdr '(ralph waldo emerson)))ですのでwaldo。同様に

(find-element 'emerson '(ralph (waldo emerson)) 'consp '(first rest))
;=> (FIRST REST FIRST REST)

(first (rest (first (rest '(ralph (waldo emerson))))))ですのでemerson。これで、アクセサ関数のリストを取得する問題は解決しました。次に、実際の式を構築する必要があります。これは、実際には以下を使用した非常に単純なタスクreduceです。

(defun build-expression (accessor-path structure)
   (reduce 'list accessor-path
           :initial-value (list 'quote structure)
           :from-end t))

これは、構造体も提供する限り、必要な方法で機能します。例えば：

(build-expression '(frog-on bump-on log-on hole-in bottom-of) '(the sea))
;=> (FROG-ON (BUMP-ON (LOG-ON (HOLE-IN (BOTTOM-OF '(THE SEA))))))

(build-expression '(branch-on limb-on tree-in bog-down-in) '(the valley o))
;=> (BRANCH-ON (LIMB-ON (TREE-IN (BOG-DOWN-IN '(THE VALLEY O)))))

次に、これらをまとめる必要があります。

(defun where-is-waldo? (object)
  (build-expression
   (find-element 'waldo object 'consp '(first rest))
   object))

これは私たちが望むように動作します:

(where-is-waldo? '(ralph waldo emerson))
;=> (FIRST (REST '(RALPH WALDO EMERSON)))

(where-is-waldo? '(mentor (ralph waldo emerson) (henry david thoreau)))
;=> (FIRST (REST (FIRST (REST '(MENTOR (RALPH WALDO EMERSON) (HENRY DAVID THOREAU))))))
于 2014-02-23T00:09:59.217 に答える