C++를 사용하여 사람을 페어링하는 방법의 수 찾기

현재 각 사람의 수가 n - 인 문제를 해결하려면 각 사람이 독신이거나 쌍으로 존재할 수 있으므로 이 사람들이 쌍을 이루는 방법의 총 수를 찾아야 합니다.

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

위 코드 설명

위의 접근 방식에서는 우리가 찾아야 하는 Young Tableau에 대한 공식을 적용하기만 하면 됩니다. 앞의 두 숫자. 이제 이 숫자를 배열 인덱스에 저장할 수 있습니다. 구독하면 공식에 대한 값을 얻을 수 있으므로 답을 계산합니다.

결론

이 튜토리얼에서는 사람들을 짝을 이루는 여러 방법을 찾기 위해 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.