朋友配对问题

在一个小组中，有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

   //对于0到2，有0到2种可能的组合
   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