ফ্রেন্ড পেয়ারিং সমস্যা

একটি গোষ্ঠীতে, n সংখ্যক বন্ধু রয়েছে৷ প্রতিটি ব্যক্তি অবিবাহিত থাকতে পারে বা অন্য কোন বন্ধুর সাথে জুটিবদ্ধ হতে পারে। মোট উপায়গুলি খুঁজুন, যেখানে বন্ধুরা একা থাকতে পারে বা জুটিবদ্ধ হতে পারে৷

যদি একটি জোড়ার দুটি বন্ধুর p এবং q থাকে, তাহলে (p, q) বা (q, p) একই।

n বন্ধুদের একটি গোষ্ঠীর জন্য, f(n) কে কীভাবে তারা জোড়া লাগানো যায় বা অবিবাহিত থাকতে পারে তার সংখ্যা হতে দিন। তারপর হয় nম ব্যক্তি অবিবাহিত থাকে, বা জুটিবদ্ধ হয়। যদি nম ব্যক্তি অবিবাহিত হয়, তবে আমরা (n - 1) বন্ধুদের জন্য পুনরাবৃত্তি করি। যদি nম ব্যক্তিটিকে অবশিষ্ট (n-1) ব্যক্তির সাথে যুক্ত করা হয়, তাহলে, আমরা পুনরাবৃত্তি করি (n-1) *f(n-2)।

ইনপুট এবং আউটপুট

Input:
The number of friends. Say 5.
Output:
The possible way to pair them. Here the answer is 26.

অ্যালগরিদম

countPairs(n)

ইনপুট: বন্ধুর সংখ্যা।

আউটপুট :বন্ধুদের জোড়ার উপায়ের সংখ্যা।

Begin
   define pair array of size n + 1
   pair[0] := 0, pair[1] := 1 and pair[2] := 2

   for i in range 3 to n, do
      pair[i] := pair[i-1] + (i+1)*pairs[i-2]
   done

   pair[n]
End

উদাহরণ

#include <iostream>
using namespace std;

int countPairs(int n) {
   int pairs[n + 1];             //number of pairs for ith number

   //for number 0 to 2, there are 0 to 2 possible combination
   pairs[0] = 0;
   pairs[1] = 1;
   pairs[2] = 2;

   for (int i = 3; i <= n; i++)             //fill array for 3 to n numbers
      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