阅读762 返回首页    go 技术社区[云栖]

如何用10只实验鼠检验出1000个药瓶中哪个有毒药？

转自：https://blog.csdn.net/u012027907/article/details/12296473


  当我第一次看到这个面试题的时候，也不知道从何处下手，但在别人的提示下，我才明白了！

    如果你看到这个题目，能够立即想到2 的 10 次方 = 1024.那你已经知道答案了！

   原题的描述是：给你10只实验小鼠，用7天的时间检验1000个瓶子中带有一瓶毒药的瓶子是哪一瓶，小鼠喝了毒药7天后才会死亡，如何编程实现？

   这是二进制数的一个应用,如果你不明白白，请看下面简单点的。

   用3只来检验8瓶。

   小鼠最后的状态只有两种，即：死亡(喝了毒药)和活着(没有喝毒药)。

   我们用0 - 7 来给8个瓶子编号，并用二进制表示：

 000     第0瓶

  001    第1瓶

  010     第2瓶

  011    第3瓶

  100     第4瓶

  101     第5瓶

  110    第6瓶

  111     第7瓶

  我们让第一只小鼠（红色表示）喝第4、5、6、7瓶，让第二只小鼠（蓝色表示）喝第2、3、6、7瓶，让第三只小鼠喝第1、3、5、7瓶，这样小鼠7天后就只有这八种状态，如果是 第一只活（0），第二只活（0），第三只死（1），那就可以确定是第一瓶，其他的也如此。

 2的3次方 = 8 ，2的10次方 = 1024，所以用10只小鼠可以检验1000个瓶子的。

  小鼠的状态可用0（活）、1（死）表示，也就可以用计算机实现。

  其实就是进制转换的问题：将二进制转为十进制。

最后输入小鼠的状态，如0000000000，转为十进制 0，则第0瓶有毒。

进制转换代码如下：

  1. public class Base {     
  2.         /**   
  3.          * 将数转为任意进制   
  4.          * @param num   
  5.          * @param base   
  6.          * @return   
  7.          */    
  8.         public String baseString(int num,int base){     
  9.             if(base > 16){     
  10.                 throw new RuntimeException("进制数超出范围，base<=16");     
  11.             }     
  12.             StringBuffer str = new StringBuffer("");     
  13.             String digths = "0123456789ABCDEF";     
  14.             Stack<Character> s = new Stack<Character>();     
  15.             while(num != 0){     
  16.                 s.push(digths.charAt(num%base));     
  17.                 num/=base;     
  18.             }     
  19.             while(!s.isEmpty()){     
  20.                 str.append(s.pop());     
  21.             }     
  22.             return str.toString();     
  23.         }     
  24.         /**   
  25.          * 16进制内任意进制转换   
  26.          * @param num   
  27.          * @param srcBase   
  28.          * @param destBase   
  29.          * @return   
  30.          */    
  31.         public String baseNum(String num,int srcBase,int destBase){     
  32.             if(srcBase == destBase){     
  33.                 return num;     
  34.             }     
  35.             String digths = "0123456789ABCDEF";     
  36.             char[] chars = num.toCharArray();     
  37.             int len = chars.length;     
  38.             if(destBase != 10){//目标进制不是十进制 先转化为十进制     
  39.                 num = baseNum(num,srcBase,10);     
  40.             }else{     
  41.                 int n = 0;     
  42.                 for(int i = len - 1; i >=0; i--){     
  43.                     n+=digths.indexOf(chars[i])*Math.pow(srcBase, len - i - 1);     
  44.                 }     
  45.                 return n + "";     
  46.             }     
  47.             return baseString(Integer.valueOf(num),destBase);     
  48.         }     
  49.     }    



最后更新：2017-04-03 15:22:13

  上一篇：go spoj 208 Store-keeper bfs+重联通分量
  下一篇：go 网络子系统39_inet_peer缓存通用接口