找出毒药

发表于 更新于

一、8瓶药里1瓶毒药，至少需要多少老鼠

老鼠找出毒药的一般问题类型是m瓶药，其中一瓶是毒药，用n只老鼠来检测，求n最小多少。

问题的最小规模是8瓶药，3只老鼠。明面和暗含的条件有

  • m瓶药里只有一瓶毒药；
  • 毒药立马发作；
  • 所有老鼠同时喝药；

答案是2^3=8，故3只老鼠即可。具体方案是：瓶子0-7号（0号瓶所有老鼠都不喝。如果M1 M2 M3都没死，那0号就是毒药）：

  • 鼠M1: 1+3+5+7
  • 鼠M2: 2+3+6+7
  • 鼠M3: 4+5+6+7

方案的本质是，每只老鼠都喝4瓶药，且任意两只老鼠喝的药有且只有2瓶是一样的。所以下面方案也可以：

  • 鼠M1: 0+1+4+5
  • 鼠M2: 0+2+4+6
  • 鼠M3: 0+3+5+6
  • 鼠M1: 1+4+5+7
  • 鼠M2: 2+4+6+7
  • 鼠M3: 3+5+6+7
  • 鼠M1: 1+4+6+7
  • 鼠M2: 2+4+5+7
  • 鼠M3: 3+6+5+7
  • 鼠M1: 1+4+6+0
  • 鼠M2: 2+4+5+0
  • 鼠M3: 3+6+5+0

采用二进制来理解的方案，图示如下：

表1：

鼠↓ 瓶→ 0号 1号 2号 3号 4号 5号 6号 7号
鼠M1 0 1 0 1 0 1 0 1
鼠M2 0 0 1 1 0 0 1 1
鼠M3 0 0 0 0 1 1 1 1

二、1000瓶药里1瓶毒药，喝药15分见效，总共60分种，至少需要多少老鼠

如果按前面的思路，一次性找出毒药需要 $\lceil \log_2{1000} \rceil$=10只老鼠没问题，可是60分钟内找出的毒药该如何解？我们可以使用n维坐标系分析，或者使用n进制给瓶子编号，这里的n指的是喝药次数+1。

采用三进制来理解的方案，图示如下：

表2：

鼠↓ 瓶→ 0号 1号 2号 3号 4号 5号 6号 7号 8号
鼠M1 0 1 2 0 1 2 0 1 2
鼠M2 0 0 0 1 1 1 2 2 2

从上面可以推测出，n瓶药里有1瓶毒药，喝药见效时间pt，总时间t，需要老鼠的通用公式为：
喝的轮数 c = $\lfloor t/pt \rfloor$
需要老鼠 m = $\lceil \log_{c+1}{n} \rceil$

三、1000瓶药里1瓶毒药，喝药15分见效，总共60分种，用最少的老鼠写出老鼠喝药的具体方案

从表2可以得出，正常情况下（最后一轮才出现老鼠死亡的情况）喝药方案：

表2：

第一轮 第二轮
M1 0+3+6 1+4+7
M2 0+1+2 3+4+5

如果中途出现老鼠死亡，剩下的老鼠去喝可能导致死亡的药即可（递归）。

喝药方案代码如下，考虑到中途可能有减员，故只给出了前两轮喝药方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

func bottleToCheck(die []int, live []int, ret map[int][]uint64) []uint64 {
    sDie := make([]uint64, 0)
    sLive := make([]uint64, 0)
    for _, v := range die {
        sDie = append(sDie, ret[v]...)
    }
    for _, v := range live {
        sLive = append(sLive, ret[v]...)
    }
    inArray := func(i uint64, arr []uint64) bool {
        for _, v := range arr {
            if v == i {
                return true
            }
        }
        return false
    }
    rt := make([]uint64, 0)
    for _, v := range sDie {
        if inArray(v, sLive) {
            continue
        }
        rt = append(rt, v)
    }
    return rt
}

func rSolution(bottle/*需要检测的瓶子*/ []uint64, mouse/*剩余老鼠编号*/ []int, k/*计算第k轮的喝药方案*/ int, n/**进制*/ int) map[int][]uint64 {
    solution := make(map[int][]uint64)
    strRightAt := func(str string, at int) int {
        var i int
        if len(str)-at-1 < 0 {
            i = 0
        } else {
            i, _ = strconv.Atoi(str[len(str)-at-1 : len(str)-at])
        }
        return i
    }
    for _, mv := range mouse {
        for _, dv := range bottle {
            str := strconv.FormatUint(dv, n)
            i := strRightAt(str, mv)
            if i == k {
                solution[mv] = append(solution[mv], dv)
            }
        }
    }
    return solution
}

func logXyCeil(x, y float64) float64 {
    a, b := math.Frexp(x)
    c, d := math.Frexp(y)
    e := (math.Log(c)*(1/math.Ln2) + float64(d)) / (math.Log(a)*(1/math.Ln2) + float64(b))
    return math.Ceil(e)
}

func main() {
    b := 81 /*瓶子数量*/
    n := 2 /*喝药轮数*/
    m := int(logXyCeil(float64(n+1), float64(b))) /*共m只老鼠*/

    fmt.Printf("瓶子数量：%d，总喝药轮数：%d，老鼠数量: %d\n", b, n, m)

    var bottle = make([]uint64, 0)
    var mouse = make([]int, 0)
    var k int
    for i := 0; i<m;i++ {
        mouse = append(mouse, i)
    }
    for i := uint64(0); i<uint64(b); i++ {
        bottle = append(bottle, i)
    }

    k = 0
    ret := rSolution(bottle, mouse, k, n+1)
    fmt.Printf("第%d轮方案：\n", k)
    for i, v := range ret {
        fmt.Printf("M%d:\t %v\n", i, v)
    }

    //假设喝完第0轮，M0死亡，其他老鼠存活。那第1轮的喝药方案应该是：
    bottle = bottleToCheck([]int{0}, []int{1, 2, 3}, ret)
    mouse = []int{1, 2, 3}
    k = 1
    ret = rSolution(bottle, mouse, k, n+1)
    fmt.Printf("第%d轮方案：\n", k)
    for i, v := range ret {
        fmt.Printf("M%d:\t %v\n", i, v)
    }
}

三、1000瓶药里2瓶毒药，喝药15分见效，总共60分种，用最少的老鼠写出老鼠喝药的具体方案

todo