Vấn đề ghép nối bạn bè

Trong một nhóm, có n số bạn. Mỗi người có thể vẫn độc thân hoặc kết đôi với một số người bạn khác. Tìm tổng số cách, trong đó bạn bè có thể vẫn độc thân hoặc có thể kết đôi.

Nếu một cặp có hai bạn p và q thì (p, q) hoặc (q, p) giống nhau.

Đối với một nhóm gồm n người bạn, gọi f (n) là số cách họ có thể kết đôi hoặc vẫn độc thân. Sau đó, người thứ n vẫn độc thân, hoặc kết đôi. Nếu người thứ n còn độc thân, thì chúng ta tái diễn cho (n - 1) người bạn. Nếu người thứ n được ghép nối với bất kỳ người nào trong số (n-1) người còn lại, thì chúng ta lặp lại (n-1) * f (n-2).

Đầu vào và Đầu ra

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

Thuật toán

countPairs(n)

Đầu vào: Số lượng bạn bè.

Đầu ra :Số cách ghép đôi n người bạ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

Ví dụ

#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);
}

Đầu ra

Enter numbers: 5
Number of ways to pair 5 friends: 26