二進制尋找毒酒

二進制尋找毒酒

寫在前面：在做一道演算法分析題目的時候，遇到一個經典題目，也是一個很有技巧性的題目，在眾多大佬的幫助解讀下，以及交作業的厚積薄發下，結合經典“小白鼠試毒”（大學計算機書第一頁）的講解，其實對于這個這個題，二分法和減治法也能做，但時間復雜度和空間復雜度遠遠不及二進制來的簡便和高效，這里給出我的利用二進制設計方案，基于python給出代碼，（可能我的理解還有些偏差，代碼也可能有不對的地方，希望大家能夠給出建議和指正）

【題目】

? 一位國王有n瓶酒，一個間諜對其中的一瓶下了毒，不幸的時，他們都不知道哪一瓶已經被下毒，毒藥非常致命，僅稀釋一滴，配成10億：1的溶液，也能將人殺死，雖然如此，但若要毒藥起作用，也需要一個月的時間，設計一個方案，在一個月的時間內，通過 O ( n l o g n ) O(nlogn) O(nlogn)個測驗者，準確確定哪個酒瓶已被下毒，

【方案設計】

在有限的時間內找到想要的數，轉換成二進制利用 O ( n l o g n ) O(n logn ) O(nlogn)個測驗者找出毒酒，假設 n = 10 瓶酒，10接近16， 2 4 = 16 2^{4} = 16 24=16,所以對10瓶酒編號需要4個bit位，即對酒進行編號0-9，4個bit位對應需要4個測驗者，編號為1-4,從左往右排序4，3，2，1，酒的編號分別為：

1. 同時給測驗者編號，并將4位測驗者測驗前的狀態表示為0000，表示4者均為未中毒狀態 ;
   分別編號為：4，3，2，1
   對應狀態為：0，0，0，0

   前提假設：毒藥非常致命，僅稀釋1滴，10億：1的溶液，也能將人殺死，

2. 測驗

   1號測驗者喝對應酒的二進制編號[1]號bit位（從右往左數）為“1”的混合酒，即酒瓶編號為1，3，5，7，9標簽的混合酒；
   2號測驗者喝對應酒的二進制編號[2]號bit位為“1”的混合酒，即即酒瓶編號為2，3，6，7標簽的混合酒；
   3號測驗者喝對應酒的二進制編號[3]號bit位為“1”的混合酒，即即酒瓶編號為4，5，6，7標簽的混合酒；
   4號測驗者喝對應酒的二進制編號[4]號bit位為“1”的混合酒，即即酒瓶編號為8，9標簽的混合酒；

3. 檢測

   一個月后，觀察結果：
   設計測驗者死亡狀態為1，未中毒狀態為0;
   可知測驗者在測驗前,分別編號為：4，3，2，1 (由于對應1號測驗對應1號bit位，3號對3號bit位，4號對4號bit位，故測驗者編號也是從左往右編號）
   對應狀態為：0，0，0，0
   若在測驗后死亡，則將死亡者0狀態變為1狀態；
   如果全部都安然無恙，則二進制編號為0000的0號標簽酒有毒；
   如果1，2，3號測驗者死亡，則表示為:
   分別編號為：4，3，2，1
   對應狀態為：0，1，1，1
   由測驗中可直接看出都喝了7號標簽的酒，即7號標簽的酒有毒；將對應狀態的二進制數轉換成十進制 0111 = 7，也可確定標簽7號酒有毒，

【python源代碼】

class JudgePoisonous:
    def __init__(self, n):
        self._n = n
        self._max_bin_len = 0 #所需bit位數，也即測驗者數目
        self._wine_lable = [] #酒的二進制編號標簽
        self._test_lable = [] #測驗者標簽
        self._condition = []
        self._dict_ctester = {}
        self._drink_it = True
        self._f_condition = []
    def get_max_bin_len(self):
        self._max_bin_len = len(str(bin(self._n))[2:])
        return self._max_bin_len
    def convert(self, ni):  # Convert the number of each bottle to binary
        bn = str(bin(ni))[2:]
        bbn = bn.zfill(self.get_max_bin_len())  #用0填充成bit位的二進制，便于編號測驗
        return bbn
    def get_wine_lable(self): #獲得酒的二進制編號
        for i in range(self._n):
            self._wine_lable.append(self.convert(i))
        return self._wine_lable
    def get_test_label(self):
        for i in range(self.get_max_bin_len(),0,-1):  # attention why we use self.get_max_bin_len()，instead of self._max_bin_len
            self._test_lable.append(i)
        return self._test_lable
    def tester_condition(self):
        self._condition = [0]*self.get_max_bin_len() #get the initial condition of tester
        return self._condition
    def dic_tlable_condition(self): #將編好號的測驗者對應的狀態用字典表示
        self._dict_ctester = dict(zip(self.get_test_label(),self.tester_condition()))
        return self._dict_ctester
    def test(self):
        for i in range(1,self.get_max_bin_len()+1):
            for j in self._wine_lable:
                if j[-i] == str(1):
                    self._drink_it
    def test_result(self,*death_tester_lable):
        self._dict_ctester = dict(zip(self.get_test_label(), self.tester_condition())) #將編好號的測驗者對應的狀態用字典表示
        for i in death_tester_lable:
            self._dict_ctester[i] = 1
        return self._dict_ctester
    def get_Poisonous_wine(self):
        for i in self._dict_ctester.values():
            self._f_condition.append(str(i))
        self._bin_poi_wine= "".join(self._f_condition) #表示出有毒的酒的二進制
        return int(self._bin_poi_wine,2)  #將二進制轉換成十進制，即為有毒酒的編號

#想寫一個測驗函式，將程式封裝起來，可以通過輸入n和測驗者的死亡情況，直接得出毒酒，但遇到了一點轉換小問題，
#ValueError: invalid literal for int() with base 2: ''
#希望有大佬能夠幫助我解決一下下
"""
if __name__ == "__main__":
    n = eval(input())  # the number of the wine
    death_tester_lable = map(str,input().split(',')[:-1])
    #JudgePoisonous(n).test_result(death_tester_lable)
    print("If label", death_tester_lable, "died", "the poisonous wine is", JudgePoisonous(n).get_Poisonous_wine())
"""

#手動測驗

#測驗代碼
t = JudgePoisonous(10)
#我們假設在一個月之后，測驗者1，2，3死亡
death_tester_lable = 1,2,3
t.test_result(1,2,3)
result = t.get_Poisonous_wine()
print("If label tester",death_tester_lable,"died","the poisonous wine is",result)

程式中還存在一些小問題，并且由于對python類還不太熟悉，寫的可能不太好，希望能有大佬幫助解決！