ในโจทย์นี้ เราได้รับการแสดงผลแบบไบนารีของจำนวนหนึ่ง และเราต้องหาการแสดงผลแบบไบนารีของจำนวนถัดไป นั่นคือ จำนวนที่ได้หลังจากบวก 1 เข้ากับจำนวนที่กำหนด
การแสดงผลแบบไบนารี ของจำนวนคือการเปลี่ยนฐานของจำนวนเป็นฐาน 2 และแสดงจำนวนโดยใช้แค่ 0 หรือ 1
เช่น การแสดงผลแบบไบนารีของ 14 คือ 1110
ที่นี่ เราจะได้รับจำนวน สมมติว่า n ในรูปแบบไบนารี และเราต้องหาการแสดงผลแบบไบนารีของ n+1
เพื่อแก้ปัญหานี้ เราต้องรู้พื้นฐานการบวกแบบไบนารี มาดูว่าจะเกิดอะไรขึ้นเมื่อบวก 1 เข้ากับ 0 หรือ 1 ในรูปแบบไบนารี
0 + 1 = 1
1 + 1 = 10
ตัวอย่าง
มาดูตัวอย่างวิธีแก้ปัญหาข้างต้น
Input: 010010111 Output: 010011000 Explanation : (010010111)2 is the binary representation of 152 and the next number will be 153 whose binary representation is (010011000)2. We will use binary addition here and add binary (1)2 to the binary representation of the number.
จากตัวอย่างข้างต้น เราเห็นว่าเมื่อบวกไบนารี 1 เข้ากับจำนวน 1 ทั้งหมดตั้งแต่ขวาสุดจะถูกแปลงเป็น 0 จนกว่าจะเจอ 0 แรก และ 0 นั้นจะถูกพลิกเป็น 1 ตอนนี้มาสร้างอัลกอริทึมสำหรับตรรกะนี้
อัลกอริทึม
ขั้นตอนที่ 1 : เริ่มจากขวาไปซ้าย คือ n-1 ถึง 0 ขั้นตอนที่ 2 : หากเจอ 0 ให้เปลี่ยนเป็น 1 และ break ขั้นตอนที่ 3 : หากเจอ 1 ให้เปลี่ยนเป็น 0 ขั้นตอนที่ 4 : เมื่อไม่เจอ 0 เลย ให้เพิ่ม 1 ไปที่จุดเริ่มต้นของอาร์เรย์ ขั้นตอนที่ 5 : พิมพ์อาร์เรย์
ตัวอย่าง
ตอนนี้ มาดูการนำไปใช้โค้ดของอัลกอริทึมนี้
#include <bits/stdc++.h> using namespace std; string nextBinary(string num) { int l = num.size(); int flag = 0 ; for (int i=l-1; i>=0; i--) { if (num.at(i) == '0') { num.at(i) = '1'; flag = 1; break; } else num.at(i) = '0'; } if (flag < 0) num = "1" + num; return num; } int main() { string number = "0111010111"; cout<<"The Binary representation of the number is "<<number<<endl; cout<<"Binary representation of next number is "<<nextBinary(number); return 0; }ผลลัพธ์
The Binary representation of the number is 0111010111 Binary representation of next number is 0111011000
