3.2 分割黄金问题与小白鼠试验问题

黄金分割：

    Taylor是一位雇主，雇用Bob为自己新建的房子铺设院子里的地砖，这是一个7天工作量的活。Taylor答应一共支付一根金条作为报酬，但是Bob要求每天支付他1/7的工资，Taylor答应了。现在请问你如何在金条上切两刀，保证每天正好能支付Bob1/7的工资。

    分析：长方体（金条）切两刀，最多切出4份，如果刀子切割路径是曲面，则难以控制均匀切。所以切两刀分出7个1/7是不可能的。考虑到是计算机公司考察的，有可能与编码有关。从二进制的角度思考：7 = 0x111 = 4+2+1 = 0x100 + 0x010 + 0x001，所以答案是一刀切在1/7处，一刀切在3/7处，即可以得到3块小金条，分别是1/7，2/7，4/7。即第一天支付1/7，第二天支付2/7，拿回1/7，第三天把1/7和2/7都给他，以此类推。（1 = 1，2 = 2，3 = 1 + 2，4 = 4，5 = 4 + 1，6 = 4 + 2，7 = 4 + 2 + 1）

小白鼠试验：

    有64瓶药，其中63瓶无毒，1瓶有毒。如果试验小白鼠喝了有毒的药，三天后死，当然喝了其他药（包括同时喝几种，各种药不会发生反应产生综合效应）则没事。现只剩下三天时间，一只小白鼠只能参与一次试验，请问最少需要多少只小白鼠才能试出哪瓶药有毒？

    分析：同样是编码问题。1. 把药按照0-63编号，即从0x000000 ~ 0x111111。2. 然后选6只小白鼠，一字排开。3. 每一只小白鼠吃对应列是1的药。4. 吃完药后三天，根据小鼠死亡情况找出有毒那瓶。（比如1，2，6号小鼠死了，反映在编码上：0x110001，即编号为2^5 + 2^4 + 2^0 = 49的药有毒。另外从信息论角度出发，64选1，也是理论上只需要log64 = 6比特的信息。每只小白鼠三天后要么活0要么死1，即分别都只提供1比特信息）

    总结：上述的小白鼠试验毒药的方法，本质上是一种编码。这种计算思维还可以运用到诸如计算机公司试验产品改进上来，用1%的用户去做对比实验。如果公司每周有大量的改进，那么为了解决用少量用户同时进行很多个试验的问题，就可以采用小白鼠试验方法，将各种不会发生冲突的试验用二进制编码，几组试验放在一起同时进行。

3.3 数据的表示、精度和范围

IEEE-754标准：   

    关于如何兼顾数据的动态范围和精度，我们会自然想到【科学记数法】。这也是当前计算机普遍采用的【IEEE-754】标准的由来：采用64位二进制编码，用1位表示正负号，用11位（-1024～1023）表示数字的动态范围，即数量级，用52位表示精度，这样的设计可以表示（绝对值）小到10^-380、大到10^380的数字。而实际上，这种记数方法会遗漏一些中间数字，如果画一个长数轴，那么计算机双精度浮点数在这根数轴上只是稀稀拉拉的占据一些点而已，大部分区域并为覆盖到。

两个玻璃球问题：

    给你两个一模一样的玻璃球。这两个球如果从一定高度摔到地上一定会摔碎，当然，如果在这个高度之下往下扔，怎么都不会碎。现在已知这个恰巧摔碎的高度在一层楼到100层楼之间。如何用最少的试验次数，用这两个玻璃球测试出摔碎的高度？

    分析：对于这个问题，最naive的想法是一层层的往上试，如果哪一层摔碎了，就找到对应高度了，但是这样平均试验次数要达到50次左右。其实可以使用【粗调和精调】的想法来解决，可以把两个球想作两位数（十位和个位），对1～100的数字进行编码，第一个球每隔10层摔一下，找到在哪一个10层空间里存在那个高度。然后用第二个球在这10层里从下往上试，这样平均需要下来5+5=10次左右。这个道理和机器学习算法中调参数时，调整步长大小的想法类似。

3.4 非线形编码和增量编码（差分编码）

    利用前后信息的相关性，编码时可以采用较少的比特数表达同样的信息。比如一组数据[3210, 3208, 3206, 3211, 3220, 3212, ...]可以表示成[3210,-2,-2,5,9,-8]（当然也可以先取对数log再用差分编码）。这方面的应用有VoIP（Skype, Zoom, 腾讯视频这种软件）。

3.5 哈夫曼编码

    核心思想是这样：在使用不等长编码时，将较短的编码分配给常见的信息，把较长的编码分配给不常出现的信息，这样比对所有信息采用同样码长在总体上更合算。

结束语：

    在计算机中表示信息，最关键的是把握【二分】这个原则，因为计算机是和二进制相连的，而二进制可以表示任何信息。其次，要想办法挤掉冗余的信息，并将较短的码用在最常见的信息上，以提高信息存储和传输的平均效率。