ในโจทย์นี้ เราได้รับการแสดงผลแบบไบนารีของจำนวนหนึ่ง และเราต้องหาการแสดงผลแบบไบนารีของจำนวนก่อนหน้า นั่นคือ จำนวนที่ได้หลังจากลบ 1 จากจำนวนที่กำหนด
การแสดงผลแบบไบนารี ของจำนวนคือการเปลี่ยนฐานของจำนวนเป็นฐาน 2 และแสดงจำนวนโดยใช้แค่ 0 หรือ 1
เช่น การแสดงผลแบบไบนารีของ 23 คือ 10111
ที่นี่ เราจะได้รับจำนวน สมมติว่า n ในรูปแบบไบนารี และเราต้องหาการแสดงผลแบบไบนารีของ n-1
เพื่อแก้ปัญหานี้ เราต้องรู้พื้นฐานการลบแบบไบนารี มาดูว่าจะเกิดอะไรขึ้นเมื่อลบ 1 จาก 0 หรือ 1 ในรูปแบบไบนารี: 0 - 1 = 1 + 1 carry จากบิตถัดไป, 1 - 1 = 0
มาดูตัวอย่างเพื่อเข้าใจปัญหาให้ดีขึ้น
Input : 101101100 Output : 101101011 Explanation : (101101100)2 Is the binary representation of 364. The number preceding it is 363 whose binary representation is (101101011)2 . we have used binary subtraction here and subtracted (1)2 from the binary representation of the number to yield the result .
มาดูตรรกะเบื้องหลังโปรแกรมนี้และออกแบบอัลกอริทึมจากตรรกะของเรา ที่นี่เราต้องลบ 1 จากการแสดงผลไบนารีของจำนวน สำหรับสิ่งนี้ เราจะเริ่มจากขวาและพลิก 0 ทั้งหมดเป็น 1 จนกว่าจะเจอ 1 เมื่อเจอ 1 เราจะพลิก 1 นั้นเป็น 0 และคืนค่าผลลัพธ์สุดท้าย
อัลกอริทึม
ขั้นตอนที่ 1 : เริ่มจากขวาไปซ้าย คือ n-1 ถึง 0 ขั้นตอนที่ 2 : หากเจอ 1 ให้เปลี่ยนเป็น 0 และ break ขั้นตอนที่ 3 : หากเจอ 0 ให้เปลี่ยนเป็น 1 ขั้นตอนที่ 4 : พิมพ์อาร์เรย์
ตัวอย่าง
การนำไปใช้โปรแกรมของอัลกอริทึมข้างต้น −
#include <bits/stdc++.h> using namespace std; string previousNumber(string num) { int n = num.size(); if (num.compare("1") == 0) return "0"; int i; for (i = n - 1; i >= 0; i--) { if (num.at(i) == '1') { num.at(i) = '0'; break; } else num.at(i) = '1'; } if (i == 0) return num.substr(1, n - 1); return num; } int main() { string number = "1011011000"; cout<<"the Binary representation of the number is "<<number<<endl; cout<<"Binary representation of previous number is "<<previousNumber(number); return 0; }ผลลัพธ์
The Binary representation of the number is 1011011000 Binary representation of previous number is 1011010111
