इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया जाता है जो एक समूह में मित्रों की संख्या को दर्शाता है। हमारा कार्य FriendsPairing समस्या . को हल करने के लिए एक प्रोग्राम बनाना है
समूह का प्रत्येक मित्र या तो अविवाहित रह सकता है या किसी अन्य मित्र के साथ जुड़ सकता है। समूह के प्रत्येक मित्र की जोड़ी केवल एक बार की जा सकती है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: n = 3
Output: 4
Explanation:
Let’s say the 3 members of the group are A, B and C.
The pairing can be done as :
{A}, {B}, {C}
{A, B}, {C}
{A, C}, {B}
{A}, {B, C} समाधान दृष्टिकोण
समस्या को हल करने का एक तरीका समूह के n छात्रों के लिए हर संभव जोड़ी बनाने के लिए एक सामान्य सूत्र खोजना है।
मान लीजिए कि हमारे समूह में n मित्र हैं। और इन मित्रों को जोड़े जाने के तरीके f(n) हैं।
समूह का प्रत्येक मित्र या तो अकेला रह सकता है या समूह में किसी अन्य मित्र के साथ जुड़ सकता है। आइए प्रत्येक मामले में आउटपुट देखें।
-
केस 1 - वां मित्र अविवाहित रहने का विकल्प चुनता है, समूह से एक सदस्य कम कर दिया जाता है, अगला रिकर्सन (N-1) यानी f(N-1) से होगा।
-
केस 2 - Nth मित्र किसी अन्य सदस्य के साथ जोड़ी बनाना चुनता है, (N-2) सदस्य बना रहता है और अगला रिकर्सन N-2 से होगा। पुनरावर्ती रूप से f(N) =f(N-1) + (N-1) * f(N-2)
कहा जाता है
उनके कई तरीके हैं जिनसे इसे हल किया जा सकता है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <iostream>
using namespace std;
int countGroupPairing(int N){
int dpArr[N + 1];
for (int i = 0; i <= N; i++) {
if (i <= 2)
dpArr[i] = i;
else
dpArr[i] = dpArr[i - 1] + (i - 1) * dpArr[i - 2];
}
return dpArr[N];
}
int main(){
int N = 6;
cout<<"The number of friends in the group is "<<N<<endl;
cout<<"The total number of possible pairs is "<<countGroupPairing(N);
return 0;
} आउटपुट
The number of friends in the group is 6 The total number of possible pairs is 76
समाधान को लागू करने के लिए पुनरावर्ती दृष्टिकोण
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
int dpArr[1000];
int countGroupPairing(int N){
memset(dpArr, -1, sizeof(dpArr));
if (dpArr[N] != -1)
return dpArr[N];
if (N > 2)
return dpArr[N] = countGroupPairing(N - 1) + (N - 1) * countGroupPairing(N - 2);
else
return dpArr[N] = N;
}
int main(){
int N = 6;
cout<<"The number of friends in the group is "<<N<<endl;
cout<<"The total number of possible pairs is "<<countGroupPairing(N);
return 0;
} आउटपुट
The number of friends in the group is 6 The total number of possible pairs is 76
समस्या को हल करने का एक और तरीका है, दिए गए समाधान में फिट होने के लिए फाइबोनैकी श्रृंखला को अनुकूलित करना
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
int dpArr[1000];
int countGroupPairing(int N){
int val1 = 1, val2 = 2, val3 = 0;
if (N <= 2) {
return N;
}
for (int i = 3; i <= N; i++) {
val3 = val2 + (i - 1) * val1;
val1 = val2;
val2 = val3;
}
return val3;
}
int main(){
int N = 6;
cout<<"The number of friends in the group is "<<N<<endl;
cout<<"The total number of possible pairs is "<<countGroupPairing(N);
return 0;
} आउटपुट
The number of friends in the group is 6 The total number of possible pairs is 76