趣算法 01：小鼠试毒

程序是为解决现实问题而诞生，算法则是以计算机角度解决问题的方法，所以编程离不开算法，无论这个算法是简单的自增赋值还是复杂到难以理解。

普通人在接触算法之前看到密密麻麻的字符大概都会觉得头大，数组、索引、循环、递归，当它们组合到一起，缜密逻辑一步接一步，阅读时如果跟不上思路无疑会非常痛苦。但算法作为软件工程师的基础素养不可逃避，或早或晚最终要面对它，接触它们才能真正理解二进制与现实世界的神奇交集。

如何以算法的方式思考问题需要训练，从简单排序开始逐步递进，慢慢感受这种新思维其实并不枯燥。准备把介绍算法的系列博文命名为《趣算法》，试着理解它而不要因畏惧止步不前。

二进制

作为进入算法世界的引子，先看一个很巧妙的问题：

1000 支装满液体的试管，其中1支有毒，生物从接触有毒液体到毒发致死需要 1 天。现在有 10 只小鼠，无限制的试管，可以给这些小鼠喝任意试管中的液体或不同试管的混合液，请问如何在 1 天内找出有毒的那支试管。

这是一个不那么抽象的现实问题，但要解决它却需要抽象为二进制世界的算法。

不用算法的一个惯性思路是直接按着一只把所有试管都尝一遍，但题目中已经说明毒液的发作时间是一天，所以毒性不能在遍历试管中表现出来，这样是不行的。

仔细阅读题目，为什么是 10 只小鼠，为什么是 1000 支试管，再结合小鼠的状态只有生和死 2 种，能否想到二进制呢？而且用这么少的小鼠对应那么多的试管，应该是指数级的对应关系。2 的 10 次方为 1024，即如果用 10 个二进制数，它所能表示的数字范围是 0 ～ 1023，即 10 个小鼠的生死排列组合可以对应 1024 个数，给这些试管编号就能对应 1024 个试管，题目中的 1000 只是一个障眼法。

同样的原理，这个问题可以简化为 4 支试管和 2 只小鼠。给试管编号 0、1、2、3，小鼠编号 0、1，设定小鼠的生为 0、死为 1，左边为二进制高位，那么 2 只小鼠的生死排列只有 4 种可能，对应 4 支试管：

新的问题是，如何产生这 4 种生死组合？肯定要给小鼠喝试管里的液体，喝哪支试管呢？

小鼠最终是生是死与它所喝的液体有关，以死而言，即二进制 1，可能导致该位为 1 的二进制数，比如 小鼠 0，为 01 和 11，即十进制 1 和 3，那么就给它喝试管 1和试管 3 的混合液。如果这两支试管其中有毒，该小鼠最终的结果就是死亡，对应二进制 1。同样的，小鼠 1要喝掉的也是可能导致该位为 1 的二进制数对应的试管，即 10 和 11，试管 2 和试管 3。

假设小鼠喝完后，小鼠 1 存活，小鼠 0 死亡，那么有毒的试管肯定不在小鼠 1 喝的混合液中，而肯定在小鼠 0 喝的混合液中，对应的二进制为 01 即十进制 1，可以确定试管 1 有毒，正好符合小鼠 0 喝的试管。

其实如果以生而言，给每只小鼠喝可能导致它们存活的试管的混合液也是一样的，有毒的试管编号不变，给小鼠喝不同的液体最终会导致不同的存活结果，但其组成的二进制数对应的还是有毒的那支试管。

基本原理就是这样，只需观察最终哪些小鼠死亡哪些小鼠存活即可对应出一个二进制数，转十进制就是有毒试管的编号。

回到原问题，给每只小鼠喝的是除它所对应的二进制位为 1 的其它 2^9 = 512 个数对应的试管的混合液，然后只要知道哪些小鼠死亡就可以确定有毒的试管。

fun main(strings: Array<String>) {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    bufferedReader.use {
        println("已给 1024 个瓶子和 10 只小鼠编号（以左为二进制高位，编号自右向左递增）")
        println("输入死亡的小鼠编号，以空格隔开")
        deal(getInputNums(bufferedReader.readLine()))
    }
}

fun deal(deadNums: IntArray) {
    if (deadNums.isEmpty()) return
    // 10 个二进制位，组成一个无符号数，从右向左，低位到高位，死亡为 1，存活为 0
    var targetNum: Int = 0
    for (i in 0 until 10) {
        val bit = if (deadNums.contains(i)) 1 else 0
        // 移动到指定的二进制位
        targetNum += bit shl i
    }
    println("有毒的瓶子编号为 $targetNum")
}

// 把输入的以空格隔开的数字字符串转换为数字数组
fun getInputNums(numbsStr: String?): IntArray {
    return numbsStr?.split(" ")?.map { it.toInt() }?.toIntArray() ?: intArrayOf()
}