1

ここではLISPの初心者です。LISP の次の試験の準備をしていて、解決できない問題に出くわしたので、経験豊富な人が助けてくれることを期待していました。

とにかく、ここに私の問題があります。要素としてリストを含む可能性のあるリストが与えられます。あなたの仕事は、特定の位置にあるアトミック要素を削除することです。

リストと位置は入力パラメータとして与えられます。

例 : Position=5 、 List=(1 (2 3) ((4)) (5 (6))) 、 (1 (2 3) ((4)) ((6))) を返す必要があります。

これが私がこれまでに得たものです...（PS以下のコードは imMaw の支援のおかげで機能します。編集をチェックして、以前の間違いを確認できます）。

(defun number_of_atoms(List)
 (atoms List 0)
)
(defun atoms(List Number)
 (cond
  ((null List) Number)
  ((atom (car List)) (atoms (cdr List) (+ 1 Number)))
  ((+ (atoms (car List) Number) (atoms (cdr List) 0)))
 )
)
(defun deleteElement(Pos List)
 (deleteElementAcc Pos 1 List)
)
(defun deleteElementAcc(Pos CurrPos List)
(cond 
  ((null List) nil)
  ((and (atom (car List)) (not(eql CurrPos Pos))) (cons (car List) (deleteElementAcc Pos (+ CurrPos 1) (cdr List))))
  ((and (atom (car List)) (eql CurrPos Pos)) (deleteElementAcc Pos (+ CurrPos 1) (cdr List)))
  ((cons (deleteElementAcc Pos CurrPos (car List))
         (deleteElementAcc Pos (+ CurrPos (number_of_atoms(car List))) (cdr List))))
)
)
4

2 に答える 2

1

Pos と CurrPos の綴りの半分に z があるのはなぜですか?

コードの問題は、cond の最後の分岐にあります。List の cdr を再帰する場合、CurrPos は (car List) 内の要素の数だけ進める必要があります。また、サブリスト内の要素を再帰的にカウントする必要があるため、単純な (長さのリスト) は機能しません。

編集：より詳細な 

(deleteElement 3 '((1 2) (3 4)))

これを

(deleteElementPos 3 1 '((1 2) (3 4))),

これは cond の最後のケースに該当し、次のようになります。

(cons (deleteElementAcc 3 1 '(1 2))
      (deleteElementAcc 3 1 '((3 4))))

リストの cdr の currPos が間違っていることに注意してください。1 ではなく 3 である必要があります。実際には、コードを次のように変更する必要があります。

(cons (deleteElementAcc 3 1 '(1 2))
      (deleteElementAcc 3 (+ 1 2) '((3 4))))

(car List) には 2 つの要素があるためです。

だから、あなたはただ変更する必要があります

(deleteElementAcc Pos CurrPos (cdr List))

の中へ

(deleteElementAcc Pos (+ CurrPos (recursive-length (car List))) (cdr List))

非常に単純な関数である recursive-length をプログラムします。サブリストの要素をカウントする必要があるため、たとえば (recursive-length '((1 2) ((3)))) は 3 を返します。

于 2012-11-29T04:31:54.197 に答える
0

この問題を解決するのは特に難しいことではありませんが、うまく解決することは非常に困難です。よくあるのは、ビッグ オーとコードの複雑さの両方、そしてコーナー ケースの処理です。このコードが不適切なリストでさえ処理できるかどうかはわかりません。また、冗長性を確実に減らすことができる部分もありますが、技術的にはあります。ツリーを正確に O(n) でウォークスルーします。ここで、n はツリー内の要素の数であり、O(n + 2 * (最大深度)) のスペースを使用します。つまり、ツリーによって既に使用されているメモリを使用します。さらに、メモリはツリーの最大深度に比例します。

循環リストまたは重複を特定する試みは行われませんでした:

(defun remove-from-tree-linear (tree &rest positions)
  (loop with node = tree
     with nilcar = (gensym)
     with positions = (sort (remove-duplicates positions) #'<)
     with counter = 0
     with copy = nil
     with root = nil
     with stack = nil
     with backrefs = nil
     while (or node stack) do
       (cond
         ((null node)
          (setf backrefs (cdr backrefs))
          (when (car stack)
            (setf copy (car backrefs)))
          (setf node (car stack) stack (cdr stack)))
         ((consp (car node))
          (if copy
              (if (eq (car copy) nilcar)
                  (setf (car copy) (list nilcar)
                        copy (car copy)
                        (car backrefs) copy)
                  (setf (cdr copy) (list nilcar)
                        copy (cdr copy)
                        (car backrefs) copy))
              (setf copy (list nilcar)
                    root copy))
          (setf backrefs (cons copy backrefs))
          (setf stack (cons (cdr node) stack)
                node (car node)))
         (t (if (and positions (= counter (car positions)))
                (setf positions (cdr positions))
                (if copy
                    (progn
                      (if (eq (car copy) nilcar)
                          (setf (car copy) (list (car node))
                                copy (car copy))
                          (setf (cdr copy) (list (car node))
                                copy (cdr copy)))
                      (setf (car backrefs) copy))
                    (setf copy (list (car node))
                          root copy
                          backrefs (list copy))))
            (setf node (cdr node))))
       (incf counter)
     finally (return root)))
于 2012-11-29T14:06:57.280 に答える