스키마의 하위 목록 색인을 반환하십시오.

Question

글쎄, 저는 초보자입니다. SICP를 지금 읽고 있습니다. 웹 사이트에서 질문을 찾았습니다. 생각해보기까지 이틀이 걸렸지 만, 생각해 낼 수는 없었습니다. 그것으로? 다음

질문 :

컴퓨터 과학의 일반적인 작업은 데이터 세트에서 패턴의 인스턴스를 찾는 것입니다. 이 문제에서 공간에있는 하위 목록의 모든 인스턴스의 시작 인 의 인덱스 목록을 순서대로 반환하는 절차 (찾기 하위 목록 공간 하위 목록)를 작성합니다. 하위 목록의 인스턴스는 []의 예제 중 하나에서와 같이 이 겹칠 수 있습니다. 공백에 목록이 포함되어있는 경우 [ *] 아래 예제 중 하나와 같이 공백 목록의 하위 목록 을 찾을 필요가 없습니다. 하위 목록이 비어 있다고 가정 할 수 있습니다.

Examples: 
(find-sublist '(7 1 2 3 4 1 2 1 2) '(1 2)) ; should return '(2 6 8) 
(find-sublist '(“a” “b” “c” “b” “d”) '(“d”)) ; should return '(5) 
(find-sublist '((1 2) (3 4) (5 . 6) 7 #f) '((3 4) (5 . 6))) ; should return '(2) 
(find-sublist '(1 1 1 2 1) '(1 1)) ; [*] should return '(1 2) 
(find-sublist '(9 1 2 3 (5 1 2 3) 1 2 3) '(1 2 3)) ; [**]should return '(2 6) 
(find-sublist '() '(#t #f #f)) ; should return '() 

Answer 1

답을 찾기 위해 몇 가지 힌트를 제공하고 공백을 채 웁니다.

지금

(define (sublist? lst sublst) 
    (cond (<???> <???>) ; if sublst is empty return true 
     ((and <???> ; if lst is not empty and 
       <???>) ; the first element is equal in both lists 
     (sublist? <???> <???>)) ; advance recursion over both lists 
     (else <???>))) ; otherwise return false 

기본 절차 : space 각 위치에서 이것을 검사하는 첫 번째 단계는 먼저 두 문제를 분할 sublst가 lst 상기 제 1 위치로부터 시작 lst 인 경우 알려주 술어 거기서 시작하는 하위 목록이 있다면 (이전 절차 사용). 그렇다면, 현재 색인 요소를 전달하는 목록을 작성하십시오. 우리는 추가 매개 변수의 현재 인덱스를 추적해야하는 공지 사항 : 당신은 자신에게 질문을

(define (find-sublist space sublist) 
    (let loop ((space space)   ; initialize iteration variables 
      (idx 1)) 
    (cond (<???> <???>)    ; if space is empty return the empty list 
      ; if the list starting at current position is the sublist 
      ((sublist? space sublist) 
      (cons <???>    ; cons current index, advance recursion 
       (loop <???> <???>))) ; over the list and increment index 
      (else      ; otherwise just advance the recursion 
      (loop <???> <???>)))))  ; same as before 

Answer 2

: 내 목록의 첫 번째 요소는 패턴과 일치 하는가? 그렇다면 색인을 기록하십시오. 이 문제를 풀면 같은 논리를 나머지 목록에 적용합니다. 다음은 간단한 해결책입니다.

(define (find-sublist list sub) 
    (define (sublist? list sub) 
    (or (null? sub) 
     (and (not (null? list)) 
      (equal? (car sub) (car list)) 
      (sublist? (cdr list) (cdr sub))))) 

    (let walking ((list list) (index 1) (indices '())) 
    (if (null? list) 
     (reverse indices) 
     (walking (cdr list) 
       (+ 1 index) 
       (if (sublist? list sub) 
        (cons index indices) 
        indices))))) 

이것은 '꼬리 재귀'라는 기술을 사용하여 계산과 동일한 반복을 수행합니다.