목록이 포함 된 목록의 요소 삭제

Question

LISP 초보자는 여기에 있습니다. 나는 LISP에서의 다가오는 시험을 준비하고 있으며, 해결할 수없는 문제를 만났습니다. 그래서 더 많은 경험을 가진 사람이 나를 도울 수 있기를 바랬습니다.

어쨌든, 여기 내 문제가 있습니다 : 목록을 요소로 포함 할 수있는 목록이 제공됩니다. 당신의 임무는 주어진 위치에 원자 원소를 삭제하는 것입니다.

목록 및 위치는 입력 매개 변수로 제공됩니다.

예 : Position = 5, List = (1 (2 3) ((4)) (5 ​​(6)))는 (1 (2 3) ((4)) (.

여기는 내가 지금까지 가지고있는 것입니다 ... (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)))) 
) 
) 

Answer 1

왜 장소의 절반에 z가있는 Pos와 CurrPos의 철자를 지정합니까?

그리고 코드의 문제는 cond의 마지막 분기에 있습니다. List의 cdr에서 재귀 할 때 CurrPos는 (car 목록의) 요소 수만큼 앞당겨 질 필요가 있습니다. 그리고 하위리스트의 요소를 재귀 적으로 계산해야하기 때문에 단순한 (길이 목록)은 작동하지 않습니다.

편집 : 더 정교 우리가

가

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

당신은 COND의 마지막 경우에 속하는

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

에이 차례 전화 말해, 당신은

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

를 얻을 수 currPos가 목록의 cdr에 대해 잘못되었음을 확인합니다. 1이 아니라 3이어야합니다. 실제로 w (자동차 목록)이 2 개 요소를 가지고 있기 때문에

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

으로 설정하는 코드를 개미.

그래서, 당신은 매우 간단한 함수입니다

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

및 프로그램 재귀 길이로

(deleteElementAcc Pos CurrPos (cdr List)) 

을 변경해야합니다. 예를 들어 (재귀 길이 '((1 2) ((3))))는 3을 반환합니다.

Answer 2

이 문제를 단지 에서 해결하는 동안 어떤 방법도 특별히 어렵지는 않지만, 잘 해결하는 것이 사소한 일입니다. 글쎄, 나는 큰 O와 코드 복잡성을 의미하며, 코너 케이스를 다루는 것 뿐이다. 이 코드가 부적절한 목록을 처리 할 지 확신 할 수 없으며 확실하게 줄일 수있는 부분이 있지만 기술적으로 볼 때 거기에 있습니다. 그것은 정확히 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)))