ARTS-WEEK1

Algorithm

• 老鼠试毒

有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时后就会死亡，问至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒？



老鼠试毒

这里，位掩码的使用就可以巧妙的解决此问题。

我们先将问题简化一下：假设只有8瓶水，其中1瓶有毒。



8杯水分别编号

将该矩阵转置，得：



水杯矩阵转置

依上述场景，取4只容器，转置后的矩阵数列配组合溶液：

取数位上为1的水，放入相应的容器，即：

第一杯：只包含8号水

第二杯：包含4、5、6、7号水

第三杯：包含2、3、6、7号水

第四杯：包含1、3、5、7号水



取4只老鼠，编号1、2、3、4，分别喝下第一杯...第四杯水，

4只老鼠的生死状态依次记为 w x y z，（w,x,y,z = {0,1}）

死亡记作1，非死亡记作0

将二进制数列wxyz转为十进制，则得到有毒水的号码。

假设6号水有毒，那么往回推算，不难看出，第2、3只老鼠会死亡，

得到的wxyz的数列就是0110，转十进制后就是6。



将1000瓶依次编号：1，2，3，4，...，1000； 且都记作二进制；

那我们要用多少位来表示呢？

总数是1000，2^9=512， 2^10=1024，于是至少要10位才够表示，

也就是：0000000001，0000000010，0000000011，...，1111101000；

道理同上。

Review

http://systems.cs.columbia.edu/files/wpid-asplos2014-kvm.pdf

文章主要讲arm虚拟化技术，并在linux平台下与x86的性能进行了对比

Tip

uboot的help中指令具体使用方法，如i2c相关的命令，可用SourceInsight软件查看具体的源码，查看其实现的方式

Share

阅读源码（RTFSC）

获取源头信息，尽少接触二手资料