二进制的二三事 | Parallel Labs
Task1：求一个固定长度集合所有子集
二进制版本
Task2：小白鼠试毒药问题
实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药？
Read full article from 二进制的二三事 | Parallel Labs
Task1：求一个固定长度集合所有子集
例如集合{a, b, c, d, e}中的子集{a, b, c}可以用“11100”来表示，子集{c, d, e}可以用“00111”来表示，空子集{}可以用“00000”来表示。
那么对任意固定长度的集合a[n]，我们可以从a[0]开始穷举a[0]在子集中和a[0]不在子集中两种情况，再依次类推从a[1]开始一直穷举到a[n-1]为止。于是我们可以得到一个很直观的递归程序：
void sub_sets_recu(int index, int length, char *array, char *bits){ int j = 0; if (index >= length) { for (j = 0; j < length; j++) { if (bits[j] == '1') { printf("%c", array[j]); } } printf("\n"); } else { bits[index] = '1'; sub_sets_recu(index+1, length, array, bits); bits[index] = '0'; sub_sets_recu(index+1, length, array, bits); }}void sub_sets_iter(int length, char *array){ int i = 0; int j = 0; for (i = 0; i < (1<<length); i++) { for (j = 0; j < length; j++) { if ((i & (1<<j)) != 0) { printf("%c", array[j]); } } printf("\n"); }}Task2：小白鼠试毒药问题
实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药？
这个问题关键是跳出思维，并不是说瓶子和小白鼠必须一一对应，然后我们用1000只小白鼠，每只各试一瓶药水，等一个礼拜然后出结果。其实我们仔细想想，小白鼠试毒只有两种结果，非“死”即“生”，又是一个0/1状态。很显然我们可以再次构建一个0/1组成的二叉树，由此即可表示不同的试毒结果。假设我们需要n个小白鼠，那么2^n-1应大于等于1000（因为有1000种可能的结果，减一是指要除去小白鼠全部不死的情况 — 多谢danqi指正），那么最小的n就是10了
解决此类问题的关键在于找到能用0/1表示的状态，然后想办法用0/1组成的二进制数来表示不同的结果，从而达到节省存储空间，提高解题效率的目的。Read full article from 二进制的二三事 | Parallel Labs
