এই সমস্যায়, আমাদের একটি ধনাত্মক পূর্ণসংখ্যা N দেওয়া হয়েছে যা একটি গ্রুপে বন্ধুর সংখ্যা নির্দেশ করে। আমাদের কাজ হল ফ্রেন্ডসপেয়ারিং সমস্যা সমাধানের জন্য একটি প্রোগ্রাম তৈরি করা
গ্রুপের প্রতিটি বন্ধু হয় অবিবাহিত থাকতে পারে বা অন্য একজন বন্ধুর সাথে জুটি বাঁধতে পারে। গ্রুপের প্রতিটি বন্ধুর জোড়া শুধুমাত্র একবার করা যেতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
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 ছাত্রদের জন্য সম্ভাব্য সব ধরনের জুটি পাওয়া যায়।
ধরা যাক গ্রুপে আমাদের এন বন্ধু আছে। এবং এই বন্ধুরা যেভাবে জোড়া লাগাতে পারে তা হল f(n)।
গ্রুপের প্রতিটি বন্ধু হয় একা থাকতে পারে বা গ্রুপের অন্য বন্ধুর সাথে জুটি বাঁধতে পারে। আসুন প্রতিটি ক্ষেত্রে আউটপুট দেখি।
-
কেস 1 − Nth বন্ধু একা থাকতে পছন্দ করে, গ্রুপ থেকে একজন সদস্য কমানো হয়েছে, পরবর্তী পুনরাবৃত্তি হবে (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
