একটি গ্রুপে n সংখ্যক বন্ধু আছে। প্রতিটি ব্যক্তি একা থাকতে পারে বা অন্য কোনো বন্ধুর সাথে জোড়া বাঁধতে পারে। বন্ধুরা একা থাকা বা জোড়া বাঁধার মোট কতভাবে সম্ভব তা বের করতে হবে।
যদি একটি জোড়ায় দুজন বন্ধু p এবং q থাকে, তবে (p, q) বা (q, p) একই ভাবা হবে।
n সংখ্যক বন্ধুর গ্রুপের জন্য, f(n) কে উপায়ের সংখ্যা ধরে নিলে, nth ব্যক্তি হয় একা থাকবে বা জোড়া বাঁধবে। যদি nth ব্যক্তি একা থাকে, তবে (n-1) জন বন্ধুর জন্য রিকার্সন করব। যদি nth ব্যক্তি বাকি (n-1) জনের কারোর সাথে জোড়া বাঁধে, তবে (n-1) * f(n-2) জন্য রিকার্সন করব।
ইনপুট এবং আউটপুট
ইনপুট: বন্ধুর সংখ্যা। ধরা যাক ৫। আউটপুট: তাদের জোড়া মিলানোর সম্ভাব্য উপায়। এখানে উত্তর ২৬।
অ্যালগরিদম
countPairs(n)
ইনপুট: বন্ধুর সংখ্যা।
আউটপুট: n জন বন্ধুকে জোড়া মিলানোর উপায়ের সংখ্যা।
শুরু
n+1 আকারের pair অ্যারে সংজ্ঞায়িত করুন
pair[0] := 0, pair[1] := 1 এবং pair[2] := 2
i := 3 থেকে n পর্যন্ত রেঞ্জে, করুন
pair[i] := pair[i-1] + (i-1) * pair[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
