哦,又开了一贴。看到原贴结了我还以为你不想知道这个问题了呢
敝姓杨,以后叫杨大哥就好了。
关于这个问题的解决策略也不是我发现的。先简单做点科普介绍。
解决这个问题的货叫米切尔.费根鲍姆(M.J.Feigenbaum),此人是美国物理学家,因在混沌学领域发现普适常数而著名,此常数后被命名为费根鲍姆常数。
之所以这里我写他的全名是为了防止和另一个叫爱德华.费根鲍姆的货搞混了。他俩是兄弟,后者是人工智能领域大师级人物。唉,这一家子全是天才。
一聊这两个家伙我就兴奋。言归正传,说说这称球的事。
球的状态是通过天平的状态来表达的。只有当天平的状态数达到或超过球的状态数才能区分开每一个球。
天平每次称量的状态有三种,平衡、左倾、右倾。
对于第一次称量,由于不知道坏球是比好球轻还是重,所以它的左倾和右倾只能传达一个意义(球在天平上)。
在之后的称量中,左倾和右倾可以与第一次的倾斜方向作参照,这时它们就有意义了。
如果倾斜方向没变说明坏球还在原来的盘子里,如果倾斜方向改变说明坏球被换到了另一个盘子里。
所以称1次我们可以得到2种状态(平衡,不平衡)
称2次。当第1次称量为平衡时得到2种状态(平衡,不平衡),当称1次衡量为不平衡时得到3种状态(平衡,左倾,右倾)。共可得到2 + 3 = 5种状态。
以此类推,称量n次,可以得到2 + 3 + 3^2 + 3^3 + ... + 3^(n - 1) = (3^n + 1) / 2 种状态。
这里需要说明一个细节,上面状态数的计算前提是已知了好球的重量,或者说我们有一枚额外的好球作参照。
这样,我们才能在第一次称量中获得两种状态。这意味着我们可以在两个球中找出那个坏球。
找法是将参考球与那两个球中的任意一个放在天平上。如果天平平衡,则没放上去的那个是坏球;如果不平衡,则放上去的那个是坏球。
但现在的情况是我们不知道好球的重量,或说我们没有那枚参考球。
而为了获得好球的重量,或者说明确地知道某个或某些球是好球,这需要消耗一次称量。
所以实际称量n次能获得的状态数是 (3^n + 1) / 2 - 1 = (3^n - 1) / 2
一个例子就是,只进行一次称量能从几个球里找出那个坏球。答案:1个。
把上面的公式看成一个函数,其反函数就是m个球可以用多少次称量找出来了。
以上就是找球这一问题的理论分析,最后说说在以上理论的支持下具体怎么找吧。
第一次,在天平左右盘各放(3^(n - 1) - 1) / 2 个球。
如果平衡,说明天平上的都是好球。其余的球继续。
如果不平衡,说明坏球在天平上,天平外的都是好球。
下一次称量,将天平上的球任取1/3下来,剩下的任取一半交换位置。
如果平衡,说明坏球在取下来的1/3里。(注意要记住这些球每个原先放在天平的哪一边了)。
如果不平衡,如果倾斜方向没变,说明坏球在天平上没交换位置的那一半里。
如果倾斜方向改变,说明坏球在天平上交换了位置的那一半里。
如此重复,任意N个球都可在ln(2N + 1)/ ln3次内一定找到那个坏球。