À l'aide de la programmation C++, trouvez le nombre de solutions de l'équation n = x + n * x

Dans cet article nous trouverons le nombre de solutions de l'équation n = x + n ⊕ x, c'est-à-dire qu'il faut trouver le nombre de valeurs possibles de x pour une valeur n donnée telle que n = x + n ⊕ x, où ⊕ représente l'opération XOR.

Nous allons maintenant discuter des informations complètes sur le nombre de solutions de n = x + n ⊕ x avec des exemples appropriés.

Méthode de la force brute

On peut simplement utiliser la méthode de la force brute pour trouver le nombre de solutions, c'est à dire pour une valeur donnée de n, on applique chaque valeur entière de x en partant de 0 et on vérifie que l'équation est satisfaite, la valeur de x doit être inférieur ou égal à n, car l’ajout d’une valeur supérieure à n à (n ⊕ x) ne renverra jamais n comme réponse.

Exemple

Trouver une valeur de x telle que n = 3 est valable ? La traduction chinoise de

   n = x + n ⊕ x
Putting x = 0,
   3 = 0 + 3 ⊕ 0
3 ⊕ 0 = 3,
   3 = 3
   LHS = RHS(x = 0 satisfy the equation)
So, x = 0 is one of the solution

Example

est :

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 3, c=0;
    for (int x = 0; x <= n; ++x)// loop for giving value of x from 0 to n
        if (n == x + n ^ x)//checking if value of x satisfies the equation
            ++c;
    cout  << "Number of possible solutions : " << c;
    return 0;
}

Output

Number of possible solutions : 4

Il s'agit d'un simple programme C++ qui trouve le nombre de solutions pour n = x + n ⊕ x en appliquant des méthodes de force brute.

Méthode efficace

Dans cette méthode, si nous regardons la forme binaire de n, nous devons trouver le nombre de bits qui sont mis à 1, et selon l'équation, nous pouvons dire que si n est défini , alors x est soit est défini, soit n ⊕ x est défini car 1 ⊕ 1 = 0. Cela signifie que n ⊕ x n'est pas défini, nous pouvons donc maintenant conclure que pour chaque bit défini dans n, le nombre de permutations est de 2 ^ (nombre de bits définis). La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
int main (){
    int n = 3, no_of_setbits = 0;    // initialising n with value and taking count of set bits as 0
    while (n != 0){
        no_of_setbits = no_of_setbits + (n % 2);    // checking if num contains set bit.
        n = n / 2;
    }
    int result = 1 << no_of_setbits;    // calculating no. of possible solution with 2^setbits
    cout << " Number of possible solutions : " << result;
    return 0;
}

Sortie

Number of possible solutions : 4

Complexité du programme

La complexité temporelle de cette approche est O(n), car nous appliquons ici la force brute. Nous pouvons appliquer des méthodes plus efficaces. pour améliorer l'efficacité du programme.

Conclusion

Dans cet article, nous résolvons un problème pour trouver un certain nombre de solutions −

n = x + n ⊕ x Nous avons également appris le programme C++ pour ce problème et le programme complet. approche par laquelle nous avons résolu ce problème. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

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!