재귀 : (하위 집합 합계) 포함/제외 패턴 이해

이 재귀가 어떻게 작동하는지 이해해야하지만 간단한 재귀 예제는 이해하지만 고급 예제는 어렵습니다. 심지어 두 줄의 코드가 있다고 생각했는데 ... return 문 자체에 문제가 있습니다. 나는 이것이 어떻게 작동하는지, 특히 and/or 연산자에 대해 공백을 그립니다. 모든 통찰력은 대단히 환영합니다.재귀 : (하위 집합 합계) 포함/제외 패턴 이해

 bool subsetSumExists(Set<int> & set, int target) { 
     if (set.isEmpty()) { 
     return target == 0; 
     } else { 
     int element = set.first(); 
     Set<int> rest = set - element; 
     return subsetSumExists(rest, target) 
      || subsetSumExists(rest, target - element); 
     } 
     }

출처

2012-11-30 Tom Lilletveit

그래서 재귀 또는 부울 연산자 '및/또는'을 이해하는 데 문제가 있습니까? – vidit

모두! 어떻게 그리고/또는 그 중 어느 것을 반환 할 것인가? 첫 번째 또는 두 번째? –

재귀를 이해하려면 재귀를 이해해야합니다. 그렇게하려면 재귀 적으로 생각해야합니다.

이 특별한 경우. 어떤 들어

: subsetSum(set, target)

set가 비어과 target 다음 subsetSum는
이 그렇지 않으면, set의 첫 번째 요소를 제거 존재, 0 인 경우. subdetSum(set, target)이 존재 또는 subdetSum(set, target - removed_element) (단계 0 사용) 존재

출처

2012-11-30 09:41:11

+1 "재귀를 이해하려면 재귀 적 이해가 필요합니다" – Angew

이상한! 나는 "재귀를 이해하려면 재 프로그래밍을 이해해야한다"라는 문장을 읽을 때 deja vu를 사용했다. –

||은 논리적 OR입니다. 그것은 왼쪽에서 오른쪽으로 평가되고 단락되었습니다.

즉, 식 A || B에서 A이 먼저 평가됩니다. true 인 경우 전체 표현식은 true이며 더 이상의 평가는 수행되지 않습니다. A이 false이면 B이 계산되고 식의 값은 B이됩니다.

예제에서 A은 "집합의 첫 번째 요소를 사용하지 않고 동일한 합계를 가져 오십시오."입니다. B은 "집합에서 첫 번째 요소를 사용하여 합계가 왼쪽으로 줄어들고 요소의 나머지 부분을 얻으려고합니다."

출처

2012-11-30 09:40:05 Angew

세트 공제 이상한 구문을 보이지만, 내가 가정합니다 경우이 요소에 팝업()을 의미합니다 확인.

지수 가긴하지만 모든 가능한 조합을 찾음으로써 "작동"합니다.

|| 문에서 LHS는 현재 요소를 포함하는 합계이고 RHS는 현재 요소를 포함하는 합계이며 RHS는 제외됩니다. 따라서 지수 트리 아래에서 각 요소의 모든 조합을 켜거나 끕니다.

지수는 30 개 요소가있는 경우 즉, 0x40000000 또는 10 억 개의 조합에 가까운 2를 30의 거듭 제곱으로 생성한다는 것을 의미합니다.

물론 메모리가 부족할 수도 있습니다.

해결책을 찾으면 모든 2^N 사례를 통과하지 못할 수 있습니다. 해결책이 없다면 항상 모든 것을 방문 할 것입니다.

출처

2012-11-30 09:41:13 CashCow

는

.. (즉 순환이 종료되는 경우) 기저 케이스 세트가 비어있을 때이다 알고리즘에서 우선 검토하자.
그렇지 않으면 프로그램은 첫 번째 요소를 가져와 집합에서 뺍니다. 그것은 그렇지 않으면 true를 돌려줍니다이 subsetSumExists(rest, target - element)를 호출하고 어떤 그것을 수익률을 반환합니다 경우
지금은, 을 subsetSumExists(rest, target)를 호출하고 그 사실 여부를 확인합니다. 간단한 측면에서

, 그것은 것입니다이 호출 subsetSumExists(rest, target - element) 단지 첫 번째 subsetSumExists(rest, target) false를 반환하는 경우.

지금 일반적이다 {3,5}의 작은 샘플 세트와 나는

sSE({3,5}, 8) => "sSE({5}, 8) || sSE({5},(8-3))" 

sSE({5}, 8) => sSE({}, 8) || sSE({}, (8-5)) 

sSE({}, 8) => false.. now will call sSE({}, (8-5)) 

sSE({}, 3) => false.. now will call sSE({5}, (8-3)) 

sSE({5}, 5) => sSE({}, 5} || sSE({}, (5-5)) 

sSE({}, 5) => false.. now will call sSE({}, (5-5)) 

sSE({}, 0) => true.. ends here and return true

출처

2012-11-30 09:41:57 vidit

재귀 코드를 지금부터 기능 SSE 전화 할게 (8)의 합으로이 코드를 실행 건조하려고 할 수 있습니다 감소의 개념과 결합. 일반적으로 감소는 일부 변환을 통해 알려지지 않은 문제를 알려진 것으로 감소시키는 수단입니다.

코드를 살펴 보겠습니다. 주어진 목표 합계가 입력 데이터 세트의 요소로 구성 될 수 있는지 여부를 알아야합니다. 데이터 세트가 비어 있으면 대상 합계를 0과 비교하는 것 외에는 아무 것도 할 수 없습니다.

그렇지 않은 경우 축소를 적용 합니다. 세트에서 숫자를 선택하면 실제로는 2 가지 가능성이 있습니다 - 선택한 숫자가 찾고있는 금액에 포함되거나 그렇지 않은 숫자입니다. 다른 가능성은 없습니다 (모든 가능성을 포괄하는 것이 매우 중요합니다!). 사실, 남은 데이터에 대한 모든 가능성을 다룰 수있는 한 어떤 데이터 요소가 선택되었는지는 중요하지 않습니다.

첫 번째 경우 : 숫자는 합계에 포함되지 않습니다. 검사 된 요소와 동일한 대상 합계가없는 데이터를 사용하여 문제를 더 작은 것으로 줄일 수 있습니다.

두 번째 경우 : 숫자가 합계에 포함됩니다. 검사 된 요소가없는 데이터 집합과 요청 된 합계가 값의 수만큼 줄어들어 문제를 더 작은 것으로 줄일 수 있습니다.

참고 이러한 상황이 사실인지는 아직 알 수 없습니다. 당신은 답을 확실히 알 수있는 사소한 비어있는 상황에 이르기까지 그들을 줄입니다.

원래 질문에 대한 대답은이 두 가지 경우에 해당되면 true입니다. 연산자 ||이 정확히 무엇입니까? 피연산자 중 하나 (2 개의 결과)가 참이면 true를 반환합니다.

출처

2012-11-30 09:52:08 SomeWittyUsername

재귀 : (하위 집합 합계) 포함/제외 패턴 이해

답변

관련 문제