資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++查詢下一個稀疏數
在這個問題中，我們給定一個整數N。我們的任務是建立一個程式來查詢下一個稀疏數。
稀疏數是一種特殊的數字，其二進位制轉換不包含任何相鄰的1。
Example: 5(101) , 16(10000)
問題描述 - 對於給定的數字N，我們需要找到大於N且最小的稀疏數。
讓我們舉個例子來理解這個問題：
輸入
N = 7
輸出
8
解釋
8的二進位制是1000，這使其成為大於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。然後將二進位制數轉換回十進位制數，這就是我們的結果。
讓我們來看一個例子：
N = 52
該數字的二進位制表示為110100
我們將從LSB開始遍歷，並在二進位制中找到第一對連續的1。它是**11**0100（突出顯示的部分）。然後，我們將這兩個1替換為0，並將下一位加1。這使得數字變為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
更新於：2021年3月13日
306 次瀏覽
廣告