首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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时的正解。
提示
全部评论
推荐
最新
楼层
网易互娱
校招火热招聘中
官网直投
相关推荐
RykerFeng
05-18 22:14
已编辑
武汉理工大学 金融学类
武汉小红书前端实习一二面面经
好久没更新了,最近要开始准备提前批了,所以开始整理三月份面的一些面经~面的是武汉小红书,人审部门一面(40min)1. 前端监控系统如何处理浏览器崩溃的情况?2. 前端监控系统如何做的资源请求优化?3. 蔚来实习优化做了什么?4. 手写二叉树的最大深度,这里要写两种实现方式,都写出来了5. 实现一个接口级别的缓存,这个是在美团做的事情,给面试官简单写了一下。6. 反问,部门是做什么的?人审。表现怎样? 前端监控系统里解决问题思路很对,方案对比的也比较多,我听下来感觉对我还算满意。一面完 10min约二面二面:(40min)1. 一面中聊到的浏览器崩溃的问题2. 蔚来实习优化做了什么?【这里面试...
找实习多的是你不知道的事
不给转正的实习,你还去吗
点赞
评论
收藏
转发
互联网农民工_
05-17 14:30
清华大学 计算机类
520 技术岗暑期实习最新更新,再不投就只能秋招了
5.17 更新 MetaAPP:https://meta.jobs.feishu.cn/140297/position/list?keywords=&category=&location=&project=7055213620741540135&type=&job_hot_flag=&current=1&limit=10&functionCategory=&tag= 亿星软件(国内知名的外贸行业ERP解决方案提供商) 歌尔:https://wecruit.hotjob.cn/SU63c50f8b0dcad47488052...
投递英伟达等公司6个岗位 >
点赞
评论
收藏
转发
牛客848889590号
03-29 13:51
已编辑
C工程师
Debuff叠满了
#简历被挂麻了,求建议# 二本+gap1年+初创
简历被挂麻了,求建议
点赞
评论
收藏
转发
26加瓦鼠鼠
04-09 09:31
莆田学院 计算机类
我等了你8天,你却...
时隔8日hr终于回复了,我茶不思饭不想了8天,他说我不合适😭,兄弟们我要掉小珍珠了😭渣男 #沉淀# #黑皮体育生# #java#
点赞
评论
收藏
转发
niuniuniuniuniuniuniuniu
05-16 12:39
人工智能
现在在哪个平台找工作比较好一点?
最近几乎都没有收到面试,一直都没找到工作崩溃了,兄弟们都在哪里投递简历的呀?
牛客在线求职答疑中心
牛客解忧铺
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
写在最后,一个大专人9年的自述
1.4W
2
...
换导师
9736
3
...
双非本 腾讯WXG暑期已offer | 附面经
8764
4
...
爱华信华等华
5210
5
...
开摆了,写小说去了
4977
6
...
没offer的我们也很优秀偶
4945
7
...
华为暑期开奖
4862
8
...
快手客户端开发工程师(1)
4796
9
...
美团本地商业 二面
4732
10
...
滴滴秋储-服务端开发 OC
4409
正在热议
#
牛客帮帮团来啦!有问必答
#
848432次浏览
13306人参与
#
机械制造薪资爆料
#
322998次浏览
3749人参与
#
晒一晒我的offer
#
3497753次浏览
55527人参与
#
金三银四,你有感觉到吗
#
332645次浏览
4244人参与
#
0offer是寒冬太冷还是我太菜
#
431719次浏览
4969人参与
#
实习生如何通过转正
#
28305次浏览
368人参与
#
互联网公司评价
#
86116次浏览
1152人参与
#
我在牛爱网找对象
#
51344次浏览
337人参与
#
运营面经
#
15502次浏览
316人参与
#
如何缓解入职前的焦虑
#
36427次浏览
359人参与
#
海康威视求职进展汇总
#
103106次浏览
1229人参与
#
国企vs私企,你更想去?
#
21416次浏览
219人参与
#
毕业租房也有小确幸
#
27469次浏览
1500人参与
#
荣耀求职进展汇总
#
73596次浏览
747人参与
#
投了多少份简历才上岸
#
61279次浏览
982人参与
#
实习必须要去大厂吗?
#
14706次浏览
235人参与
#
你遇到过哪些神仙同事
#
19357次浏览
284人参与
#
职业发展规划如何回答
#
12420次浏览
85人参与
#
你已经投递多少份简历了
#
312725次浏览
4622人参与
#
实习工作,你找得还顺利吗?
#
43950次浏览
485人参与
牛客网
牛客企业服务