資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告