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 に入力するだけなので、簡単に理解できます。 、および式の計算に左シフト "<<"演算子を使用しています。このコードの時間計算量は、nのサイズが大きくなるにつれて遅くなるO（1）です。

結論

この記事では、問題を解決して、集合上の反射関係の数を見つけます。反射関係の数を計算する式が数学者によって導き出されるので、与えられた問題を解決するための簡単なアプローチについて議論しました。

また、この問題のC ++プログラムを学習しました。これにより、時間計算量がO（1）のソリューションが見つかりました。同じプログラムをC、Java、Python、その他の言語などの他の言語で作成できます。