小白鼠试毒药问题



题目如下:

    实验室里有1000个一模一样的瓶子,但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话,会在一个星期的时候死去,其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药:

    a. 9

    b. 10

    c. 32

    d. 999

    e. 以上都不对

    这个题目很简单,拿来复习信息论和二进制编码的粗浅知识刚好合适。

    首先呢,如果让我使用我的LabTop解题,那么简单了,用1000只小白鼠去试验,将瓶子和白鼠编号一一对应,哪只死了便是哪个瓶子里有毒啦!毕竟电脑资源很充裕,平时CPU利用率不到1%,实在是太清闲啦!在上面开辟1000个小白鼠出来还不简单!再说,这种方法虽然简单粗暴,却是最流行的用得最多的办法。不过我猜出这个题目的人是不希望看到这个答案的,因为不管是人还是小白鼠都不愿意看到小白鼠们横尸遍野的场面。记得我高中一位考上了医学院的同学说,小白鼠是很脆弱的,你拿一颗大头钉就可以把它钉到墙壁上面去。它们的腿骨轻轻一折也就断了。真是可怜啊!所以得继续分析下去。

    那么让我们先看看理论上最少得用多少小白鼠好了:1000个瓶子里只有1个是有毒药的,其它的都是好的,那问题又简单了:将瓶子依次排列起来,无毒的用0表示,有毒的用1表示,一共只可能出现1000种不同的状态。这下好了,对1000求以二为底的对数,结果小于10,但是却大于9。看来b是一个很有前途的答案!

    说到这里先打住,我们回过头看看用1000只小白鼠去试验的方法为什么不科学。随便从那1000个瓶子里取出一个来,问你是有毒的还是没有毒的,你说没有毒,那么恭喜你,极有可能你答对了!你犯错误的可能只有0.1% 。一只小白鼠的生死本身有两种完全独立的状态,可以表示1bit的信息;而随便拿出来一个瓶子,它极有可能是没有毒的,信息量只有对1000求以2为底的对数所得数值的千分之一bit那么大!即:ln(1000)/1000ln(2) bit。这个数很小,还不到0.01,看来用一只小白鼠去对付它实在太浪费了!

    也许上一段文字里面有一些你不明白的东西,其中最不明白的就是信息量怎么是那样计算的。我知道你没有学过这东西所以原谅你,但是请你相信我说的是大致正确的,并且我也不会欺骗你。小事情嘛,干吗骗人呢!要骗就在大事情上骗。其实这个算法最初是香农那家伙说的,有错误你去找他好了。

    剩下的,我们最关心的是用10只小白鼠能不能找出那个有毒的瓶子来,或者怎么才能找出来。答案是能够找出来的!用二进制编码的办法。我先说两句这个编码问题。我们小学的时候数数,从1数到9,再往下数,便是一个突破。进位了!二进制里面,你数到1,再往下数,困难了,因为里面只有0和1,连2都没有。麻烦了,到这里就得进位。好了,我们来数一数:0,1,10,11,100,101,110,111,1000,……看明白了吗?这样数下去,数到1111111111,10位,再加1就又要进位了就大于10位了,我们的小白鼠就不够用了。其实已经够了,你回头看看,我们从0到1111111111已经数了1024个数字。对付1000个瓶子还是够了的。

    现在开始解题!把上面数过的数字,长度短于10的,前面全都加上0补够10位数字。比如1101就变成了0000001101。不过它只有1+4+8=13那么大,远远没有1000大呢!哪个数字对应十进制里面的1000呢?应该是1111111111(1023)-10000(16)-100(4)-10(2)-1(1)=1111101000(1000),这个就是十进制里面的1000。让瓶子和小白鼠都排成一列,站好了不准动,对瓶子从1到1000编号,然后把号码转化成10位长的二进制串,刚好和10只小白鼠一位对一位。一个瓶子里的二进制编号有哪几位是1,就让那些小白鼠喝下去其中的一点儿东西好了。将来那些喝了的小白鼠刚好都死了而没喝它的一只都没有死,我们就指定它有毒好啦!

    如此简单的一个问题被我说到了这个地步,不禁心中大乐,哈哈哈哈,我也会瞎扯啦!不过问题还没有完全搞定。如果告诉你有1024个瓶子,用10只小白鼠能否测出来呢?你也看到了,1111111111才有1023那么大,不到1024。其实是可以的,因为我们对瓶子是从1开始编号的,而留下了0没有使用。从0到1023可是1024个数字。

    那么,留一个家庭作业,呵呵:如果题目给的是1024个瓶子里面最多有一个瓶子有毒,还能够用10只小白鼠检测出来吗?这好像跟正零与负零有点儿关系。

网络分层图示

TCP/IP网络分层 和 ISO网络分层对应关系

Linux Network Layers

BSD socket层:这一部分处理BSD socket相关操作,每个socket在内核中以struct socket结构体现。
    这一部分的文件主要有:/net/socket.c /net/protocols.c etc

INET socket层:BSD socket是个可以用于各种网络协议的接口,而当用于tcp/ip,即建立了AF_INET形式的socket时,还需要保留些额外的参数,于是就有了struct sock结构。
    文件主要有:/net/ipv4/protocol.c /net/ipv4/af_inet.c /net/core/sock.c etc

TCP/UDP层:处理传输层的操作,传输层用struct inet_protocol和struct proto两个结构表示。
    文件主要有:/net/ipv4/udp.c /net/ipv4/datagram.c /net/ipv4/tcp.c /net/ipv4/tcp_input.c
        /net/ipv4//tcp_output.c /net/ipv4/tcp_minisocks.c /net/ipv4/tcp_output.c
        /net/ipv4/tcp_timer.c etc  
     
IP层:处理网络层的操作,网络层用struct packet_type结构表示。
     文件主要有:/net/ipv4/ip_forward.c ip_fragment.c ip_input.c ip_output.c etc.

数据链路层和驱动程序:每个网络设备以struct net_device表示,通用的处理在dev.c中,
    驱动程序都在/driver/net目录下。

第一场笔试

之前参加了几场正式的、非正式的面试,今天才是真正的第一次笔试。结果被鄙视了。

考完回来的路上还在自我感觉良好的和同学们谈论考题,还在给郁闷的舍友讲这个该咋办那个该咋搞,结果他接到面试通知了,我被鄙视了!超级郁闷啊!

看来还是我的基础不够扎实,接下来要好好看书了。笔试和做项目毕竟不一样,对于常考的C/C++我都是停留在理论认识和简单应用,如果没有长期的实际操作经验的积累,很容易就会出错的。

好好学习啊!