ปัญหาการจับคู่เพื่อนใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวก N ซึ่งแสดงถึงจำนวนเพื่อนในกลุ่ม งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหา ปัญหาการจับคู่เพื่อน

เพื่อนแต่ละคนในกลุ่มสามารถเป็นโสดหรือจับคู่กับเพื่อนอีกคนหนึ่งได้ การจับคู่ของเพื่อนแต่ละคนในกลุ่มสามารถทำได้เพียงครั้งเดียว

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input: n = 3
Output: 4
Explanation:
Let’s say the 3 members of the group are A, B and C.
The pairing can be done as :
{A}, {B}, {C}
{A, B}, {C}
{A, C}, {B}
{A}, {B, C}

แนวทางการแก้ปัญหา

วิธีหนึ่งในการแก้ปัญหาคือการหาสูตรทั่วไปเพื่อให้ได้การจับคู่ที่เป็นไปได้ทั้งหมดสำหรับนักเรียน n ของกลุ่ม

สมมติว่าเรามีเพื่อน n คนในกลุ่ม และวิธีที่เพื่อนเหล่านี้สามารถจับคู่กันได้คือ f(n)

เพื่อนแต่ละคนในกลุ่มสามารถอยู่คนเดียวหรือจับคู่กับเพื่อนคนอื่นในกลุ่มได้ มาดูผลลัพธ์กันในแต่ละกรณีกันครับ

• กรณีที่ 1 − เพื่อนคนที่ 9 เลือกที่จะอยู่คนเดียว สมาชิกจากกลุ่มหนึ่งลดลง การเรียกซ้ำครั้งต่อไปจะมาจาก (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

วิธีการแบบเรียกซ้ำเพื่อใช้โซลูชัน

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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