C++ プログラミングを使用して、方程式 n = x + n * x の解の数を求めます。

この記事では、方程式 n = x n ⊕ x の解の数を見つけます。つまり、与えられた値 n に対して x の可能な値の数を見つける必要があります。 n = x n ⊕ x のようになります。ここで、⊕ は XOR 演算を表します。

ここで、n = x n ⊕ x の解の数について完全な情報を説明し、適切な例を示します。

ブルート フォース メソッド

ブルート フォース メソッドを使用して、解の数を見つけることができます。つまり、与えられた n の値に対して、0 から始まる x の各整数値を適用します。方程式を確認します。満足するには、x の値が n 以下である必要があります。n より大きい値を (n ⊕ x) に加算しても、n が答えとして返されることはありません。

例

n = 3 が成り立つような x の値を見つけますか?

   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

の中国語訳は次のとおりです。

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

これは、総当たり力を適用して n を見つける単純な C プログラムです。 Method = x n ⊕ x の解の数。

効率的な方法

この方法では、n のバイナリ形式を見ると、1 に設定されたビットの数を見つける必要があります。 1 ⊕ 1 = 0 であるため、n が設定されている場合は、x が設定されるか、n ⊕ x が設定されると言えます。これは、n ⊕ x が設定されていないことを意味するため、n の各設定ビットの順列数は 2^(設定ビットの数) であると結論付けることができます。

例

の中国語訳は次のとおりです:

Example

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

出力

Number of possible solutions : 4

プログラムの複雑さ

このアプローチの時間計算量は O(n) です。ここではブルート フォースを適用しているため、より効率的な方法を適用してプログラムの効率を向上させることができます。

結論

この記事では、次の問題を解決します。解の数を見つけます −

n = x n ⊕ x. また、この問題に対する C プログラムと、この問題を解決するための完全なアプローチも学びました。同じプログラムを他の言語でも書くことができます。 C、Java、Python、その他の言語として使用できます。この記事がお役に立てば幸いです。

以上がC++ プログラミングを使用して、方程式 n = x + n * x の解の数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。