有64瓶藥,其中63瓶無毒,1瓶有毒。
如果實驗用小白鼠喝了有毒的藥,3天後會死掉,而喝了無毒的藥,即便同時喝幾種都沒事。
現在你剩下3天時間,請問最少需要幾隻小白鼠試藥,才能找出哪瓶有毒?
對習慣二進位思維的軟體工程師來說很直觀,看到64就想到2的6次方,答案:6隻老鼠。
分別會讓:
老鼠一號代表bit 0,即2的0次方;
老鼠二號代表bit 1,即2的1次方;
以此類推...
老鼠六代號表bit 5,即2的5次方。
老鼠六代號表bit 5,即2的5次方。
(二進位表示順序bit 5 bit 4 bit 3 bit 2 bit 1 bit 0)。
十進位1=二進位000001,第1瓶藥,由bit 0的老鼠喝;
十進位2=二進位000010,第2瓶藥,由bit 1的老鼠喝;
十進位3=二進位000011,第3瓶藥,由bit 0、bit 1這兩隻老鼠喝...
以此類推...
而第64瓶 ,全部老鼠都不喝。
假如全部老鼠都活著,代表第64瓶藥有毒;
假如bit 0、跟bit 5這兩隻老鼠死掉,2^0+2^5=1+32 = 33,第33瓶藥有毒。
若是讓我我設計題目,可能不會設計得那麼直覺,
假如bit 0、跟bit 5這兩隻老鼠死掉,2^0+2^5=1+32 = 33,第33瓶藥有毒。
若是讓我我設計題目,可能不會設計得那麼直覺,
可能是有59瓶藥,其中58瓶無毒,1瓶有毒,如果...
不會那麼直覺看出。
沒有留言:
張貼留言