มีเพื่อน n คน แต่ละคนสามารถ อยู่คนเดียว (Single) หรือ จับคู่ (Pair) กับอีกคนหนึ่งได้ หาจำนวนวิธีทั้งหมดที่เป็นไปได้
หมายเหตุ: คู่ (p, q) และ (q, p) ถือว่าเป็นวิธีเดียวกัน
ตัวอย่าง Input และ Output
Input: n = 5 Output: Number of ways to pair 5 friends: 26
สูตร Reccurrence
กำหนด f(n) = จำนวนวิธีสำหรับ n คน
พิจารณาบุคคลที่ n:
- อยู่คนเดียว: เหลือ n-1 คน →
f(n-1)วิธี - จับคู่: เลือกคู่จาก n-1 คนที่เหลือ →
(n-1) × f(n-2)วิธี
Recurrence: f(n) = f(n-1) + (n-1) * f(n-2)
Base cases: f(0)=0, f(1)=1, f(2)=2
อัลกอริทึม Dynamic Programming
ฟังก์ชัน countPairs(n)
ขั้นตอน:
- สร้างอาร์เรย์
pairs[n+1] pairs[0]=0, pairs[1]=1, pairs[2]=2- for i = 3 ถึง n:
pairs[i] = pairs[i-1] + (i-1) * pairs[i-2]
- คืน
pairs[n]
ตัวอย่างโค้ด 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 << "Enter numbers: "; cin >> n;
cout << "Number of ways to pair " << n << " friends: " << countPairs(n);
return 0;
}Output
Enter numbers: 5 Number of ways to pair 5 friends: 26
ตารางค่าตัวอย่าง
| n | f(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 10 |
| 5 | 26 |
| 6 | 76 |
| 7 | 232 |
ความซับซ้อน
- Time: O(n)
- Space: O(n) (ลดเป็น O(1) ได้)
ความสัมพันธ์กับ Telephone Numbers
ลำดับนี้เรียกว่า Telephone Numbers หรือ Involution Numbers ปรากฏใน Combinatorics หลายบริบท
