ในการแก้ปัญหาที่ n − จำนวนคนที่ตอนนี้แต่ละคนสามารถเป็นโสดหรืออยู่เป็นคู่ได้ เราจำเป็นต้องค้นหาจำนวนวิธีทั้งหมดที่สามารถจับคู่คนเหล่านี้ได้
Input : 3
Output: 4
Explanation : [ {1}, {2}, {3},], [{1, 2}, {3}], [{1}, {2, 3}], [{1, 3}, {2}] these four ways are the only ways we can pa up these 3 people.
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];// To store the answer.
A[1] = 1; // initial values
A[2] = 2; // initial values
for (int i = 3; i <= n; i++) { // using the formula of "Young Tableau" to calculate our answer
A[i] = A[i - 1] + (i - 1) * A[i - 2];
}
return A[n]; // returning the answer
}
int main(){
int n = 6;
cout << Young_Tableau(n);
return 0;
} ผลลัพธ์
76
คำอธิบายของโค้ดด้านบน
ในแนวทางข้างต้น เราเพียงแค่ใช้สูตรสำหรับ Young Tableau ที่เราต้องหา สองตัวเลขก่อนหน้า ตอนนี้เราสามารถเก็บตัวเลขเหล่านี้ไว้ในดัชนีอาร์เรย์ได้ การสมัครรับข้อมูลทำให้เราได้ค่าสำหรับสูตรของเรา และด้วยเหตุนี้เราจึงคำนวณคำตอบของเรา
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ปัญหาเพื่อค้นหาวิธีจับคู่ผู้คนหลายวิธี นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
