从N个变量中找出一个异常变量的方法
从N个变量中找出一个错误变量的方法
假设有N包咖啡,里面有一包咖啡是掺和了沙子的,可以将咖啡放到水杯里融化,如果十分钟后,被子里有沙子沉淀的,那么那包就是有问题的咖啡。问题是:在十分钟之内,需要最少多少个杯子能检验出那包有问题的咖啡呢?
【思路】
可以利用二进制数的特点来解答。将N表示成二进制,那么二进制的如果能确定出现问题的咖啡在二进制位的哪些(哪个)位上,即使解答。而要确定哪些位,只需要知道二进制的长度即可。(将咖啡搀和起来融化)
【实例】
假设8包,3个碗(log_2_8=3),给“糖”编号0~7
000:0
001:1
010:2
011:3
100:4
101:5
110:6
111:7
第一个碗中放4~7号,第二个碗中放2367号,第三个碗中放1357号。
过十分钟看效果:
都没有沙子:0号有问题;
第一个有沙子,其他无:4号有问题;
第二有沙子,其他无:2号;
第三有沙子,其他不:1号;
第一第二有沙子,第三无:6号;
第二第三有沙子,第一无:3号;
第一第三有沙子,第二无:5号;
有沙子:7号。