C++ में फ्रेंड्स पेयरिंग समस्या

समस्या विवरण

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

समूह का प्रत्येक दोस्त या तो अकेला रह सकता है या किसी अन्य दोस्त के साथ जोड़ी बना सकता है। समूह के प्रत्येक दोस्त की जोड़ी केवल एक बार की जा सकती है।

उदाहरण

इनपुट: n = 3
आउटपुट: 4
व्याख्या: मान लीजिए समूह के 3 सदस्य A, B और C हैं। जोड़ी निम्न प्रकार से की जा सकती है:
{A}, {B}, {C}
{A, B}, {C}
{A, C}, {B}
{A}, {B, C}

हल का दृष्टिकोण

समस्या को हल करने की एक विधि n छात्रों के समूह के लिए सभी संभावित जोड़ी के लिए एक सामान्य सूत्र खोजना है।

मान लीजिए हमारे पास समूह में n दोस्त हैं। और इन दोस्तों के जोड़ी बनाने के तरीके f(n) हैं।

समूह का प्रत्येक दोस्त या तो अकेला रह सकता है या समूह में किसी अन्य दोस्त के साथ जोड़ी बना सकता है। आइए प्रत्येक मामले में आउटपुट देखें।

• केस 1 - Nवां दोस्त अकेला रहना चुनता है, समूह से एक सदस्य कम हो जाता है, अगली पुनरावृत्ति (N-1) से होगी यानी f(N-1)।
• केस 2 - Nवां दोस्त किसी अन्य सदस्य के साथ जोड़ी बनाने का चयन करता है, (N-2) सदस्य रहते हैं और अगली पुनरावृत्ति N-2 से होगी। पुनरावर्ती रूप से f(N) = f(N-1) + (N-1) × f(N-2)

डायनामिक प्रोग्रामिंग समाधान

#include <iostream> 
using namespace std; 

int countGroupPairing(int N) {
    vector<int> dp(N + 1);
    for (int i = 0; i <= N; i++) {
        if (i <= 2)
            dp[i] = i;
        else
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
    return dp[N];
}

int main() {
    int N = 6;
    cout << "समूह में दोस्तों की संख्या है " << N << endl;
    cout << "कुल संभावित जोड़ी की संख्या है " << countGroupPairing(N);
    return 0;
}

पुनरावर्ती दृष्टिकोण (मेमोइजेशन के साथ)

#include <bits/stdc++.h> 
using namespace std; 

int dp[1000];

int countGroupPairing(int N) {
    if (dp[N] != -1) return dp[N];
    if (N > 2)
        return dp[N] = countGroupPairing(N - 1) + (N - 1) * countGroupPairing(N - 2);
    else
        return dp[N] = N;
}

int main() {
    memset(dp, -1, sizeof(dp));
    int N = 6;
    cout << "समूह में दोस्तों की संख्या है " << N << endl;
    cout << "कुल संभावित जोड़ी की संख्या है " << countGroupPairing(N);
    return 0;
}

स्पेस-अनुकूलित O(1) दृष्टिकोण

int countGroupPairing(int N) {
    if (N <= 2) return N;
    long long a = 1, b = 2, c = 0; // f(1), f(2)
    for (int i = 3; i <= N; i++) {
        c = b + (i - 1) * a;
        a = b;
        b = c;
    }
    return c;
}

आउटपुट

समूह में दोस्तों की संख्या है 6
कुल संभावित जोड़ी की संख्या है 76

जटिलता विश्लेषण

अनुक्रम

यह टेलीफोन संख्याओं / अनुक्रम A000085 के रूप में जाना जाता है: 1, 2, 4, 10, 26, 76, 232, 764, ...