এই সমস্যাতে, আমাদের একটি পজিটিভ ইন্টিজার N দেওয়া আছে যা একটি গ্রুপে ফ্রেন্ডের সংখ্যা নির্দেশ করে। আমাদের কাজ হল ফ্রেন্ডস পেয়ারিং প্রোব্লেম সমাধান করা।
গ্রুপের প্রতিটি ফ্রেন্ড অথবা সিঙ্গল থাকতে পারে অথবা অন্য একটি ফ্রেন্ডের সাথে পেয়ার হতে পারে। গ্রুপের প্রতিটি ফ্রেন্ডের পেয়ারিং শুধু একবারই করা যাবে।
উদাহরণ দেখি:
ইনপুট: n = 3 আউটপুট: 4 ব্যাখ্যা: ধরি গ্রুপের ৩ সদস্য হল A, B এবং C। পেয়ারিং করা যায়: {A}, {B}, {C} {A, B}, {C} {A, C}, {B} {A}, {B, C}
সমাধানের পদ্ধতি
একটি পদ্ধতি হল সব সম্ভাব্য পেয়ারিং বের করার একটি জেনারেল ফর্মুলা খুঁজে বের করা।
ধরি গ্রুপে n জন ফ্রেন্ড আছে। এবং এই ফ্রেন্ডরা যেভাবে পেয়ার হতে পারে সেটি f(n)।
গ্রুপের প্রতিটি ফ্রেন্ড অথবা সিঙ্গল থাকতে পারে অথবা অন্য একজন ফ্রেন্ডের সাথে পেয়ার হতে পারে। প্রতিটি কেসের আউটপুট দেখি।
কেস ১ - Nth ফ্রেন্ড সিঙ্গল থাকতে চায়, গ্রুপ থেকে একজন কমে যায়, পরবর্তী রিকার্শন হবে (N-1) থেকে অর্থাৎ f(N-1)।
কেস ২ - 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
