数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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** - 第 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
递归方法实现解决方案
示例
程序说明了我们解决方案的工作原理
#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
更新于: 2022年2月1日
526 次查看
广告