ในปัญหานี้ เราได้รับจำนวนเต็มบวก N แสดงจำนวนเพื่อนในกลุ่ม ภารกิจของเราคือการสร้างโปรแกรมแก้ ปัญหาจับคู่เพื่อน (Friends Pairing Problem)
แต่ละเพื่อนในกลุ่มสามารถอยู่คนเดียวหรือจับคู่กับอีกเพื่อนหนึ่งได้ การจับคู่ของแต่ละเพื่อนในกลุ่มสามารถทำได้เพียงครั้งเดียว
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: n = 3 Output: 4 Explanation: สมมติว่า 3 สมาชิกคือ A, B และ C การจับคู่ได้ดังนี้ : {A}, {B}, {C} {A, B}, {C} {A, C}, {B} {A}, {B, C}
วิธีการแก้ปัญหา
วิธีหนึ่งในการแก้ปัญหาคือการหาสูตรทั่วไปเพื่อรับการจับคู่ที่เป็นไปได้ทั้งหมดสำหรับ n นักเรียนในกลุ่ม
สมมติว่าเรามีเพื่อน n คนในกลุ่ม และวิธีที่เพื่อนเหล่านี้สามารถจับคู่ได้คือ f(n)
แต่ละเพื่อนในกลุ่มสามารถอยู่คนเดียวหรือจับคู่กับอีกเพื่อนหนึ่งในกลุ่มได้ มาดูผลลัพธ์ในแต่ละกรณี
กรณี 1 - เพื่อนคนที่ N เลือกอยู่คนเดียว สมาชิกหนึ่งในกลุ่มลดลง การเรียกซ้ำครั้งต่อไปจะเป็นจาก (N-1) คือ f(N-1)
กรณี 2 - เพื่อนคนที่ N เลือกจับคู่กับอีกสมาชิกหนึ่ง (N-2) สมาชิกเหลือ และการเรียกซ้ำครั้งต่อไปจะเป็นจาก N-2 เรียกซ้ำเป็น f(N) = f(N-1) + (N-1) * f(N-2)
มีหลายวิธีที่เราสามารถแก้ได้
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <iostream> using namespace std; int countGroupPairing(int N){ int dpArr[N + 1]; for (int i = 0; i <= N; i++) { if (i <= 2) dpArr[i] = i; else dpArr[i] = dpArr[i - 1] + (i - 1) * dpArr[i - 2]; } return dpArr[N]; } int main(){ int N = 6; cout<<"The number of friends in the group is "<<N<<endl; cout<<"The total number of possible pairs is "<<countGroupPairing(N); return 0; }
เอาต์พุต
The number of friends in the group is 6 The total number of possible pairs is 76
วิธีการเรียกซ้ำ (Recursive approach) ในการใช้งานคำตอบ
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <bits/stdc++.h> using namespace std; int dpArr[1000]; int countGroupPairing(int N){ memset(dpArr, -1, sizeof(dpArr)); if (dpArr[N] != -1) return dpArr[N]; if (N > 2) return dpArr[N] = countGroupPairing(N - 1) + (N - 1) * countGroupPairing(N - 2); else return dpArr[N] = N; } int main(){ int N = 6; cout<<"The number of friends in the group is "<<N<<endl; cout<<"The total number of possible pairs is "<<countGroupPairing(N); return 0; }
เอาต์พุต
The number of friends in the group is 6 The total number of possible pairs is 76
อีกวิธีหนึ่งในการแก้ปัญหา คือการเพิ่มประสิทธิภาพชุดฟีโบนัชชีให้เข้ากับคำตอบที่กำหนด
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <bits/stdc++.h> using namespace std; int dpArr[1000]; int countGroupPairing(int N){ int val1 = 1, val2 = 2, val3 = 0; if (N <= 2) { return N; } for (int i = 3; i <= N; i++) { val3 = val2 + (i - 1) * val1; val1 = val2; val2 = val3; } return val3; } int main(){ int N = 6; cout<<"The number of friends in the group is "<<N<<endl; cout<<"The total number of possible pairs is "<<countGroupPairing(N); return 0; }
เอาต์พุต
The number of friends in the group is 6 The total number of possible pairs is 76
