C ++中子集差异的总和

在这个问题上，我们得到了一个n的集合S。我们的任务是创建一个程序，以查找子集差异之和，即子集的最后一个元素与第一个元素的差异。

公式是

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

让我们举个例子来了解这个问题，

输入 -

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

输出-

说明-所有子集是-

{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

解决该问题的简单方法是找到所有子集的last和first之间的差异，然后将它们相加以获得总和输出。这不是最有效的解决方案，因此让我们讨论一个更有效的解决方案。

对于n个元素的集合S，也可以使用从数组的元素开始的所有子集的数量来计算总和。然后求和以求结果。

所以，

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

因此，对于具有元素{s1，s2，s3，…sn}的集合S。

可以使用元素与{s2，s3，…sn}的组合来构成以s1开头的子集。这将给出2 ^n-1套。

同样，对于以s2开头的子集，给出2^个n-2集。

概括起来，子集以Si开头，给出2 ^n-i。

因此，所有子集的第一个元素的总和为-

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

同样，我们将计算固定最后一个元素的sumLast。

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

示例

用于说明上述解决方案的程序，

#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;
}

输出结果

The sum of subset differences is 45