เพื่อแก้ปัญหาที่ n = จำนวนคน ตอนนี้แต่ละคนสามารถโสดอยู่ได้ หรืออยู่ในคู่ได้ เราต้องหาจำนวนวิธีทั้งหมดที่คนเหล่านี้สามารถจับคู่ได้
Input : 3 Output: 4 Explanation : [{1}, {2}, {3}], [{1, 2}, {3}], [{1}, {2, 3}], [{1, 3}, {2}] 4 วิธีนี้คือวิธีเดียวที่เราสามารถจับคู่คน 3 คนได้
Input : 6 Output : 76
วิธีการแก้ปัญหา
ในวิธีนี้ เราจะใช้สูตรของ Young Tableau เพื่อคำนวณปัญหานี้ สูตรที่เราจะใช้คือ
A[n] = A[n-1] + (n-1) * A[n-2]
ตัวอย่าง
โค้ด C++ สำหรับวิธีการข้างต้น
#include <bits/stdc++.h>
using namespace std;
int Young_Tableau(int n){
int A[n + 1];
A[1] = 1;
A[2] = 2;
for (int i = 3; i <= n; i++) {
A[i] = A[i - 1] + (i - 1) * A[i - 2];
}
return A[n];
}
int main(){
int n = 6;
cout << Young_Tableau(n);
return 0;
}
ผลลัพธ์
76
คำอธิบายโค้ด
ในวิธีนี้ เราแค่ใช้สูตร Young Tableau ซึ่งต้องหาตัวเลขสองตัวก่อนหน้า ตอนนี้เราสามารถเก็บตัวเลขเหล่านี้ใน Array Index ได้ โดยการอ้างอิงดัชนี เราสามารถได้ค่าสำหรับสูตรของเรา และคำนวณคำตอบได้
สรุป
ในบทช่วยสอนนี้ เราแก้ปัญหาการหาจำนวนวิธีจับคู่คน เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์
