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

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

यदि एक जोड़ी में दो दोस्त p और q हैं, तो (p, q) या (q, p) समान हैं।

n दोस्तों के एक समूह के लिए, मान लें f(n) वह संख्या है जिससे वे जोड़े जा सकते हैं या अकेले रह सकते हैं। तो या तो nवां व्यक्ति अकेला रहता है, या जोड़ा जाता है। यदि nवां व्यक्ति अकेला है, तो हम (n-1) दोस्तों के लिए रिकर करते हैं। यदि nवां व्यक्ति शेष (n-1) व्यक्तियों में से किसी के साथ जोड़ा जाता है, तो हम (n-1) * f(n-2) के लिए रिकर करते हैं।

इनपुट और आउटपुट

इनपुट: दोस्तों की संख्या। मान लें 5।
आउटपुट: उन्हें जोड़ने का संभावित तरीका। यहां उत्तर 26 है।

एल्गोरिदम

countPairs(n)

इनपुट: दोस्तों की संख्या
आउटपुट: n दोस्तों को जोड़ने के तरीकों की संख्या

शुरुआत
    pair ऐरे को आकार n+1 का परिभाषित करें
    pair[0] := 0, pair[1] := 1 और pair[2] := 2
    i रेंज 3 से n में, करें
        pair[i] := pair[i-1] + (i-1) * pairs[i-2]
    पूर्ण
    pair[n]
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int countPairs(int n) {
    int pairs[n + 1];
    pairs[0] = 0;
    pairs[1] = 1;
    pairs[2] = 2;
    
    for (int i = 3; i <= n; i++)
        pairs[i] = pairs[i-1] + (i-1) * pairs[i-2];
    
    return pairs[n];
}

int main() {
    int n;
    cout << "Enter numbers: "; cin >> n;
    cout << "Number of ways to pair " << n << " friends: " << countPairs(n);
}

आउटपुट

Enter numbers: 5
Number of ways to pair 5 friends: 26