ปัญหาการจับคู่เพื่อน

ในกลุ่ม มีเพื่อนจำนวน 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