2 道很有意思的进制题

1. 一共有 10 只老鼠，1000 只水杯，杯子里都盛着水，只有一个杯中是有毒的液体，这种毒 液老鼠喝下去以后，一个星期就会死掉。现在要求使用这 10 只老鼠，在一个星期之内找出盛着毒液的杯子。

分析一下，这道题目其实是一道和二进制相关的题目。由于只能在一个星期内完成任务，那就说明不能进行重复的实验。这样的话，由于 10 只老鼠在一个星期以后的状态只能是死亡或者存活两种状态，根据乘法原理，我们知道，10 个单位的两种状态，可能出现的所有可能是 2^10 = 1024。足够编码 1000 个杯子了。也就是说，我们现在的任务是把 1000 个杯子 与 10 只老鼠的死和活的组合一一对应起来。如果把 1 到 1000 表示成二进制，那么答案就很明显了。

将 1 到 1000 共一千个数，都转换成二进制编码。对于数字 A，如果它的二进制的最低位 是 1，那么就让 1 号老鼠喝一点这个杯子里的液体，如果是 0 就不喝。A 的二进制的倒数第二低位如果是 1，那么编号为 2 的老鼠就喝，否则不喝。依次类推。直到最高位如果是 1，那么编号为 10 的老鼠就喝，否则该老鼠不喝。一个星期以后观察结果，如果编号为 x 的老鼠死掉 了，那么就从低向高数 x 位，在那个位置上标 1，其他的位置标 0。例如，如果只有 2 号和 4 号 老鼠死掉了，那么记录的结果就是“00 0000 1010”，这样一个二进制数。把它转成十进制是 10，这就意味着 10 号杯子里装的是毒液，其他杯子则是水。

2. 有一架天平，它有 20 个砝码，这 20 个砝码的重量分别为 1,3,9,27···3^19。只要被称的物品的重量为位于区间 [1,(3^20−1)/2] 的整数，就可以使用这架天平进行称量。假设物品一直放在天平的左边，现在给出每个物品的重量，请打印出称量的方案。输出格式为两组数字，第一组代表天平左边要放的砝码，第二组代表天平右边要放的砝码。这两组数中间用空格隔开。每一组内部的数使用逗号隔开。如果天平的某一边不需要放砝码，那就打印 empty。
   例如，输入是 9，输出是 empty 9，代表左边不需要额外的砝码，而右边需要放一个重量为 9 的砝码。 输入是 4，输出是 empty 1,3。

从最简单的情况入手进行分析。比如说 1，那右边只要放 1 就可以。如果是 2，我们可以用左边放 1，右边放 3 这样的方案代替。3，右边只要放 3。4，右边放 1 和 4。到了 5，由于不能再使用 3-1 去凑一个 2 了，所以唯一的方案是左边放 1，3，右边放 9。同样，6，也只好用 9-3 来凑。我们来分析一下这个规律。

4 的三进制是 11，代表了 1 * 3 ^ 1 + 1，5 的三进制是 12，代表了 1 * 3 ^ 1 + 2 * 3^0，6 的三进制是 20，代表了 2 * 3^1 + 0 * 3^0。由于我们手里的砝码是 3^0, 3^1, 3^2……，也就是说，如果目标数字的各个位置上都是 1，那我们直接就能组合出来，而如果第 n 位上是 2，就必须使用 3^(n+1) - 3^n 来凑这个数。也就是说，我们要在天平的左右两边各加上一个 3^n，才能保持平衡。这样就把低一位上的 2，消除成了高一位上的 1。

好了。有了这个算法，我们就可以写出程序了。

public int[][] solve(int x) {
    int pl = 0, pr = 0;
    int poise = 1, r;
    final int LEFT = 0, RIGHT = 1;
    int[][] result = new int[2][20];

    while (x > 0) {
        r = x % 3;
        if (r == 2) {
            result[LEFT][pl++] = poise;
            x = (x + 1) / 3;
        }   
        else if (r == 1) {
            result[RIGHT][pr++] = poise;
            x = x / 3;
        }
        else
            x = x / 3;

        poise *= 3;
    }

    return result;
}