Lisp에서 가장 길어지는 순서가 짧음

Question

나는 곧 시험을 치기 위해 몇 가지 문제를 해결하기 위해이 Lisp 함수에 대한 도움이 필요하다. CLISP에서 일하고 있어요. 목록에서 홀수만으로 구성된 가장 긴 감소 시퀀스를 찾아야합니다. 예 :

(longest '(13 9 3 7 4 7 5 3 2 8 15 11 9 7 3)) 

반환해야는 :

(15 11 9 7 3) 

유일한 필수 요구 사항은 함수가 연속 서브 시퀀스로 재귀 적 :

Answer 1

구현 될 필요가 있다는 것이 쉽다는 것이다. 나는 혀짤 소리를 내지 않는다는 것을 제외하고 말로 설명해야한다.

1. 통화 이들 부가 긴 즉 C의 원경 b) 길이 발견 인자 a)) 현재 서브 시퀀스 d) 길이 재귀 헬퍼. 처음에 이들은() 0() 0입니다.
2. 목록의 머리가 고른 동안 꼬리에 재발.
3. 첫 번째 홀수가 발생하여 current을 시작하고 꼬리에 반복하십시오.
4. head가 짝수이거나 head가 이전 요소보다 작지 않은 경우 현재 시퀀스가 ​​중지됩니다. 길이를 이전에 발견 된 가장 긴 순서와 비교하십시오. 전류가 더 길다면, 가장 긴 새로운 것이되고 그렇지 않으면 전류를 잊어 버리게됩니다. 2로 이동하십시오.

목록의 끝에 도달하면 두 개의 저장된 목록 중 더 긴 것이 답입니다.

Answer 2

재귀를 사용하여 한 단계에서이 작업을 수행 할 수 있습니다 (제안하려는 방법보다 더 빠른 &). 그러나 모든 코드를 생성하는 경우 코드가 읽기 쉽고 모듈화되며 간단합니다. 먼저 가능한 솔루션을 선택하고 유효한 솔루션으로 필터링 한 다음 해당 솔루션 중에서 최상의 솔루션을 반환하십시오.

이렇게하려면 발전기 & 맵핑 기능이 필요합니다 (이 문제에 대해서는 두 개의 중첩 된 매치리스트를 제안합니다), 필터 함수 (이 함수를 작성하고 홀수가 감소한 다음 리스프의 remove- if-not funciton) 및 감소 함수 (필터링 된 것 중에서 가장 좋은 솔루션 (가장 긴 목록)을 반환).

접근 방식이 스타일에 대해 설명 SICP의 섹션이있다 : http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2

신호 처리 엔지니어가 자연 단계의 캐스케이드를 통해 흐르는 신호의 측면에서 에게 이러한 프로세스를 개념화 찾을 것입니다 .. .

Answer 3

일부 비틀기와 하스켈로 번역 Daniel's answer으로하는 알고리즘 :

longest_sub xs = g2 xs [] 0 
    where 
    g2 [] a _ = a 
    g2 (x:t) a i 
     | even x = g2 t a i 
     | otherwise = g4 t [x] 1 
     where 
     g4 [] b j = if j>i then reverse b else reverse a 
     g4 xs@(x:t) b j    
      | even x || x >= head b 
         = if j>i then g2 xs b j 
            else g2 xs a i 
      | otherwise = g4 t (x:b) (j+1) 

012 커먼 리스프에서 3,516,

:

(defun longest (xs) 
    (prog ((a nil) (i 0) b j x)     ; var decls 
     G2 (if (null xs) (return (reverse a))) ; code 
      (setf x (car xs) xs (cdr xs)) 
      (if (evenp x) 
       (go G2)) 
     G3 (setf b (list x) j 1) 
     G4 (if (null xs) 
       (if (> j i) 
        (return (reverse b)) 
        (return (reverse a)))) 
      (setf x (car xs) xs (cdr xs)) 
      (when (evenp x) 
       (if (> j i) (setf a b i j)) 
       (go G2)) 
      (when (>= x (car b)) 
       (if (> j i) (setf a b i j)) 
       (go G3)) 
      (setf b (cons x b) j (+ j 1)) 
      (go G4))) 

함수 호출은, 결국 영광 GOTO 그렇지?

참조 : prog doc page.