ค้นหาจำนวนคำตอบของ n =x + n x โดยใช้ C++

ในบทความนี้ เราจะต้องหาจำนวนคำตอบของสมการ n =x + n ⊕ x นั่นคือ เราต้องหาจำนวนค่าของ x ที่เป็นไปได้ด้วยค่าที่กำหนด n ซึ่ง n =x + n ⊕ x โดยที่ ⊕ แทนการดำเนินการ XOR .

ตอนนี้เราจะพูดถึงข้อมูลทั้งหมดเกี่ยวกับจำนวนวิธีแก้ปัญหาของ n =x + n ⊕ x พร้อมตัวอย่างที่เหมาะสม

วิธีเดรัจฉาน

เราสามารถใช้วิธีเดรัจฉานง่ายๆ เพื่อหาจำนวนคำตอบ เช่น สำหรับค่าที่กำหนดของ n เราใช้ค่าจำนวนเต็มของ x ทุกค่าที่เริ่มจาก 0 และตรวจสอบว่าสมการตรงหรือไม่ ค่าของ x ควรน้อยกว่าหรือเท่ากับ n เพราะการบวกค่าที่มากกว่า n ด้วย (n ⊕ x) จะไม่คืนค่า n เป็นคำตอบ

ตัวอย่าง

ค้นหาค่า x หนึ่งค่าสำหรับ n =3 หรือไม่

   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

ตัวอย่าง

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

ผลลัพธ์

Number of possible solutions : 4

เป็นโปรแกรม C++ ง่ายๆ ในการหาจำนวนคำตอบของ n =x + n ⊕ x โดยใช้วิธี Brute force

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้ หากเรามองที่ n ในรูปแบบเลขฐานสอง เราต้องหาจำนวนบิตที่ถูกตั้งค่าเป็น 1 และดูที่สมการ เราสามารถพูดได้ว่าถ้าตั้งค่า n แล้ว x จะถูกตั้งค่าหรือ n ⊕ x จะถูกตั้งค่าเพราะ 1 ⊕ 1 =0 หมายความว่า n ⊕ x ไม่ได้ตั้งค่าไว้ ดังนั้นตอนนี้เราสามารถสรุปจำนวนการเรียงสับเปลี่ยนสำหรับทุกชุดบิตใน n นั่นคือ 2^(จำนวนเซตบิต )

ตัวอย่าง

#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 และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์