10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶

10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶

　　　　身似浮雲，心如飛絮，氣若游絲。

• 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。
• 其中，二進位位運算就是每一隻老鼠代表一個二進位0或1，0就代表老鼠存活，1代表老鼠死亡；根據數學運算 2³ = 8、2⁴  = 16，那麼至少需要四隻老鼠可以找到其中的那瓶毒藥。

/**
 * binary : 0001 : 第1瓶藥水
 * binary : 0010 : 第2瓶藥水
 * binary : 0011 : 第3瓶藥水
 * binary : 0100 : 第4瓶藥水
 * binary : 0101 : 第5瓶藥水
 * binary : 0110 : 第6瓶藥水
 * binary : 0111 : 第7瓶藥水
 * binary : 1000 : 第8瓶藥水
 * binary : 1001 : 第9瓶藥水
 * binary : 1010 : 第10瓶藥水
 * 藥液混合後的數組1: [1, 3, 5, 7, 9]
 * 藥液混合後的數組2: [2, 3, 6, 7, 10]
 * 藥液混合後的數組3: [4, 5, 6, 7]
 * 藥液混合後的數組4: [8, 9, 10]
 *
 * 列印結果如上，此時就可以按照二進位邏輯判定哪瓶是毒藥了。
 * 此時用四隻老鼠分別去喝四組混合後的藥液，即老鼠1和混合要和後的數組1，老鼠2喝混合數組2，老鼠3喝混合數組3，老鼠4和混合數組4
 * 假設第七瓶是毒藥
 * 那麼可以觀察到混合藥液後的數組1、數組2、數組3 都混入的毒藥7
 * 所以就是第一隻老鼠死亡，第二只老鼠死亡，第三隻老鼠死亡，第四隻存活，之前混合藥液的邏輯就是 1有毒 0無毒
 * 所以它們對應的二進位就是：1110，也就是上述的：binary : 0111 : 第7瓶藥水
 *
 * 假設第六瓶是毒藥就是對應著：0110，也就是第一隻老鼠存活、第二只老鼠死亡、第三隻老鼠死亡、第四隻老鼠存活
 *
 * 所以，最後可以根據老鼠的死亡和存活狀態 & 結合混合後的藥液數組 判定哪瓶是毒藥
 * 同理 1000瓶毒藥至少需要10只老鼠可以找出那瓶有毒
 * 2∧10 = 1024
 */

 1 package com.bebird.vote;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.List;
 6 
 7 public class TestVirus {
 8 
 9     public static void main(String[] args) {
10         // 給十瓶毒藥標序號,用1~10標記，並轉為二進位
11         List<Integer> virusArr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
12         // 四個藥液混合的數組
13         List<Integer> list1 = new ArrayList<>();
14         List<Integer> list2 = new ArrayList<>();
15         List<Integer> list3 = new ArrayList<>();
16         List<Integer> list4 = new ArrayList<>();
17         for(int i = 0; i < virusArr.size(); i++) {
18             Integer num = virusArr.get(i);
19             // 設置返回至少4位數字：使用5位數字並切掉第一位數字。
20             String binary = Integer.toBinaryString(num + 0b10000).substring(1);
21             System.out.println("binary : " + binary.concat(" : 第").concat(String.valueOf(i + 1)).concat("瓶藥水"));
22             /**
23              * 把二進位數組中，個位數為1的 十位數為1的 和百位數為1的 千位數為一的 分別組成一個數組
24              * 為什麼這樣做，其實就假設二進位中，1位的是有毒，0位是無毒，按這種邏輯把十瓶藥水混合成四平給四隻老鼠喝
25              */
26             // 判斷二進位 個十百千 位數是否為1:
27             // 個位為1
28             boolean flagGe = (Integer.parseInt(binary) >> 0 & 1) == 1;
29             if (flagGe) {
30                 list1.add(i + 1);
31             }
32             // 十位為1
33             boolean flagShi = (Integer.parseInt(binary) >> 1 & 1) == 1;
34             if (flagShi) {
35                 list2.add(i + 1);
36             }
37             // 百威為1
38             boolean flagBai = (Integer.parseInt(binary) >> 2 & 1) == 1;
39             if (flagBai) {
40                 list3.add(i + 1);
41             }
42             // 千位為1
43             if (binary.startsWith("1")) {
44                 list4.add(i + 1);
45             }
46 
47         }
48         System.out.println("藥液混合後的數組1: "+ list1);
49         System.out.println("藥液混合後的數組2: "+ list2);
50         System.out.println("藥液混合後的數組3: "+ list3);
51         System.out.println("藥液混合後的數組4: "+ list4);
52         /**
53          * binary : 0001 : 第1瓶藥水
54          * binary : 0010 : 第2瓶藥水
55          * binary : 0011 : 第3瓶藥水
56          * binary : 0100 : 第4瓶藥水
57          * binary : 0101 : 第5瓶藥水
58          * binary : 0110 : 第6瓶藥水
59          * binary : 0111 : 第7瓶藥水
60          * binary : 1000 : 第8瓶藥水
61          * binary : 1001 : 第9瓶藥水
62          * binary : 1010 : 第10瓶藥水
63          * 藥液混合後的數組1: [1, 3, 5, 7, 9]
64          * 藥液混合後的數組2: [2, 3, 6, 7, 10]
65          * 藥液混合後的數組3: [4, 5, 6, 7]
66          * 藥液混合後的數組4: [8, 9, 10]
67          *
68          * 列印結果如上，此時就可以按照二進位邏輯判定哪瓶是毒藥了。
69          * 此時用四隻老鼠分別去喝四組混合後的藥液，即老鼠1和混合要和後的數組1，老鼠2喝混合數組2，老鼠3喝混合數組3，老鼠4和混合數組4
70          * 假設第七瓶是毒藥
71          * 那麼可以觀察到混合藥液後的數組1、數組2、數組3 都混入的毒藥7
72          * 所以就是第一隻老鼠死亡，第二只老鼠死亡，第三隻老鼠死亡，第四隻存活，之前混合藥液的邏輯就是 1有毒 0無毒
73          * 所以它們對應的二進位就是：1110，也就是上述的：binary : 0111 : 第7瓶藥水
74          *
75          * 假設第六瓶是毒藥就是對應著：0110，也就是第一隻老鼠存活、第二只老鼠死亡、第三隻老鼠死亡、第四隻老鼠存活
76          *
77          * 所以，最後可以根據老鼠的死亡和存活狀態 & 結合混合後的藥液數組 判定哪瓶是毒藥
78          * 同理 1000瓶毒藥至少需要10只老鼠可以找出那瓶有毒
79          * 2∧10 = 1024
80          */
81 
82 
83     }
84 
85 
86 }