ในปัญหานี้ เราได้รับค่าจำนวนเต็ม N หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาหมายเลขสำรองถัดไป
จำนวนน้อย เป็นตัวเลขชนิดพิเศษที่การแปลงเลขฐานสองไม่มี 1 ตัวติดกัน
Example: 5(101) , 16(10000)
คำอธิบายปัญหา − สำหรับจำนวนที่กำหนด N เราจำเป็นต้องหาจำนวนที่น้อยที่สุดที่มากกว่า N ซึ่งเป็นจำนวนเบาบาง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 7
ผลลัพธ์
8
คำอธิบาย
เลขฐานสองของ 8 คือ 1,000 ซึ่งทำให้เป็นจำนวนเบาบางที่น้อยที่สุดที่มากกว่า n
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการตรวจสอบตัวเลขทั้งหมดที่มากกว่า N และหยุดจนกว่าเราจะพบจำนวนเบาบางตัวแรกของเรา
สำหรับสิ่งนี้เราต้องวนซ้ำจาก N ถึงอนันต์และสำหรับตัวเลขแต่ละตัวตรวจสอบว่าเป็นจำนวนเบาบางหรือไม่ ถ้าใช่ ให้ทำลายลูปไม่เช่นนั้นให้ดำเนินการต่อ
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
bool isSpareNumber(int N){
int currentBit = (N&1);
int nextBit ;
while (N!= 0){
nextBit = currentBit;
currentBit = (N&1);
N >>= 1;
if(nextBit == currentBit && nextBit == 1 && currentBit == 1)
return false ;
}
return true;
}
int findNextSparseNumber(int N) {
while(1){
if(isSpareNumber(N))
return N;
N++;
}
return -1;
}
int main() {
int N = 564;
cout<<"The number is "<<N<<endl;
cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
return 0;
} ผลลัพธ์
The number is 564 The next Sparse Number is 576
แนวทางที่มีประสิทธิภาพ
วิธีที่มีประสิทธิภาพในการแก้ปัญหาคือการจัดการบิตของตัวเลข สำหรับสิ่งนี้ เราจะค้นหาเลขฐานสองของตัวเลขและจัดการบิตที่เกิดความใกล้เคียงกัน ข้ามจากบิตที่มีนัยสำคัญน้อยที่สุดไปยังบิตที่มีนัยสำคัญมากที่สุด เมื่อเราพบคู่ของ 1 ร่วมกัน เราจะแทนที่ทั้ง 1 ตัวด้วย 0 และสร้างบิตถัดไป 1 และทำสิ่งนี้จนกว่าเราจะไปถึง MSB แล้วแปลงเลขฐานสองของตัวเลขกลับเป็นเลขฐานสิบซึ่งเป็นผลลัพธ์ของเรา
มาดูตัวอย่างกัน
ไม่มี =52
เลขฐานสองคือ 110100
เราจะสำรวจจาก LSB และหาคู่แรกของ 1 ที่ต่อเนื่องกันในไบนารี มันคือ 11 0100 ส่วนที่ไฮไลท์ จากนั้นเราจะแทนที่ทั้ง 1 ด้วย 0 และเพิ่มหนึ่งในบิตถัดไป ทำให้จำนวน 1000000 ที่มีการแปลงไบนารีเป็น 64 .
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
int findNextSparseNumber(int N) {
int spNum[16];
int n = 0;
while (N != 0) {
spNum[n] = (N&1);
n++;
N >>= 1;
}
n++;
int lastCorrectedBit = 0;
for (int i= 0 ; i< n; i++) {
if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1){
spNum[i+1] = 1;
for (int j=i; j>=lastCorrectedBit; j--)
spNum[j] = 0;
lastCorrectedBit = i+1;
}
}
int sparseNumber = 0;
for (int i =0; i<n-1; i++)
sparseNumber += spNum[i]*(1<<i);
return sparseNumber;
}
int main() {
int N = 564;
cout<<"The number is "<<N<<endl;
cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
return 0;
} ผลลัพธ์
The number is 564 The next Sparse Number is 576
