재귀 적으로 동등성을 위해 두 세트를 비교합니까?

Question

나는 프로그래밍에 익숙하지 않고 입력으로 두 세트를 취할 수있는 함수를 만들려고하는데, 다른 세트 (a (bc) de (fg (h)), (abc (def))를 포함 할 수있다. 예를 들어 그들이 동등한 지 여부를 반환합니다. 도움이된다면 계획대로 작업하지만 실제로 어떻게 할 수 있는지 시각화하려고합니다. 사전에 도움을 주셔서 감사합니다.

Answer 1

간단한 재귀 적 접근 방식은 집합 A의 원소와 집합 B에서 동등한 원소를 찾는다. 하나가 발견되면 A와 B에서 두 원소를 제거하고 재귀한다. 두 집합이 모두 비어 있으면 성공으로 멈추고, 하나가 비어 있으면 실패로 끝난다. A의 선택된 요소에 B의 해당 요소가없는 경우

Answer 2

일부 la nguage에는 Racket을 포함한 기본 제공 세트 유형이 있습니다. 따라서 유일한 문제는 목록 (다른 목록을 포함 할 수 있음)을 중첩 된 집합으로 변환하는 것입니다. 이 같은 뭔가 : (경고 - 완전히 테스트되지 않은 코드)

(require racket/set) 
(define (recursive-make-set obj) 
    (cond 
    [(list? obj) (list->set (map recursive-make-set obj))] 
    [else obj])) 

는 기본적으로 우리는 혼자 원자를두고 반복적으로 요소를 변환 에 내장 list->set 함수를 사용하여 목록에서 세트를 구축 할 수 있습니다.

Answer 3

두 가지 핵심 포인트 : 당신이 "핵심"요소에 도착하면 값을 일치시키기위한 (나) 시험

값 개별 구성 요소의 일치 형 동일성에 대한 (가) 시험 사용 무엇이든 프로그래밍 언어, 우리의 경우 예를 들어, (a (bc) ...)와 (abc ...)와 같은리스트를 보면, 각각이 다른 타입 인 "a"를 본 후에 우리는 주목할 것입니다. 첫 번째 목록은 목록과 함께 "a"를 따르고 두 번째 목록은 다른 비 목록 요소와 함께 이어집니다. 언어가 실패하거나 (일종의 오류를 신호로 보냄) 그렇지 않으면 이와 유사한 유형을 각각 고려할 수 있지만 일반적으로 유형을 쿼리하는 방법을 제공합니다.

스키마에서 (그리고 정확하게 기억하지 못합니다.) 첫 번째 목록의 car 값은 a이고 cdr 값은 목록 ((bc) ...)입니다. 두 번째 목록에는 a의 자동차 값이 있지만 cdr은 목록을 반환합니다 (b c ...). 이 두 언어는 언어가 "동일성"에 대한 다른 시각을 제공하지 않는 한 동일 할 수 없습니다.

개체 유형에 대한 이러한 종류의 테스트는 목록이 동일한 지 확인하는 첫 번째 단계입니다.

다음으로 이미 확인 된 동일한 구조 내의 해당 위치에서 기본 요소 값을 테스트합니다. 우리는 적절한 방식으로 구조를 횡단해야합니다 (즉, 구조 세부 정보에 의존).

트래 버설의 알고리즘 세부 정보는 프로그래밍 언어에 따라 다릅니다. 일부 언어는 실수를 피하고 동일성을 테스트 할 때 다른 언어보다 도움이됩니다.

우리는 재귀 적 또는 반복적 접근법을 사용할 수 있습니다. 구성표와 개념적으로 재귀 적으로 더 자연 스럽습니다.

유형 및 값이 모두 구성된 테스트 의사 코드 인 샘플 의사 코드 =?

function f (l1, l2): 
(=? car(l1) car(l2)) 
and 
(f cdr(l1) cdr(l2)) 

재귀에 유의하십시오. 이것이하는 일은, 단순한 요소를 얻는다면, eqality를 테스트하고 그 값을 반환한다는 것입니다. 그 함수가 직접적으로 호출 되었다면, 그것은 최종적으로 재귀 적으로 호출 되었다면, 그 응답을 함수 호출의 체인으로 다시 보내서 중첩 된 (f cdr (l1) cdr (l2)) false 또는 true를 반환합니다 궁극적으로 가장 높은 수준의 호출도 false를 반환하거나 잠재적으로 여전히 true를 반환 할 수 있습니다 ("and"요구 사항과 작동 방식을 기록하십시오).모든 부분이 사실 일 때만 참이되고, 어떤 부분이 거짓이면 거짓이 발생 함). 마찬가지로, 함수가리스트를 얻으면, car 부분을 테스트하고 나머지리스트에서 재귀 적으로 스스로를 호출 할 때 얻는 값으로 "t and f"값을 "and"합니다. 따라서이 함수는 사용자가 피드를 제공하는 하위 목록의 복잡한 구조에서 목록과 비 목록을 모두 처리합니다. [우리가 =로 가정했음을 기억하십시오. 예를 들어 두 종류와 값 확인, 관리하도록 (=? B '(B)) #F]

는 [또한, 당신은 동등성을 테스트하는 데 사용할 수있는 무엇을 http://cs.gettysburg.edu/~tneller/cs341/scheme-intro/exercises.html#Equivalence를 볼 것입니다.]