閱讀762 返回首頁    go 阿裏雲 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緩存通用接口