Écrit en C++, trouver le nombre de relations réflexives sur un ensemble

Dans cet article, nous expliquerons comment trouver des relations réflexives sur un plateau. Dans ce problème, on nous donne un nombre n et un ensemble de n nombres naturels, et nous devons déterminer le nombre de relations réflexives.

Relation réflexive - Si pour tout 'a' de l'ensemble A, (a, a) appartient à la relation R, alors la relation R est dite être une relation réflexive sur l'ensemble A. Par exemple -

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 ) }

Par conséquent, si pour chaque élément a ∈ A, il y a (a, a) ∈ R, alors la relation R est réflexive.

Méthode de solution

Le nombre de relations réflexives sur l'ensemble des éléments peut être calculé par la formule 2n2−n. Cette formule générale s'obtient en comptant le nombre de relations réflexives d'entiers.

Exemple

#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;
}

Sortie

Number of reflexive relations on set: 1

Explication du programme ci-dessus

Ce programme est facile à comprendre car nous prenons simplement l'entrée de l'utilisateur et la mettons dans la formule 2n2−n nous utilisons left Utiliser l'opérateur de décalage "

Conclusion

Dans cet article, nous avons abordé un problème concernant le nombre de relations réflexives sur les ensembles. Nous avons discuté de moyens simples de résoudre un problème donné et les mathématiciens ont dérivé une formule pour compter le nombre de relations réflexives.

Nous avons également appris à écrire un programme pour ce problème en C++, avec une complexité temporelle de O(1). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et d'autres langages.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!