一道腾讯08年的面试题

铛铛 2010-09-19 10:11:44
题目:

1000瓶药水,其中至多有1瓶剧毒,现在给你10只小狗在24小时内通过小狗试药的方式找出哪瓶药有毒或者全部无毒(小狗服完药20小时后才能判断是否中毒)


(c/c++板块搬过来的......)
...全文
1127 81 打赏 收藏 转发到动态 举报
写回复
用AI写文章
81 条回复
切换为时间正序
请发表友善的回复…
发表回复
CodeArhat 2011-09-27
  • 打赏
  • 举报
回复
思路:
一、“小狗服完药20小时后才能判断是否中毒”,现只有“24小时内”,那么只能试一轮。
毒药发作时间没有指明是否精确。

二、一轮过后,每只小狗状态有两种:生、死
把每只狗看成二进制数的一位,那么结果是个10位的二进制数,可表示2^10 即1024种情况
这已经超过了目标总数(1000),因此有可能找到一种编码方案,将1000种情况唯一的表现出来。

三、将1000瓶药编号:1~1000,换成2进制:0000000001至1111101000(称最左边为第9位,最右边为第0位)

再取10个试管,狗编号:9876543210
对每瓶药,对它2进制编号中所有为1的位,按位序号给对应狗吃。

例如第1000瓶药的编号为1111101000,加入第9,8,7,6,5,3号瓶。

然后对狗编号,吃下对应试管的药(混合后的)。

四、20小时后,根据狗的情况:生=0,死=1 得到一个10位2进制数,即毒药的编号。

另外这题还有只给5只狗的版本,我想32瓶一组的话,只能精确到某组,无法完全确定。
terry 2010-09-20
  • 打赏
  • 举报
回复
都是高人啊,俺佩服27楼的兄弟。
埋头路过。
lf200000 2010-09-20
  • 打赏
  • 举报
回复
如果发作时间固定的话,时间可以解决。
sweetqueen1 2010-09-20
  • 打赏
  • 举报
回复
结帖率很正常啊、、还没结的那个应该是无满意结贴把、、
不过LZ发的内容学习了、、、不错、、
阿旭 2010-09-20
  • 打赏
  • 举报
回复
我来学习一下,顺便留个名。
Diza1986 2010-09-20
  • 打赏
  • 举报
回复
2进制吗
10只老鼠就是10位 可以表示2^10=1024
没有问题啊
guyoujing 2010-09-20
  • 打赏
  • 举报
回复
学习了。。
kingdomht 2010-09-20
  • 打赏
  • 举报
回复
关注中!
LZ给点分
铛铛 2010-09-20
  • 打赏
  • 举报
回复
[Quote=引用 66 楼 xiaohuweiwei 的回复:]
引用 65 楼 zxp8819 的回复:

引用 59 楼 zhangviv 的回复:
引用 58 楼 zxp8819 的回复:
这是理论...
喂药不需要时间

那么楼主发帖中的24小时,20小时可以不用提了...

我不说20小时后药效发作,你们可以做吗?

再说了二进制的方法也只是理论而已,谁有办法在四小时内把这些要喂完的




谁也没说不能使用工具,一开始……
[/Quote]
呵呵,题目就这么给的我也没办法,你不用这四小时是你厉害
可能人家想不到呢
Olive_Guo 2010-09-20
  • 打赏
  • 举报
回复
药与药会不会起反应
绿色夹克衫 2010-09-20
  • 打赏
  • 举报
回复
多么残忍的题目,腾讯真是一家邪恶的公司,为什么用狗,而不是老鼠或小强......
dylike 2010-09-20
  • 打赏
  • 举报
回复
如果第1瓶药有毒,第2瓶没毒,先喂第1瓶再喂第2瓶,第2瓶的药把第1瓶毒药稀释了,中毒发作时间就会超过20小时.不考虑实际问题?如果说一只狗喂N瓶药,结果这些没毒的药把有毒的药稀释地不中毒了,怎么办?
xiaohuweiwei 2010-09-20
  • 打赏
  • 举报
回复
[Quote=引用 65 楼 zxp8819 的回复:]

引用 59 楼 zhangviv 的回复:
引用 58 楼 zxp8819 的回复:
这是理论...
喂药不需要时间

那么楼主发帖中的24小时,20小时可以不用提了...

我不说20小时后药效发作,你们可以做吗?

再说了二进制的方法也只是理论而已,谁有办法在四小时内把这些要喂完的
[/Quote]



谁也没说不能使用工具,一开始就将1000瓶药用流水线配好药,然后就给小狗吃的话根本用不着4小时,谁也没说不能这么做。
dodducs 2010-09-19
  • 打赏
  • 举报
回复
101 结贴 神人也
Code従業員 2010-09-19
  • 打赏
  • 举报
回复
呵呵,原来楼主自己答了。。。接着电话没提交。。。。。闪了。。
Code従業員 2010-09-19
  • 打赏
  • 举报
回复
晕,明显是靠编程的。。。还去想其他的干嘛?

首先我们看到10条狗、1000瓶药,最先想到的是 2 的 10 次方 为 1024 满足要求

这样好办了,给狗编号(0-9),每条狗代表一个二进制位

再给药瓶编号,开始喂狗:比如36号药,转二进制就是 100100 那就同时给 2号狗和5号狗喂,明白?

把各大狗该吃的,准备好,同时灌肠。

20小时后,比如 0到5号都挂了,那二进制就是 111111 那就是 63号药是毒药(因为至多一瓶嘛)
yue_shanglin 2010-09-19
  • 打赏
  • 举报
回复
[Quote=引用 25 楼 jsnjlhb 的回复:]
膜拜LZ的结帖率
[/Quote]
膜拜+1
铛铛 2010-09-19
  • 打赏
  • 举报
回复
像我这样的不止我一个,但是为数不多
jsnjlhb 2010-09-19
  • 打赏
  • 举报
回复
膜拜LZ的结帖率
ziyuexuan 2010-09-19
  • 打赏
  • 举报
回复
[Quote=引用 22 楼 kj289907795 的回复:]

结贴率 101% ?? 还一个没结贴呢?? 系统问题 了 ??
[/Quote]
纳闷中。。。
等待楼主给一个合理的答复,到底是不是CSDN派来的探子
加载更多回复(57)

110,499

社区成员

发帖
与我相关
我的任务
社区描述
.NET技术 C#
社区管理员
  • C#
  • Web++
  • by_封爱
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告

让您成为最强悍的C#开发者

试试用AI创作助手写篇文章吧