資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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解決此問題的一個簡單方法是找到所有子集的最後一個元素和第一個元素之間的差，然後將它們加起來得到輸出總和。這不是最有效的解決方案，因此讓我們討論一個更有效的解決方案。
對於一個包含 n 個元素的集合 S，總和也可以使用從陣列元素開始的所有子集的數量來計算。然後將其相加以找到結果。
所以，
sumSetDifference(S) = Σ [last(s) - Σfirst(s)]
所以，對於一個包含元素 {s1, s2, s3, … sn} 的集合 S。
以 s1 開頭的子集可以使用元素 {s2, s3, … sn} 的組合來建立。這將產生 2n-1 個集合。
類似地，以 s2 開頭的子集產生 2n-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
更新於：2020-08-05
199 次檢視
廣告