数据结构
网络
关系数据库管理系统 (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 次浏览
广告