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开头的子集。这将给出2n-1套。
同样,对于以s2开头的子集,给出2个n-2集。
概括起来,子集以Si开头,给出2n-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