天平称球问题

天平称球问题

　　笔试题目碰到了天平称球的问题，之前遇到没有细细的查阅资料，再次笔试的时候就吃亏了，这里记录下结论：

现有N个小球，其中有一个坏球不知比标准球轻还是重。我们令H={log₃(2N)}。         

     1)要保证在N个球中找出坏球并知道其轻重，至少需要称H次。假设N≠2，我们有2)如果N＜(3H-1)/2，那么称H次就足够了；3)如果N=(3H-1)/2，那么称H次足以保证找到坏球，但不足以保证知道坏球比标准球轻还是重；4)如果N=(3H-1)/2，而且还另有一个标准球，那么称H次足以保证找到坏球和知道，知道坏球比标准球轻还是重。假设N=2，我们有5)如果还另有一个标准球，称H={log3(2*2)}=2次足以保证找到坏球和知道坏球比标准球轻还是重。

    5)看起来有点奇怪，不过这其实很显然。如果有超过两个球，我们知道坏球是“独一无二”的那一个，总找得出来；但是如果只有两个球，一个好球一个坏球，都是“独一无二”的，如果没有一个标准球的话，我们无论如何不可能知道哪个才是好的。

    一般地，能由H次称量找出坏球并知道其轻重的最大小球数量为(3H-1)/2-1 = (3H-3)/2；能由H次称量找出坏球但不需要知道其轻重的最大小球数量为(3H-1)/2；有一标准球，能由H次称量找出坏球并知道其轻重的最大小球数量也为(3H-1)/2。为了比如说为了找出坏球并知道其轻重，则3次最多可以称12个，4次为39个，5次为120个，6次为363个等等；为了找出坏球却不需知道其轻重，则3次最多可以称13个，4次为40个，5次121个，6次364个等等——但是如果另有一个标准球，那么就可以用相同的次数来知道坏球的轻重。

    过程构造算法：

 编码：知道了球数，就能算出需要称量几次；以这个次数作为长度，使用0、1、2排列组合进行编码，如001021、212022等等，再去掉全0、全1和全2，可知一共有个编码；如果在一个编码中，第一处相邻数字不同的情况是01、12或20，则我们称它为正序码，如1120021；否则为逆序码，如2221012；在长度为n的编码中，正序码和逆序码的数量相等，均为个。
赋值：如果把一个正序码中的0换成1，1换成2，2换成0，则它仍然是正序码；根据这个原理，我们把所有正序码按3个3个进行分组，如12001、20112、01220这3个就是一组；把正序码一组一组地分配给小球，每球一个，直到分完；然后把每个正序码的0换成2，2换成0，它就变成了一个逆序码，如12001变成10221；这样，每个小球就有了两个编码，一个正序，一个逆序，而且所有球都不重复。
称重：第一轮，我们把所有正序码第一位为0的小球放在天平左侧，为2的小球放在右侧，其它的放在旁边；如果天平左倾，记为0；右倾，记为2；平衡，记为1；然后是第二轮，把第二位为0的小球放在左侧，为2的放在右侧，同样记下称量结果；每一轮都按这个顺序进行，一共要称n次，最终结果是个n位的编码；如果编码等于某个小球的正序码，则这个小球比其它球重；如果编码等于某个小球的逆序码，则这个小球比其它球轻。

    转自于：称球问题——经典智力题推而广之三

    参考：小球称重问题：用天平称量几次才能找到有问题的球？

转载于:.html