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

来源:https://www.cnblogs.com/taojietaoge/archive/2022/11/30/16938221.html
-Advertisement-
Play Games

10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶 身似浮雲,心如飛絮,氣若游絲。 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。 其中,二進位位運算就是每一隻老鼠代表一個二進位0或1,0就代表老鼠存活,1代表老鼠死亡;根據數學運算 23 = 8、24 = 16,那麼至少需要四 ...


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

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

  • 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。
  • 其中,二進位位運算就是每一隻老鼠代表一個二進位0或1,0就代表老鼠存活,1代表老鼠死亡;根據數學運算 23 = 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 }

 

 

 

 

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

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一.小結 1.不可變對象一旦創建,就不能改變。為防止用戶修改對象,可以定義不可變類。 2.實例變數和靜態變數的作用域是整個類,與變數在何處聲明無關。實例變數和靜態變數可以在類中的任意位置聲明。為保持一致,最好在類的起始位置聲明它們。 3.關鍵字this可用於表明調用對象。關鍵字this也可以用在構造 ...
  • 序言 各位好啊,我是會編程的蝸牛,作為java開發者,我們每天都要和開發工具打交道。我以前一開始入門java開發的時候,就是用的eclipse,雖然感覺有點繁瑣,但好在還能用。後來偶然間發現了IDEA,然後就漸漸被IDEA所吸引了,不過最近在做一些老項目的開發,大概是十幾年的那種技術,我發現用IDE ...
  • 前言 本文是博主從事後端開發以來,對公司、個人項目的經驗總結,包含代碼編寫、功能推薦、第三方庫使用及優雅配置等,希望大家看到都能有所收穫 博主github地址: https://github.com/wayn111 一. 優雅的進行線程池異常處理 在Java開發中,線程池的使用必不可少,使用無返回值 ...
  • 重構項目目錄 celery_task: logs:項目運行時/開發時日誌目錄包 luffapi:項目同名文件夾 apps:項目所有應用的集合文件夾 libs:第三方類庫的保存目錄[第三方組件、模塊] - 包 media:用戶提交的文件目錄文件夾 settings:配置目錄,包含開發時的配置文件和上線 ...
  • 話說在前面,我不是小黑子~ 我是超級大黑子😏 表弟大周末的跑來我家,沒事幹天天騷擾我,搞得我都不能跟小姐姐好好聊天了,於是為了打發表弟,我決定用Python做一個小游戲來消耗一下他的精力,我思來想去,決定把他變成小黑子,於是做了一個坤坤打籃球的游戲,沒想到他還挺愛玩的~ 終於解放了,於是我把游戲寫 ...
  • 使用腳本自動跑實驗(Ubuntu),將實驗結果記錄在文件中,併在實驗結束之後將結果通過郵件發送到郵箱,最後在windows端自動解析成excel表格。 ...
  • 大家好,我是陶朱公Boy。 前言 上一篇文章《關於狀態機的技術選型,最後一個真心好》我跟大家聊了一下關於”狀態機“的話題。從眾多技術選型中我也推薦了一款阿裡開源的狀態機—“cola-statemachine”。 於是就有小伙伴私信我,自己項目也考慮引入這款狀態機,但網上資料實在太少,能不能系統的介紹 ...
  • 一、Kafka存在哪些方面的優勢 1. 多生產者 可以無縫地支持多個生產者,不管客戶端在使用單個主題還是多個主題。 2. 多消費者 支持多個消費者從一個單獨的消息流上讀取數據,而且消費者之間互不影響。 3. 基於磁碟的數據存儲 支持消費者非實時地讀取消息,由於消息被提交到磁碟,根據設置的規則進行保存 ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 1. 講故事 年前遇到了好幾例托管堆被損壞的案例,有些運氣好一些,從被破壞的托管堆記憶體現場能觀測出大概是什麼問題,但更多的情況下是無法做出準確判斷的,原因就在於生成的dump是第二現場,借用之前文章的一張圖,大家可以理解一下。 為了幫助更多受此問題困擾的朋友,這篇來整理一下如何 快狠準 的 ...
  • 前言 .NET6 開始,.NET Croe API 項目取消了 Startup.cs 文件,在 Program.cs 文件的 Main 函數中完成服務的註冊和中間件管道的管理。但當我們項目引入更多包的時候,Program.cs 文件也會看起來很臃腫。 而且,我們不只會有一個後端項目,為了方便快速創建 ...
  • 目錄 背景 get 與 post 的區別 所有介面都用 post 請求? 背景 最近在逛知乎的時候發現一個有趣的問題:公司規定所有介面都用 post 請求,這是為什麼? 看到這個問題的時候其實我也挺有感觸的,因為我也曾經這樣問過我自己。在上上一家公司的時候接到一個項目是從零開始搭建一個微服務,當時就 ...
  • *以下內容為本人的學習筆記,如需要轉載,請聲明原文鏈接 微信公眾號「englyf」https://mp.weixin.qq.com/s/2GFLTstDC7w6u3fTJxflNA 本文大概 1685 個字,閱讀需花 6 分鐘內容不多, 但也花了一些精力如要交流, 歡迎關註我然後評論區留言 謝謝你的 ...
  • 在新版本的pandas中,上述代碼會引起警告,建議改成SQLAlchemy connectable(engine/connection),後續代碼將引入這種升級的連接方式。 ...
  • 幾乎所有的高級編程語言都有自己的垃圾回收機制,開發者不需要關註記憶體的申請與釋放,Python 也不例外。Python 官方團隊的文章 https://devguide.python.org/internals/garbage-collector 詳細介紹了 Python 中的垃圾回收演算法,本文是這篇 ...
  • 如果您想查找高於或低於平均值的數字,可以不必計算該平均值,就能查看更高或更低的值。通過Java應用程式,可以自動突出顯示這些數字。除了快速突出顯示高於或低於平均值的值外,您還可以查看高於或低於的值的個數。現在讓我們看看如何在 Java應用程式中實現此操作。 引入jar包 導入方法1: 手動引入。將  ...
  • 第一種方式:使用{} firstDict = {"name": "wang yuan wai ", "age" : 25} 說明:{}為創建一個空的字典對象 第二種方式:使用fromkeys()方法 second_dict = dict.fromkeys(("name", "age")) #valu ...
  • 在golang中可以使用a := b這種方式將b賦值給a,只有當b能進行深拷貝時a與b才不會互相影響,否則就需要進行更為複雜的深拷貝。 下麵就是Go賦值操作的一個說明: Go語言中所有賦值操作都是值傳遞,如果結構中不含指針,則直接賦值就是深度拷貝;如果結構中含有指針(包括自定義指針,以及切片,map ...
  • 本文結合京東監控埋點場景,對解決樣板代碼的技術選型方案進行分析,給出最終解決方案後,結合理論和實踐進一步展開。通過關註文中的技術分析過程和技術場景,讀者可收穫一種樣板代碼思想過程和解決思路,並對Java編譯器底層有初步瞭解。 ...