친구 페어링 문제

그룹에는 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)

입력: 친구 수.

출력 :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