趣算法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()
}