首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

1000个瓶子里面999瓶是水,多少次试验确定哪瓶是毒药

题图 | @望川鸟

在文章之前我先抛出一个有趣的问题,相信有的同学是看过的,没有看过的也不打紧儿,文章下面会进行解答。问题如下:

现在有1000个瓶子,里面999瓶是水,1瓶是毒药。最少通过多少次的试验,能确定哪瓶是毒药。

这个问题你可以思考一下,我先来说一说最近在生活中遇到的另一间相关的事。

前段时间在设计一张数据表的时候遇到了一个小问题。情况是这样的,一条数据有着三种状态,这三种状态是可能叠加并且重复的。什么意思呢?我举一个通俗的例子来类比一下。

孔子曰:吾日三省吾身。高乎?帅乎?富乎?高、富、帅可以说是一个人的三种状态。比如通过「骨骼生长」这个函数的处理,人可以拥有「高」这个状态;通过「自我打理、运动健身」这个函数的处理,人可以拥有「帅」这个状态;通过「发奋图强」这个函数的处理,人可以拥有「富」这个状态。什么是叠加?就是一个人可以拥有其中的多种状态;什么是重复?比如一个人多次「奋发图强」,依然会拥有「富」的状态。

解释完这些,再回到问题本身。我当时想的是,给每个状态一个单独的布尔类型(可以判断真或假)的字段,然后在进行处理时对相应状态进行分别判断。这样虽然也能完成任务,但是显得笨重且不优雅。举两个显而易见的例子:

假如这条数据将来不止三种状态,难道需要重新对数据库进行改造吗?而且程序也要相应地修改。数据库作为基础设施,一旦确定,修改地成本是很高的。

因为一条数据可能会经过多次相同类型地处理,假如这样设计,每次处理前程序都需要知道当前状态是真是假,处理完再决定是否修改状态码。这会导致程序的冗余、不简洁。

...

针对这些问题,X叔(组里一位我很敬重的老哥)建议我可以用一个笼统的字段 ,然后每种状态的值可以设置为1、2、4...这样。我心想,妙啊。

多重状态叠加产生的值是不会产生重复的,比如「高富」=3,「高帅」=5,「富帅」=6等等。而且以后有新的状态,假设新增「健康」这些,到时候,直接约定为相应值8、16等等。

那这和位运算有什么关系呢?我们来看下面这张图。

而在重复处理方面,位与运算带来了更加简洁的操作。举个例子,假如当前状态时是「高帅」,需要再次进行「帅」处理,如果按照传统的加减方式,需要判断当前有没有「帅」这个状态4,有的话不加,没有的话加上4。这无疑是非常繁琐的。

使用位与运算,会简洁很多,比如:

很方便。在进行位或的时候也是如此,可以结合具体情况试一试。

解决了这个问题。回头看看文章开头的智力题。

可以先公布一下答案:10。

假设现在有十只小白鼠,如何10只小白鼠的生死来找出那一瓶毒药呢?我们先将1000个瓶子用二进制编号,就像下图:

从000000001-1111111111,代表1号到1024号(1001-1024个瓶子可以忽视,因为只需要1000个),可以看到,每个数都有十位,那么我们让每只小白鼠负责一列,将这一列的编号出现1的瓶子中的液体混合着喝下去。如果某只小白鼠死了那么可以判定这列为1的所有瓶子中,有一瓶是毒药。通过十只小白鼠的生死情况组合来看,不难发现那瓶是毒药的瓶子编号。

如果你觉得数量太大,有些纳闷,可以减少数量,假设总共共有八个瓶子,其中一瓶是毒药。仔通过这种方式来计算一下。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180914B0TL6P00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券