C++を使用して人々をペアリングする方法の数を見つける

n −現在、各人の人数が1人またはペアで存在する可能性があるという問題を解決するには、これらの人をペアにする方法の総数を見つける必要があります。

Input : 3

Output: 4

Explanation : [ {1}, {2}, {3},], [{1, 2}, {3}], [{1}, {2, 3}], [{1, 3}, {2}] these four ways are the only ways we can pa up these 3 people.

Input : 6

Output : 76

解決策を見つけるためのアプローチ

このアプローチでは、 Young Tableauの式を使用します。 この問題を計算するために使用する式は-

A[n] = A[n-1] + (n-1) * A[n-2]

例

上記のアプローチのC++コード

#include <bits/stdc++.h>
using namespace std;
int Young_Tableau(int n){
    int A[n + 1];// To store the answer.
    A[1] = 1; // initial values
    A[2] = 2; // initial values
    for (int i = 3; i <= n; i++) { // using the formula of "Young Tableau" to calculate our answer
        A[i] = A[i - 1] + (i - 1) * A[i - 2];
    }
    return A[n]; // returning the answer
}
int main(){
    int n = 6;
    cout << Young_Tableau(n);
    return 0;
}

出力

76

上記のコードの説明

上記のアプローチでは、見つける必要のあるYoungTableauの式を適用するだけです 前の2つの数字。これで、これらの数値を配列インデックスに格納できます。サブスクライブすることで、数式の値を取得できるため、回答を計算します。

結論

このチュートリアルでは、問題を解決して、人をペアにするいくつかの方法を見つけます。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。