Bài Toán Ghép Đôi Bạn Bè (Friend Pairing Problem)

Giới thiệu

Có n bạn bè, mỗi người có thể ở đơn độc hoặc ghép thành một cặp. Tìm tổng số cách ghép đôi hoặc ở đơn. Cặp (p, q) và (q, p) được coi là giống nhau.

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

Đầu vào: Số bạn bè n = 5
Đầu ra: Số cách ghép đôi = 26

Công thức Quy hoạch động

Gọi f(n) là số cách với n người. Người thứ n có thể ở đơn -> f(n-1) cách. Hoặc ghép với một trong n-1 người còn lại -> (n-1)*f(n-2) cách. Do đó: f(n) = f(n-1) + (n-1)*f(n-2).

countPairs(n)
Begin
    định nghĩa mảng pair[0..n]
    pair[0] := 0, pair[1] := 1, pair[2] := 2
    for i := 3 to n do
        pair[i] := pair[i-1] + (i-1) * pair[i-2]
    done
    return pair[n]
End

Ví dụ 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 << "Nhập số bạn bè: "; cin >> n;
    cout << "Số cách ghép " << n << " bạn bè: " << countPairs(n);
    return 0;
}

Kết quả

Nhập số bạn bè: 5
Số cách ghép 5 bạn bè: 26