इस समस्या में, हमें n संख्याओं का एक समुच्चय S दिया गया है। हमारा कार्य उपसमुच्चय अंतर का योग ज्ञात करने के लिए एक प्रोग्राम बनाना है जो उपसमुच्चय के अंतिम और पहले तत्वों का अंतर है।
सूत्र है,
sumSubsetDifference = Σ [last(s) - first(s)] s, समुच्चय 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
योग = 1 + 8 + 7 + 8 = 24
समस्या का एक सरल समाधान सभी उपसमुच्चयों के लिए अंतिम और पहले का अंतर ढूंढना और फिर उन्हें जोड़कर योग आउटपुट प्राप्त करना है। यह सबसे प्रभावी समाधान नहीं है, तो आइए एक अधिक कुशल समाधान पर चर्चा करें।
n तत्वों के एक समुच्चय S के लिए, योग की गणना सरणी के एक तत्व से शुरू होने वाले सभी उपसमुच्चयों की संख्या का उपयोग करके भी की जा सकती है। और परिणाम ढूंढने के लिए इसे जोड़ना।
तो,
sumSetDifference(S) = Σ [last(s) - Σfirst(s)]
तो, तत्वों {s1, s2, s3, ... sn} वाले समुच्चय S के लिए।
s1 से शुरू होने वाले उपसमुच्चय को {s2, s3, ... sn} तत्वों के संयोजन का उपयोग करके बनाया जा सकता है। यह 2^(n-1) सेट देता है।
इसी तरह s2 से शुरू होने वाले उपसमुच्चय के लिए 2^(n-2) सेट मिलते हैं।
इसे सामान्यीकृत करते हुए, Si से शुरू होने वाला उपसमुच्चय 2^(n-i) देता है।
तो, सभी उपसमुच्चयों के पहले तत्व का योग है -
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<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("उपसमुच्चय अंतरों का योग %d", sumSetDiff);
return 0;
}
आउटपुट
उपसमुच्चय अंतरों का योग 45
