C++ 中的朋友配对问题
c++server side programmingprogramming更新于 2025/5/31 9:52:17
在此问题中，我们给出一个正整数 N，表示一个组中的朋友数量。我们的任务是创建一个程序来解决朋友配对问题
。该组的每个朋友都可以保持单身，也可以与另一个朋友配对。小组中的每个朋友只能配对一次。
让我们举一个例子来理解这个问题
输入:n = 3
输出:4
解释:
假设小组的 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<<"该群组中的朋友数量为 "<<N<<endl;
cout<<"可能配对的总数为 "<<countGroupPairing(N);
return 0;
}
输出
该群组中的朋友数量为 6 可能配对的总数为 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<<"该群组中的朋友数量为 "<<N<<endl;
cout<<"可能配对的总数为 "<<countGroupPairing(N);
return 0;
}
输出
该群组中的朋友数量为 6 可能配对的总数为 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<<"群组中好友数量为"<<N<<endl;
cout<<"可能配对总数为"<<countGroupPairing(N);
return 0;
}
输出
群组中好友数量为 6 可能配对总数为 76
