นับวิธีจับคู่ผู้เข้าร่วมที่แต่ละคนจับคู่ได้สูงสุด 1 คน ใน C++

ได้รับ N ผู้เข้าร่วม ต้องการนับวิธีจับคู่ที่แต่ละคนจับคู่ได้สูงสุด 1 คน (อาจอยู่คนเดียวได้) — ปัญหา Telephone numbers / Involution numbers

ความสัมพันธ์เวียนเกิด (Recurrence)

f(0) = 1, f(1) = 1

f(n) = f(n-1) + (n-1) × f(n-2)

• f(n-1): คนที่ n อยู่คนเดียว
• (n-1)×f(n-2): คนที่ n จับคู่กับคนใดคนหนึ่งใน n-1 คน ที่เหลือจับคู่กัน f(n-2) วิธี

ตัวอย่าง

อินพุต: persons = 3

เอาต์พุต: 4

คำอธิบาย: (a,b)(c), (a,c)(b), (b,c)(a), (a)(b)(c)

อินพุต: persons = 2

เอาต์พุต: 2

ตัวอย่างโค้ด C++ (เวียนเกิด)

#include <iostream>
using namespace std;

int makePairs(int p) {
    int count = 0;
    if (p == 0 || p == 1) count = 1;
    else count = makePairs(p-1) + (p-1) * makePairs(p-2);
    return count;
}

int main() {
    int persons = 5;
    cout << "Number of ways to make pair (or remain single): " << makePairs(persons);
    return 0;
}

ผลลัพธ์

Number of ways to make pair (or remain single): 26