百度面试题

听完这道题后，我第一感觉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为其他数，方法也跟这个一样，不再赘述~