10瓶毒藥其中只有一瓶有毒至少需要幾只老鼠可以找到有毒的那瓶
身似浮云，心如飛絮，氣若游絲，
- 用二分查找和二進制位運算的思想都可以把死亡的老鼠降到最低，
- 其中，二進制位運算就是每一只老鼠代表一個二進位0或1，0就代表老鼠存活，1代表老鼠死亡；根據數學運算 23 = 8、24 = 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 }
身似浮云 心如飛絮 氣若游絲
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/538810.html
標籤：其他
上一篇：python基礎-面向物件
下一篇：Kafka牛逼在哪里？