首页 > 代码库 > 天平称球问题
天平称球问题
笔试题目碰到了天平称球的问题,之前遇到没有细细的查阅资料,再次笔试的时候就吃亏了,这里记录下结论:
现有N个小球,其中有一个坏球不知比标准球轻还是重。我们令H={log3(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位的编码; 如果编码等于某个小球的正序码,则这个小球比其它球重; 如果编码等于某个小球的逆序码,则这个小球比其它球轻。
转自于:称球问题——经典智力题推而广之三
参考:小球称重问题:用天平称量几次才能找到有问题的球?
天平称球问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。