C++의 하위 집합 차이 합계

이 문제에서는 n개의 집합 S가 제공됩니다. 우리의 임무는 부분 집합의 마지막 요소와 첫 번째 요소의 차이인 부분 집합 차이의 합을 찾는 프로그램을 만드는 것입니다.

공식은,

sumSubsetDifference =Σ [last(s) - first(s)]s는 집합 S의 하위 집합입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 -

S ={1, 2, 9} n =3

출력 -

설명 − 모든 하위 집합은 −

문제에 대한 간단한 해결책은 모든 하위 집합에 대해 마지막과 처음의 차이를 찾은 다음 더하여 합계 출력을 얻는 것입니다. 이것은 가장 효과적인 솔루션이 아니므로 보다 효율적인 솔루션에 대해 논의해 보겠습니다.

n개의 요소로 구성된 집합 S의 경우 배열의 요소에서 시작하는 모든 부분 집합의 수를 사용하여 합을 계산할 수도 있습니다. 그리고 결과를 찾기 위해 합산합니다.

그래서

sumSetDifference(S) =Σ [마지막(s) - Σfirst(s)]

따라서 요소가 {s1, s2, s3, … sn}인 집합 S의 경우

s1로 시작하는 부분집합은 {s2, s3, … sn}이 있는 요소의 조합을 사용하여 만들 수 있습니다. 이렇게 하면 2 ^n-1 이 됩니다. 세트.

마찬가지로 s2로 시작하는 부분 집합의 경우 2 ^n-2 를 제공합니다. 세트.

일반화하면 2 ^n-i 이 주어진 Si로 시작하는 부분집합 .

따라서 모든 부분집합의 첫 번째 요소의 합은 -

SumFirst =a1.2
n-1
 + a2.2
n-2
 + a3.2
n-3
 + ... + an.2
n-n
 

마찬가지로 마지막 요소를 수정하는 sumLast를 계산합니다.

SumLast =a1.2
n-n
 + a1.2
n - (n-1)
 + a3.2
n - (n-2)
 + ... + an.2
n - (n-(n-1))
 

예시

위의 솔루션을 설명하는 프로그램,

#include#include네임스페이스 std;int CalcSumFirst(int S[], int n) { int sum =0; for (int i =0; i  
출력
 
하위 집합 차이의 합은 45입니다.