百度的一道假盐面试题引发的争论，评论略叼

问题：

N个瓶子里装着一种盐，其中有一瓶是假盐，假盐的特点是溶于水后变色，其他的盐则不变色。现在给你X碗水找出那瓶假盐，则X至少为？

一楼

听完这道题后，我第一感觉X应该是log2(N)的上界。不过我当时没说出答案，我在想如何证明出来，最后一时没想出来好的简单的证明方法，也错失了这个机会。 现在证明一下，其实这个思路非常简单。 假设这N个瓶子分别标号为0、1、2、...、N - 1、N 用0表示水加入盐后不变色，1表示水加入盐后变色，则X碗水中加入盐后的状态可用X位的二进制来表示。 易知这状态有2^X种，用一种状态就可以对应假盐的瓶子号，而假盐的瓶子号只有N种。 现在关键是怎么样往水中加盐使其最后的状态就可以看出唯一的假盐的瓶号。 先看几个数的二进制表示(我从左往右记，与平时的刚好相反) 0 0000…… 1 1000…… 2 0100…… 3 1100…… 从这个几个数大家会发现用什么方法呢？ 比如0号状态对应结果是0号瓶是假盐，X个碗状态都不变色，则显然0号瓶盐不加入任何碗中 1号状态对应结果是1号瓶是假盐，X个碗只有第1个碗变色，则只把1号瓶盐加入第一个碗中 2号状态对应结果是2号瓶是假盐，X个碗只有第2个碗变色，则只把2号瓶盐加入第一个碗中 3号状态对应结果是3号瓶是假盐，X个碗只有第1、2个碗变色，则只把2号瓶盐加入第一、二个碗中 现在给定一个具体的数，N=8，该如何往碗中加盐，从上面的分析中可以我们可以按如下方法加盐 X = log2(N) = 3 0 000 1 100 2 010 3 110 4 001 5 101 6 011 7 111 则0号瓶盐不加入任何碗中，1号瓶盐只加入第一个碗中，2号瓶盐只加入第二个碗中，3号瓶盐加入第一、二个碗中，4号瓶盐只加入第三个碗中，5号瓶盐加入第一、三个碗中，6号瓶盐加入第二、三个碗中 ，7号瓶盐三个碗中都加入。 即第一个碗中将加入1、3、5、7号瓶盐 第二个碗中将加入2、3、5、7号瓶盐 第三个碗中将加入4、5、6、7号瓶yan 这样由3个碗中最后的状态就可以知道唯一的假盐的瓶号了。 N为其他数，方法也跟这个一样，不再赘述~

看完这个评论，我表示大神给跪了，说的好有道理，不明觉厉。

二楼

没错，一碗就够了。 加1号瓶的盐，加2号，加3号，看加到第几号瓶变色.

感觉好有道理，我竟无言以对。

三楼

这些人, 用来面试程序员, 感觉有点过份, 因为有N种答案, 就像偻主那样, 认为他的才正确, 还算成logn碗, 好简单的事情, 不是说只有一种会变色吗? 直接每瓶顺序倒点盐进去, 水变色就是假盐了, 或者打一碗水来倒进盐瓶里, 变色的也是. 这题和工厂选空的盒子一样, 请了个科学家, 花了几个月, 精准的计算, 花了几千万, 终于做出一款可以选空盒子, 请个农民, 农民只用一台风扇就搞定的事一样.

科学家的脑回路比较长……

四楼

设a=碗的容积，b=融化一粒盐与融化一粒假盐所需的水量的最小公倍数 x=(n/b)/a ——这个不对吧，你这算的是最坏的情况下，即加盐是放在最后的那个位置 假盐是放在第i个位置的概率为1/n 那么需要的水杯数： (1/n)*(1/ab)+(1/n)*(2/ab)+(1/n)*(3/ab)+....+(1/n)*(n/ab) =(n+1)/2ab，再向上取整

不知道你在说什么鬼。

看到这么对回复，那么你觉得答案是什么呢？毕竟百度面试题，评论下方留言你的答案！

End