首页 > 试题广场 >

给定一个正整数n，求出0到n中有几个数满足其二进制表示不包含

[单选题]

给定一个正整数n，求出0到n中有几个数满足其二进制表示不包含连续的1。1<=n<=10^9。
样例：
输入：5，输出：5。
由于0到5的二进制表示分别为： 0； 1； 10； 11； 100； 101。这六个数中，只有3的二进制表示包含有连续的1，故答案为5。
问题：
若输入为6144，则输出为

```
980
```
```
364
```
```
377
```
```
610
```

查看正确选项

我只是想要个offer

6144 ==> 1100000000000 11后面11个0

分成两个排列问题

10后面排列11个0/1 其中需要保证01交叉, 所以可以看成在 x 个 0 中间插入 11 - x 个 1, 对每种情况有x+1个空位

另一种情况为12个0/11 排列，排列条件与上类似。

综合两种情况得出答案610

发表于 2018-09-10 00:59:01 回复(0)

offersHarvester

由于6144=1100000000000，由2个1和11个0组成。小于6144的可以分为三种情况：10/01/00（+11位）。

（1）对于00和10，由于第二位是1，所以前两位不会影响“连续的1”。使用插队法：例如，后面11个0里面有3个1时，其他的是8个0，8个0将产生9个空隙可以插入，于是位C₉^{3 。}依次类推，可以得到233种。（2）对于前两位位01，和01的来说，第三位只能是0.因此。后面的10位可以再次使用插队法。有144种。

最后，144+2*233=610.

发表于 2018-09-16 15:29:46 回复(0)

TaoHuang

6144=>1100000000000,后面11个0。需要判断小于6144而不重复的1的元素的个数，故把最高位分为三种情况：00，01，10。由此可知00的个数与10的个数一样————转为后面11位不连续出现1的情况，考虑1出现的个数得到结果为：C_11^0+C_11^1+C_10^2+C_9^3+C_8^4+C_7^5+C_6^6=233；而01情况————转为后面10位不连续出现1的情况,考虑1出现的个数得到结果为：C_10^0+C_10^1+C_9^2+C_8^3+C_7^4+C_6^5=144。
最终结果为：233+233+144=610

编辑于 2018-09-11 13:59:17 回复(0)

furr

我用代码算的。在前面大神分析的基础上加一点我自己的看法。

设 f1(m) 和 f0(m) ，分别表示第 x 位取 1 或 0 时，得到不含连续的 1 的数的个数

f1(m) 中，return f0(m-1)。 m位若设置为1，则(m-1)位只能取0

f0(m) 中，return f1(m-1)+f0(m-1)。 m位若设置为0，则(m-1)位可取1或0

一直执行到 f1(1) 或 f0(1)

【 f1(m) 和 f0(m) 传入的参数是根据输入取的，不同的输入得到的 m 不同（像5就不可以直接用这个方法），并且 m 不一定是这个数的总位数。现在只针对 6144 来讲，它最高位（第13位）可取 1 或 0，所以从它最高位开始考虑，m=13】

每次执行到 f1(1) 或 f0(1) ，即代表一个符合题意的数从第 m 位到第 1 位全被设置好了，则返回 1。

这样，设 i = f1(x)+f0(x) ，那么每执行到 f1(1) 或 f0(1) ，i 会加1，就可以算出所求数的个数

发表于 2018-09-13 20:46:39 回复(0)

tp_16b

不懂！！

发表于 2018-09-09 17:49:14 回复(0)

loveeee

6144 => 1100000000000 共13位

若有n位，令f(n)表示不包含连续1的个数 f(n)=f(n-1)+f(n-2) f(n-1)表示最高位为0的取法，f(n-2)表示最高位为1的取法

因此总数为 f(12)+f(11) f(12)表示最高位为0的取法，f(11)表示最高位为1的取法

初始值 f(1) = 2 （0,1） f(2)=3(00,01,10) 递推就行了

发表于 2018-09-13 11:34:53 回复(0)

坏坏62

这题真心不会求大神来分析一下解题思路。

发表于 2018-09-07 14:35:31 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师算法工程师 2018 迅雷 Java工程师

来自：2018迅雷校园招聘A...

上传者：小小

难度：

7条回答 124收藏 4591浏览

给定一个正整数n，求出0到n中有几个数满足其二进制表示不包含

问题信息

热门推荐

相关试题