C++를 사용하여 집합의 재귀 관계 수 찾기

이 기사에서는 집합에서 반사 관계의 수를 찾는 방법에 대해 설명합니다. 이 문제에서는 수 n이 주어지고 n개의 자연수 집합에서 반사 관계의 수를 결정해야 합니다.

반사적 관계 - 집합 A의 관계는 모든 'a'가 집합 A에 속할 때 ( a, a )가 R에 속할 경우 재귀적 관계라고 합니다. 예를 들어 -

Input : x = 1
Output : 1
Explanation : set = { 1 }, reflexive relations on A * A :
{ { 1 } }

Input : x = 2
Output : 4
Explanation : set = { 1,2 }, reflexive relations on A * A :
   { ( 1, 1 ) , ( 2, 2 ) }
   { ( 1, 1 ), ( 2, 2 ), ( 1, 2 ) }
   { ( 1, 1 ), ( 2, 2 ), ( 1, 2 ), ( 2, 1 ) }
   { ( 1, 1 ), ( 2, 2 ), ( 2, 1 ) }

따라서 관계는 다음과 같은 경우 재귀적입니다. (a, a) ∈ R ∀ a ∈ A.

해결책을 찾기 위한 접근 방식

요소 집합에 대한 이 수의 반사 관계는 공식 2n2−n으로 해결할 수 있습니다. 이 일반식은 정수의 반사 관계의 수를 계산하여 생성됩니다.

예시

#include <iostream>
using namespace std;
int countReflexive(int n){
    int ans = 1 << (n*n - n);
    return ans;
}
int main(){
    int n ;
     cin >> n ; // taking input n from the user using std cin.
    int result = countReflexive(n); // calling function to calculate number of reflexive relations
    cout << "Number of reflexive relations on set: " << result ; // printing the answer
    return 0;
}

출력

Number of reflexive relations on set: 1

위 프로그램 설명

이 프로그램은 사용자로부터 입력을 받아 2n2−n 공식에 입력하기 때문에 이해하기 쉽습니다. , 그리고 수식을 계산하기 위해 왼쪽 시프트 "<<"연산자를 사용하고 있습니다. 이 코드의 시간 복잡도는 O(1)이며 n의 크기가 커질수록 느려집니다.

결론

이 기사에서는 집합의 재귀 관계 수를 찾는 문제를 해결합니다. 주어진 문제를 풀기 위한 간단한 접근 방식을 수학자가 도출한 반사 관계의 수를 계산하는 공식으로 논의했습니다.

우리는 또한 O(1)의 시간 복잡도를 가진 솔루션을 찾는 이 문제에 대한 C++ 프로그램을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.