Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सभी संभावित सबसेट के गुणनफल का योग

इस समस्या में, हमें N संख्याओं का एक ऐरे arr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो सभी संभावित सबसेट के गुणनफल का योग निकालेगा।

यहां, हम सभी सबसेट ढूंढेंगे और फिर प्रत्येक सबसेट के लिए सभी तत्वों का गुणनफल निकालेंगे। फिर अंतिम योग की गणना करने के लिए सभी मानों को जोड़ेंगे।

उदाहरण से समझते हैं

इनपुट

arr[] = {4, 5, 6}

आउटपुट

209

व्याख्या

arr[] के सभी सबसेट हैं: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
गुणनफल का योग = (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
                = (4) + (5) + (6) + (20) + (30) + (24) + (120)
                = 209

समस्या को हल करने का एक सरल दृष्टिकोण सेट के सभी सबसेट ढूंढना और प्रत्येक सेट के तत्वों का गुणनफल निकालना है। और सभी गुणनफलों को जोड़ना, फिर अंतिम योग वापस करना जब सभी सबसेट ट्रैवर्स हो जाएं।

C++ प्रोग्राम उदाहरण (सरल दृष्टिकोण)

#include <iostream>
#include <math.h>
using namespace std;

int findSumProductSubset(int *arr, int set_length) {
    unsigned int size = pow(2, set_length);
    int sum = 0;
    int product;
    for (int counter = 1; counter < size; counter++) {
        product = 1;
        for (int j = 0; j < size; j++) {
            if (counter & (1 << j))
                product *= arr[j];
        }
        sum += product;
    }
    return sum;
}

int main() {
    int arr[] = {4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The sum of the product of all subsets is " << findSumProductSubset(arr, n);
}

आउटपुट

The sum of the product of all subsets is 209

उपरोक्त दृष्टिकोण सभी सबसेट उत्पन्न करता है इसलिए इसकी समय जटिलता एक्सपोनेंशियल है। इसलिए, यह सबसे कुशल दृष्टिकोण नहीं है।

कुशल दृष्टिकोण: समाधान के लिए पैटर्न ढूंढना

अब, तीन संख्याओं x, y, z का एक सेट देखते हैं।

योग = x + y + z + xy + yz + xz + xyz

योग = x + xz + y + yz + xy + xyz + z + 1 - 1

योग = x(1+z) + y(1+z) + xy(1+z) + 1(z+1) - 1

योग = (x + y + xy + 1)(1 + z) - 1

योग = (x(1+y) + 1(1+y))(1+z) - 1

योग = (1 + x) * (1 + y) * (1 + z) - 1

इसे निम्न तरीके से सामान्यीकृत किया जा सकता है,

n तत्व सेट के लिए,

योग = (1+ e1) * (1 + e2) * … * (1 + en) - 1

C++ प्रोग्राम उदाहरण (कुशल दृष्टिकोण)

#include <iostream>
using namespace std;

int productOfSubsetSums(int arr[], int n) {
    int sum = 1;
    for (int i = 0; i < n; ++i)
        sum *= (arr[i] + 1);
    sum--;
    return sum;
}

int main() {
    int arr[] = {5, 6, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of product of all possible subsets is " << productOfSubsetSums(arr, n);
    return 0;
}

आउटपुट

Sum of product of all possible subsets is 3779
  1. C++ में अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग C++ में अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग

    इस समस्या में, हमें N संख्याओं की एक सरणी arr दी गई है जहां arr[i] (i+1)वें नोड को दर्शाता है। साथ ही, M जोड़े किनारे हैं जहां u और v किनारे से जुड़े नोड्स को दर्शाते हैं। हमारा कार्य एक प्रोग्राम बनाना है जो अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग निकाले। यदि एक नोड की किसी अन

  1. - C++ में सभी सबसीक्वेंस के योग का योग ढूंढें

    मान लीजिए हमारे पास n एलिमेंट्स वाला एक ऐरे A है। हमें ऐरे के सभी सबसेट के योग का कुल योग ढूंढना है। तो यदि ऐरे A = [5, 6, 8] जैसा है, तो यह होगा - सबसेट योग 5 5 6 6 8 8 5,6 11 6,8 14 5,8 13 5,6,8 19 कुल योग 76 जैसा कि ऐरे में n एलिमेंट्स हैं, तो हमारे पास 2ⁿ संख्या में सबस

  1. C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें

    मान लीजिए हमारे पास एक धनात्मक पूर्णांक L है, जो परफेक्ट बाइनरी ट्री में स्तरों की संख्या दर्शाता है। इस परफेक्ट बाइनरी ट्री में पत्ती नोड्स को 1 से n तक संख्या दी गई है। जहां n पत्ती नोड्स की संख्या है। पैरेंट नोड बच्चों का योग है। हमारा कार्य इस परफेक्ट बाइनरी ट्री के सभी नोड्स का योग प्रिंट करने