首页 > 试题广场 >

n从1开始，每个操作可以选择对n加1或者对n加倍。若想获得整

[单选题]
n从1开始，每个操作可以选择对n加1或者对n加倍。若想获得整数2013，最少需要多少个操作：( ) 
  • 18
  • 24
  • 21
  • 不可能
查看答案及解析
添加回答
在午休的里根很高大头像 在午休的里根很高大
最好用位运算的方法
乘2代表左移一位，加1是最低位加1，例如：
从1到5可以先将5转化为二进制101,1可以通过以下几个步骤到101：
1→10→100→101
即变化3次可以从1到5，观察规律，5的二进制表示中除最高位时每个1次数加2，每个0次数加1
2013可以表示为11111011101，总共有8个1和2个0
所以需要8*2+2次，即为18次
发表于 2015-08-27 15:34:23 回复(7)
牛客851824号头像 牛客851824号
我觉得一次就行了，2013倍
发表于 2015-09-10 22:28:26 回复(2)
corny813头像 corny813
A是对的。
逆向推导： 由2013-1=2012，2012/2=1006（由于只允许+1和乘2的操作，逆向即为-1和除以2）
1006/2=503 ，503-1=502 ……一直下去，遇到偶数除以2，遇到奇数-1

最后得到结果操作序列为：1*2=2，2+1=3  （以下只用结果数表示）
2，3，6，7，14，15，30，31，62，124，125，250，251，502，503，1006，2012，2013


发表于 2015-08-26 22:04:40 回复(0)
牛客837763号头像 牛客837763号
風待-睡郷鈴慕提示用位移算法，思路非常好，解释稍微不太详细，我补充下：
把n表示成二进制数时，首位的1当做是数字初始值1；
例如10，是有1左移1位，需要一次操作；11是由1左移一位，然后加1，需要两次操作。
因此，二进制n中，除首位以外，“1”需要两次操作，“0”需要一次操作。
若n由a为1,b位0，则需要操作数为（a-1）*2+b;
发表于 2015-08-28 19:33:50 回复(0)
DOREEN头像 DOREEN
逆推，奇数减一，偶数除二
发表于 2015-08-30 10:10:21 回复(0)
阳光下的水滴头像 阳光下的水滴
2013可以表示为11111011101，一共11位，9个1.故需要左移10次，加8次1，共18次操作。
发表于 2017-09-25 22:41:53 回复(0)
陈芳n头像 陈芳n
2013=2012+1
2012=2*1006=（502+1）*2*2
502=251*2=（250+1）*2
250=125*2=（124+1）*2
124=62*2=2*2*31=（30+1）*2*2
30=15*2=（14+1）*2
14=7*2=（6+1）*2
6=3*2=（2+1）*2
2=1*2
总共18步

发表于 2022-09-08 20:16:15 回复(0)
聊寂园头像 聊寂园
由题中条件可知道对当前数的操作有两种
① 当前数*2
② 当前数+1
两种解法
① 直接逆推法
2013    2012    1006    503    502    251    250    125    124    62    31    30    15    14    7    6    3    2    1
（1    10    11    110    111    1110    1111    11110    11111    111110    1111100    1111101    11111010    11111011    111110110    111110111    1111101110    11111011100    11111011101）
由此可知道需要18步
②二进制分析法，由对当前数的操作可以知道，加倍即是左移1位，而加1操作是直接末尾变为1
分析一下由1到5,
5的二进制101   变化为
1    10（左移一位，即加倍） 101（加1操作） 需要2次操作
由 1到15
15的二进制 1110
1110  <---111   <----110   <---11  <----10  <--1 需要5次操作
分析可知，转换为二进制数后，除了首位1之外，其余位如果是1，则必然是经过两次操作所得（先加倍，后加1），其余位是0则通过一次操作可得（加1操作）
则设给定数A的二进制中有a个1，b个0，则需要操作的次数为（a-1）*2+b
2013=11111011101  所以a=9，b=2   (9-1)*2+2=18次操作   
发表于 2018-07-22 09:38:26 回复(0)
怪我过分萌头像 怪我过分萌
同样按照奇数-1，偶数/2逆推
2013  2012 1006  503  502  251  250  125  124  62  31  30  15  14  7  6  3  2  
18个
发表于 2017-08-08 10:03:05 回复(0)
┕純℡屬虛构头像 ┕純℡屬虛构
逆推
发表于 2016-09-07 20:54:19 回复(0)
guanjian头像 guanjian
考点:二进制
2013可以表示为11111011101-> 1111101110:需要先-1再右移，总共两次
因此：除去最高位1之外，含8个1,2个0，总共需要8*2+2
发表于 2015-09-12 15:00:51 回复(0)
荔枝树头像 荔枝树
2013 = 11111011101b  = 2^10 + 1111011101 （8个1）
10 + 8 = 18
发表于 2015-08-28 13:37:39 回复(1)
提交观点

问题信息

智力题
来自：英特尔2016软件类研...
难度：
12条回答 22037浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号