C++での友達ペアリングの問題

この問題では、グループ内の友達の数を示す正の整数Nが与えられます。私たちの仕事は、FriendsPairingの問題を解決するためのプログラムを作成することです。

グループの各友達は、独身のままにすることも、他の1人の友達とペアにすることもできます。グループの各友達のペアリングは1回だけ実行できます。

問題を理解するために例を見てみましょう

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}

ソリューションアプローチ

この問題を解決する1つの方法は、グループのn人の生徒の可能なすべてのペアリングを取得するための一般式を見つけることです。

グループにn人の友達がいるとしましょう。そして、これらの友達がペアになる方法はf（n）です。

グループの各友達は、独身でいることも、グループ内の別の友達とペアを組むこともできます。それぞれの場合の出力を見てみましょう。

• ケース1 − n番目の友人は独身でいることを選択し、グループの1人のメンバーが減らされ、次の再帰は（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

問題を解決するもう1つの方法は、指定されたソリューションに適合するようにフィボナッチ系列を最適化することです。

例

ソリューションの動作を説明するプログラム

#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