Tổng sự khác biệt của tập hợp con trong C ++

Trong bài toán này, chúng ta được đưa ra một tập S gồm n số. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng của sự khác biệt của tập hợp con là hiệu của phần tử cuối cùng và phần tử đầu tiên của tập hợp con.

Công thức là,

sumSubsetDifference = Σ [last(s) - first(s)]
s are subsets of the set S.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

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

Đầu ra -

Giải thích - Tất cả các tập hợp con là -

{1}, last(s) - first(s) = 0
{2}, last(s) - first(s) = 0
{9}, last(s) - first(s) = 0
{1, 2}, last(s) - first(s) = 1
{1, 9}, last(s) - first(s) = 8
{2, 9}, last(s) - first(s) = 7
{1, 2, 9}, last(s) - first(s) = 8
Sum = 1 + 8 + 7 + 8 = 24

Một giải pháp đơn giản cho vấn đề là tìm sự khác biệt giữa cuối cùng và đầu tiên cho tất cả các tập con và sau đó thêm chúng để có được kết quả tổng. Đây không phải là giải pháp hiệu quả nhất, vì vậy chúng ta hãy thảo luận về một giải pháp hiệu quả hơn.

Đối với tập hợp S gồm n phần tử, tổng cũng có thể được tính bằng cách sử dụng số lượng của tất cả các tập con bắt đầu từ một phần tử của mảng. Và tính tổng nó để tìm ra kết quả.

Vì vậy,

sumSetDifference(S) = Σ [last(s) - Σfirst(s)]

Vì vậy, đối với tập hợp S có các phần tử {s1, s2, s3,… sn}.

Tập hợp con bắt đầu bằng s1 có thể được tạo bằng cách sử dụng kết hợp các phần tử với {s2, s3,… sn}. Điều này sẽ cho 2 ^n-1 bộ.

Tương tự đối với tập hợp con bắt đầu bằng s2 cho kết quả là 2 ^n-2 bộ.

Tổng quát hóa nó, tập hợp con bắt đầu bằng Si cho trước 2 ^n-i .

Vì vậy, tổng của phần tử đầu tiên của tất cả các tập hợp con là -

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

Tương tự, chúng tôi sẽ tính toán sumLast sửa phần tử cuối cùng.

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

Ví dụ

Chương trình minh họa giải pháp trên,

#include<iostream>
#include<math.h>
using namespace std;
int CalcSumFirst(int S[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
      sum = sum + (S[i] * pow(2, n-i-1));
   return sum;
}
int CalcSumLast(int S[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
      sum = sum + (S[i] * pow(2, i));
   return sum;
}
int main() {
   int S[] = {1, 4, 9, 6};
   int n = 4;
   int sumSetDiff = CalcSumLast(S, n) - CalcSumFirst(S, n);
   printf("The sum of subset differences is %d", sumSetDiff);
   return 0;
}

Đầu ra

The sum of subset differences is 45