나는 그것을 반복해서 실행하려는 해달라고

Question

(define (lcs lst1 lst2) 
    (define (except-last-pair list) 
    (if (pair? (cdr list)) 
    (cons (car list) (except-last-pair (cdr list))) 
    '())) 
    (define (car-last-pair list) 
    (if (pair? (cdr list)) 
    (car-last-pair (cdr list)) 
    (car list))) 
    (if (or (null? lst1) (null? lst2)) null 
    (if (= (car-last-pair lst1) (car-last-pair lst2)) 
     (append (lcs (except-last-pair lst1) (except-last-pair lst2)) (cons (car-last-pair lst1) '())) 
     (**if (> (length (lcs lst1 (except-last-pair lst2))) (length (lcs lst2 (except-last-pair lst1)))) 
      (lcs lst1 (except-last-pair lst2)) 
      (lcs lst2 (except-last-pair lst1))))))** 

..

감사합니다, Superguay

Answer 1

나는이가 가장 긴 일반적인 서브을하도록되어 볼을이 알고리즘 (LCS)을 개선 할 수있는 방법 두 목록 중. 아시다시피, 꽤 느립니다. 보다 신속하게 작업하기를 원한다면 이런 식의 강압적 인 방법보다 더 복잡한 접근법을 취해야합니다. 표준 솔루션은 this Wikipedia article에 설명 된 동적 프로그래밍 알고리즘입니다.

다른 알고리즘으로 완전히 전환하지 않고도 솔루션 속도를 크게 향상시킬 수있는 방법 중 하나는 결과로 memoization을 통해 얻는 것입니다. 그 이유는 요소를 반복 출하 할 때 동일한 중간 결과를 계속 계산할 것이기 때문입니다. 리스트의 끝.

편집 : 글쎄, 쉬운 방법, 그것은 빠르게 많은 작업없이 하단에 추가 작업을 피하기 위해 let 절을 사용하는 것 좀 만들 즉

(if (or (null? lst1) (null? lst2)) null 
    (let ((front1 (except-last-pair lst1)) (front2 (except-last-pair lst2))) 
    (if (= (car-last-pair lst1) (car-last-pair lst2))  
     (append (lcs front1 front2) (cons (car-last-pair lst1) '())) 
     (let ((sub-lcs1 (lcs lst1 front2)) (sub-lcs2 (lcs lst2 front1))) 
     (if (> (length sub-lcs1) (length sub-lcs2)) 
      sub-lcs1 
      sub-lcs2)))) 

가 올바른지 희망 - 내가 돈 ' 통역사는 편리합니다.하지만 당신은 그 그림을 얻습니다.