Menggunakan pengaturcaraan C++, cari bilangan penyelesaian kepada persamaan n = x + n * x

Dalam artikel ini kita akan mencari bilangan penyelesaian kepada persamaan n = x + n ⊕ x, iaitu kita perlu mencari bilangan kemungkinan nilai x untuk nilai n yang diberikan supaya n = x + n ⊕ x, dengan ⊕ mewakili operasi XOR.

Sekarang kita akan membincangkan maklumat lengkap tentang bilangan penyelesaian n = x + n ⊕ x dengan contoh yang sesuai.

Kaedah brute force

Kita hanya boleh menggunakan kaedah brute force untuk mencari bilangan penyelesaian, iaitu untuk nilai n yang diberikan, kita menggunakan setiap nilai integer x bermula dari 0 dan mengesahkan bahawa persamaan itu berpuas hati, nilai daripada x hendaklah kurang daripada atau sama dengan n, kerana menambah nilai yang lebih besar daripada n kepada (n ⊕ x) tidak akan mengembalikan n sebagai jawapan.

Contoh

Cari nilai x sehingga n = 3 dipegang? Terjemahan bahasa Cina

   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

Contoh

ialah:

Contoh

#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

Ini ialah program C++ mudah yang mencari bilangan penyelesaian untuk n = x + n ⊕ x dengan menggunakan kaedah kekerasan.

Kaedah yang cekap

Dalam kaedah ini, jika kita melihat bentuk binari n, kita perlu mencari bilangan bit yang ditetapkan kepada 1, dan mengikut persamaan, kita boleh mengatakan bahawa jika n ditetapkan , maka x adalah sama ada ditetapkan, sama ada n ⊕ x ditetapkan kerana 1 ⊕ 1 = 0. Ini bermakna n ⊕ x tidak ditetapkan, jadi sekarang kita boleh membuat kesimpulan bahawa untuk setiap bit set dalam n, bilangan pilih atur ialah 2^(bilangan bit set). Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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

Output

Number of possible solutions : 4

Kerumitan Program

Kerumitan masa pendekatan ini ialah O(n), kerana kami menggunakan kaedah yang lebih cekap di sini untuk meningkatkan kecekapan program.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah untuk mencari beberapa penyelesaian −

n = x + n ⊕ x Kami juga mempelajari program C++ untuk masalah ini dan lengkap pendekatan yang kami gunakan untuk menyelesaikan masalah ini Kami boleh menulis program yang sama dalam bahasa lain seperti C, java, python, dan bahasa lain Semoga artikel ini membantu.

Atas ialah kandungan terperinci Menggunakan pengaturcaraan C++, cari bilangan penyelesaian kepada persamaan n = x + n * x. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!