ลบหนึ่งบิตจากเลขฐานสองเพื่อรับค่าสูงสุดใน C++

อภิปรายปัญหาที่เราได้รับเลขฐานสอง เราต้องลบออกเล็กน้อยเพื่อให้จำนวนที่เหลือควรเป็นจำนวนสูงสุดของตัวเลือกอื่น ๆ ทั้งหมดเช่น

Input : N = 1011
Output: 111
Explanation: We need to remove one bit so removing 0 bit will give a maximum number than removing any 1’s bit. 111 > 101, 011.

Input: 111
Output: 11
Explanation: Since all the bits are 1 so we can remove any bit.

แนวทางในการหาแนวทางแก้ไข

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

การใช้กำลังเดรัจฉานจะให้จำนวนผลลัพธ์สูงสุด กล่าวคือ โดยเอาแต่ละบิตออกทีละรายการ เปรียบเทียบผลลัพธ์ที่ต่างกัน และรับผลลัพธ์สูงสุด

แต่มี แนวทางที่มีประสิทธิภาพ . ประการหนึ่ง ที่ใช้งานได้ กล่าวคือ ถ้าเราเอาบิตที่ซ้ำซ้อนน้อยที่สุดออก

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

วิธีที่มีประสิทธิภาพจะมีผลน้อยที่สุดกับจำนวนผลลัพธ์

• ขั้นแรก สำรวจผ่านบิตจากทางขวา

• ค้นหา 0 และลบออกจากเคาน์เตอร์แรก

• หากไม่พบ 0 ให้ลบบิตออก

ตัวอย่าง

รหัส C++ สำหรับแนวทางที่มีประสิทธิภาพ

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str = "1011";
    bool flag = false;
    int n = str.length();
    // Initialising new array for
    char res[n - 1];
    int j = 0;
    // traversing through the binary number from right.
    for (int i = 0; j < n - 1; i++) {
        // if 0 is found then skip it.
        if (str[i] == '0' && flag == false) {
            flag = true;
            continue;
        }
        else
            res[j++] = str[i];
    }
    // printing the resulting string.
    cout << "Maximum number: " << res;
    return 0;
}

ผลลัพธ์

Maximum number: 111

คำอธิบายของโค้ดด้านบน

• ตัวแปรแฟล็กถูกใช้เพื่อกำจัด 0 ตัวเดียวเท่านั้น

• res array อักขระถูกเตรียมใช้งานเพื่อเก็บหมายเลขผลลัพธ์

• ลูปจะทำงานจนถึง n-1 เพราะเราต้องเก็บองค์ประกอบที่น้อยกว่าจำนวนเดิมหนึ่งรายการ

บทสรุป

ในบทช่วยสอนนี้ เราได้พูดถึงการค้นหาจำนวนสูงสุดหลังจากลบหนึ่งบิตออกจากมัน เราได้หารือถึงสองแนวทางในการแก้ปัญหานี้

นอกจากนี้เรายังเขียนโค้ด C++ เช่นเดียวกัน ซึ่งเราสามารถเขียนในภาษาอื่นๆ เช่น C, Java, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์