首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
课程
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
B_k
2019-10-12 09:41
已编辑
沈阳航空航天大学
关注
已关注
取消关注
小白鼠问题(海明码)
小白鼠问题(海明码)
同学问了一道智力题:30瓶水,其中有一瓶毒药,小白鼠喝了毒药之后一天会死,求只有一天时间,用最少的小白鼠找出毒药?
很简单的我就想到了海明码:
数位
数值
C1
00001
C2
00010
C4
00100
C8
01000
C16
10000
\(C1=A1⊕A3⊕A5...⊕A29\)
\(C2=A2⊕A3⊕A5...⊕A30\)
\(C4=A4⊕A5⊕A5...⊕A30\)
\(C8=A8⊕A9⊕A10...⊕A30\)
\(C16=A16⊕A17⊕A518.⊕A30\)
我们将A看作水,将水从1编号到30。C作为混合水,也就是将对应编号的水混合成5瓶水,对应C16C8C4C2C1。每瓶水用一只小白鼠实验(残忍),哪只死亡,哪只对应编号为1。例如,C8,C4死亡,那么对应二进制数为0110,也就是十进制12,代表12号水有毒。
如果推广到n瓶水呢?当:
\[2^x-1>=n\]
时,可以满足需求。即:
\[x>=log_2 (n+1)\]
所需小白鼠数量为大于等于以2为底n+1的对数的最小整数。
但是这个是使用一切情况吗?当n=1时,x=1。但是实际上,一杯水不需要验证,他就是有毒的。所以我发现当:
\[n=2^x\]
时是一种特殊情况。例如,当n=32时,我可以把标号为32的水拿出,剩余31瓶可以按照如上方法求出答案,只是多出一种00000的情况,说明前31瓶水都无毒。那么拿出的32号水肯定有毒!
所以正确的公式应为:
\[2^x>=n\]
即:
\[x>=log_2 n\]
所需小白鼠数量为大于等于以2为底n的对数的最小整数。这是推广到n时的正解。
提示
全部评论
推荐
最新
楼层
国泰君安
校招火热招聘中
官网直投
相关推荐
雨天里一只可怜无助的小黑牛
06-12 09:58
中山大学 计算机类
小红书-新业务后端一面
1、自我介绍2、项目拷打3、八股,答的都挺好的4、聊到B+树时,突然让我手撕B+树,寄
小红书一面64人在聊
查看4道真题和解析
点赞
评论
收藏
分享
牛客435173689号
06-13 14:27
浙大学神们
有没有浙大的好兄弟,能带我进去逛逛嘛
点赞
评论
收藏
分享
在改简历的ssr很喜欢疯狂星期四
04-18 15:42
北京科技大学天津学院 计算机类
实在人
点赞
评论
收藏
分享
牛客644521318号
05-27 14:32
已编辑
山西传媒学院
有没有3D建模的朋友指点一下啊啊啊啊想找工作 #在找工作求抱抱#
在找工作求抱抱
点赞
评论
收藏
分享
lucky_tao
06-12 18:49
中国科学技术大学 电子信息类
实习offer选择,路过的佬帮忙投投票,感谢!
6月底,现在手里有海康研究院(已拒)。达摩院的ic设计。海思巴龙芯片开发部(对接人打电话来了,估计这两天下offer)。达摩院带转正。华为不带转正,不过对接人说部门实习生没有拿不到秋招offer的且进去以后优先安排做设计。 达摩 vs 海思,怎么选。纠结。
投递海康威视等公司10个岗位 >
点赞
评论
收藏
分享
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
5000字说透简历和面试核心要点
2.2W
2
...
手上只有1个看不上的实习offer要不要去?
5848
3
...
你怎么看今年的秋招?预测一波
5507
4
...
6.13校招&实习招聘信息汇总
5166
5
...
除了互联网,还能关注哪些公司
5147
6
...
关于实习的转正、边秋招、没实习的相关问题
3694
7
...
oppo VS 京东
2498
8
...
好未来面试记录
2498
9
...
华为许愿
2477
10
...
重庆移动实习
1920
正在热议
#
牛客帮帮团来啦!有问必答
#
1328373次浏览
18671人参与
#
非技术岗薪资爆料
#
53418次浏览
730人参与
#
OPPO开奖
#
59082次浏览
852人参与
#
和牛牛一起刷题打卡
#
44952次浏览
3575人参与
#
写简历别走弯路
#
360293次浏览
4535人参与
#
我发现了面试通关密码
#
409513次浏览
7309人参与
#
极具前瞻性,现代汽车编程题
#
9510次浏览
188人参与
#
产品每日一题
#
1763次浏览
93人参与
#
来聊聊你目前的求职进展
#
229966次浏览
2905人参与
#
华子oc时间线
#
11277次浏览
60人参与
#
投递实习岗位前的准备
#
753635次浏览
13147人参与
#
如果可以选,你最想从事什么工作
#
219970次浏览
3401人参与
#
晒一晒我的offer
#
4031788次浏览
60399人参与
#
国企vs私企,你更想去?
#
34608次浏览
404人参与
#
我想象的工作vs实际工作
#
116897次浏览
1807人参与
#
软件开发2024笔面经
#
1570663次浏览
36086人参与
#
硬件兄弟们 甩出你的华为奖状
#
37964次浏览
224人参与
#
24届软开秋招面试经验大赏
#
1239218次浏览
18675人参与
#
互联网公司评价
#
105866次浏览
1371人参与
#
参加过提前批的机械人,你们还参加秋招么
#
16720次浏览
382人参与
#
百度工作体验
#
31995次浏览
315人参与
#
机械制造笔面经
#
11779次浏览
332人参与
牛客网
牛客企业服务