Trong bài toán này, chúng ta được cung cấp một số nguyên dương N biểu thị số lượng bạn bè trong một nhóm. Nhiệm vụ của chúng tôi là tạo một chương trình để giải quyết Vấn đề kết nối bạn bè.
Mỗi người bạn trong nhóm có thể vẫn độc thân hoặc có thể kết đôi với một người bạn khác. Việc ghép đôi của mỗi người bạn trong nhóm chỉ có thể được thực hiện một lần.
Hãy lấy một ví dụ để hiểu vấ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} Phương pháp tiếp cận giải pháp
Một phương pháp để giải quyết vấn đề là tìm một công thức chung để có được tất cả các phép ghép đôi có thể có cho n học sinh của nhóm.
Giả sử chúng ta có n người bạn trong nhóm. Và cách những người bạn này có thể kết đôi là f (n).
Mỗi người bạn trong nhóm có thể ở độc thân hoặc kết đôi với một người bạn khác trong nhóm. Hãy xem kết quả trong từng trường hợp.
-
Trường hợp 1 - Người bạn thứ N chọn ở độc thân, một thành viên trong nhóm bị giảm đi, lần đệ quy tiếp theo sẽ từ (N-1) tức là f (N-1).
-
Trường hợp 2 - Người bạn thứ N chọn ghép đôi với một thành viên khác, (N-2) thành viên vẫn còn và đệ quy tiếp theo sẽ từ N-2. Được gọi đệ quy là f (N) =f (N-1) + (N-1) * f (N-2)
Họ có nhiều cách có thể giải quyết vấn đề này.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The number of friends in the group is 6 The total number of possible pairs is 76
Cách tiếp cận đệ quy để triển khai giải pháp
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The number of friends in the group is 6 The total number of possible pairs is 76
Một phương pháp khác để giải quyết vấn đề, là bằng cách tối ưu hóa seriest fibonacci để phù hợp với giải pháp đã cho
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The number of friends in the group is 6 The total number of possible pairs is 76