Trong bài toán này, chúng ta được cung cấp một giá trị nguyên N. nhiệm vụ của chúng ta là tạo một chương trình để tìm Số phụ tùng tiếp theo.
Số thưa thớt là một loại số đặc biệt có chuyển đổi nhị phân không chứa bất kỳ số 1 liền kề nào.
Example: 5(101) , 16(10000)
Mô tả sự cố - Với số N đã cho, ta cần tìm số nhỏ nhất lớn hơn N là số thưa.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 7
Đầu ra
8
Giải thích
Số nhị phân của 8 là 1000 khiến nó trở thành số thưa thớt nhỏ nhất lớn hơn n.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là kiểm tra tất cả các số lớn hơn N. và dừng lại cho đến khi chúng tôi tìm thấy số thưa thớt đầu tiên.
Đối với điều này, chúng ta cần lặp lại từ N đến vô cùng và đối với mỗi số kiểm tra xem nó có phải là một số thưa thớt hay không. Nếu có, hãy phá vỡ vòng lặp, nếu không, hãy tiếp tục.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The number is 564 The next Sparse Number is 576
Cách tiếp cận hiệu quả
Một cách tiếp cận hiệu quả đối với vấn đề là sử dụng các bit của số. Đối với điều này, chúng tôi sẽ tìm nhị phân của số và thao tác các bit nơi xảy ra kề. Chuyển từ Bit ít quan trọng nhất sang Bit quan trọng nhất, khi chúng ta gặp một cặp số 1 với nhau, chúng tôi sẽ thay thế cả hai số 1 bằng số 0 và tạo bit tiếp theo là 1. Và làm điều này cho đến khi chúng tôi đạt được MSB. Và sau đó chuyển đổi số nhị phân thành số thập phân, đó là kết quả của chúng tôi.
Hãy lấy một ví dụ ở đây,
N =52
Nhị phân của số là 110100
Chúng tôi sẽ đi ngang từ LSB và tìm cặp số 1 liên tiếp đầu tiên trong hệ nhị phân. Đó là 11 0100 phần được đánh dấu. Sau đó, chúng tôi sẽ thay thế cả số 1 bằng số 0 và thêm một số vào bit tiếp theo. Điều này tạo nên số 1000000, có chuyển đổi nhị phân là 64 .
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The number is 564 The next Sparse Number is 576