算法合集之《一类称球问题的解法》

1、一类称球问题的解法1问题的提出给定N个球有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。2N = 312312是次品12是次品12是次品N=3时称1次就可以找出次品3N = 9123456789ABCAB次品在A中次品在B中AB 通过一次称量，可以把次品可能存在的范围从9个，缩小到3个 N = 3的时候一次就能称出次品N = 9时称2次次品在C中AB4更一般的情况N = 3k12k12k12kABC5更一般的情况ABABAB次品在A中次品在B中次品在C中范围缩小到原来的1/36更一般的情况 n = 3k+1, n = 3k+2和n=3k类似，也是均分成三堆每次称量把范围大致

2、缩小到原来的1/3因此：从n个球中找次品至多要称log3n次。（统一表示取上整）7判定树log3n无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡8判定树称(1, 2)=13=79=46= log3nlog3n是最优解11小结引进了有力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀12分配的均匀性1239称(1, 2)= log3n深度很大，远超过其兄弟13问题2的提出N个球，混入了一个轻重不详的次品手中有一架天平和一个标准球用最少的次数称出次品并求出次品的轻重14问题2的基本分析12可得如下信息：次品若在中，则它偏重。次品若在中

3、，则它偏轻。15引理的提出已知两堆球，第一堆有a个、第二堆有b个。若次品在第一堆，必是重球若次品在第二堆，必是轻球分析总共a+b个球每个球都有可能是次品判定树至少a+b个叶子树的深度h = log3(a+b)只要称log3(a+b)次就能找到次品16引理的分析a = 3pp 个p 个p 个A1A2A3b = 3qp 个B1B2B3p 个p 个17引理的分析A1B1A2B2A3B3次品在A1 或者 B2范围被缩小到p+q个球里面18引理的分析A1B1A2B2A3B3次品在B1 或者 A2范围被缩小到p+q个球里面19引理的分析A3B3次品在A3 或者 B3范围被缩小到p+q个球里面A1B1A2B

4、220子问题的分析总共a+b=3(p+q)个球无论天平怎么偏，都可以把范围缩小到p+q个球中，即原来的1/3根据a, b mod 3的余数分类，上面讨论的是a mod 3 = b mod 3 = 0的情况。其他情况可类似进行。关键要“均”分。引理中问题称log3(a+b)次即可。21问题2的分析n个球，每个球都有可能是轻球或者重球，有2n种不同的可能结果判定树至少要2n个叶子节点判定树的深度h = log3(2n)22问题2的分析比较S与1=2L/=A1重或A2轻2p个叶子节点A1轻或A2重2p个叶子节点A3轻重都有可能2p个叶子节点|A1|=|A2|=|A3|=p总共有6p个叶子节点27问题2的分析n=3k+2分法|A1|=k+1 |A2|=k+1 |A3|=k6k+4个叶子节点分摊到每个孩子是：2k+2 2k+2 2k是均匀的28问题2的分析N = 3k + 1分法一：k，k，k+1分摊的叶子节点：2k，2k，2k+2分法二：k+标准球，k+1，k分摊的叶子节点：2k+1，2k+1，2k29问题2的小结log3(2n)即是问题2的解。最优性和可行性均已证明判定树是一种估界和证明最优性的有力工具。通过对判定树的研究，衍生了一条重要的原则：均匀。均分的对象不是球，而是叶子节点（即不同的结果）。30其他形式只要求次品，不求轻重。结论是log3(2n-1)问题2去掉标准球。第