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

(完整版)算法合集之《一类称球问题的解法》(完整版)算法合集之《一类称球问题的解法》(完整版)算法合集之《一类称球问题的解法》一类称球问题的解法长沙雅礼中学何林关键字判定树三分均匀摘要本文对一类天平称球问题提出了完整、严谨的解法,在此基础上总结了研究过程中的一些心得和方法.引言有n（n≥3）个球，其中一个是次品，你有一架天平。现在要称出哪个次品来。问题1已知次品的重量比其他的要重一些。问题2不知道次品的重量.问题3不知道次品的重量。不仅要求出次品,还要求次品的轻重。问题4不知道次品的重量，要求次品和次品的轻重.另外你手里还得到了一个标准球。面对这一系列类似的问题,我们该从何入手?简单问题的分析先来考虑最简单的问题1.为了方便叙述，把n个球按1,2,…,n顺次编号。若n=3,把一号球放在天平左边、二号球放在天平右边.如果天平：左偏，一号重，是次品。右偏，二号重,是次品.保持平衡，那么一、二都是正常的球，因此就只有可能三号球是次品了。因此n=3,至多一次就能称出哪个是次品。记作f（3)=1。下面考虑n=9。把所有的球分成三组:A{1,2,3}，B｛4,5，6},C{7，8，9}.A组的球放在左边、B组放在右边。如果天平：左偏，则次品在A组里面。右偏，则次品在B组里面。保持平衡,次品在C组里面。无论在哪个组里面,我们已经把次品的范围从“9"缩小到了“3”,也就是减少到原来的1/3。之前我们已经研究过，3个球1次就能称出来,故而f(9）=2。不难推广到一般的情况：定理1。1f(3n)=n。证明：n=1,2时，已证.设n=k成立，则f（3k）=k；下面考虑n=k+1的情况。将3k+1个球分成三堆A,B，C，使得|A|=|B｜=|C｜=3k。把A放在天平左边、B放在右边，天平：左偏，次品在A右偏,次品在B平衡，次品在C无论哪种结果，我们都把次品的范围缩小到了3k个球里面。而f(3k）=k，故而f（3k+1）=k+1。综上，定理1。1成立.稍经分析不难得到：定理1.2f（n)=这个的证明和定理1.1完全类似，分nmod3=0,1，2适当讨论即可。我们必须注意到是可行的，因为我们能够构造出这样一个方案。问题是它是否最优?我们采取的方案是每次将球尽量均匀的三分，这样做的根据就是天平只有三种结果：左偏、右偏、平衡。于是就能保证无论次品在哪一份都能将结果的范围缩小到原来的1/3.从感性上认识，应该就是最优解了。为了更加严格的证明的最优性，我们引进判定树的概念。下图就是n=9时的一种判定树:比较(1,2,3)与(4,5,6)>=<比较(1)与(2)>13=<2比较(7)与(8)>79=<8比较(4)与(5)>46=<5此题的判定树是这样一棵树：叶子节点代表一种可能的结果。非叶子节点代表一次称量。非叶子节点至多有三个儿子,分别代表天平的左偏、右偏、平衡三种情况。任意一种称量方案都能唯一的表示成一棵判定树;反过来一棵判定树也唯一对应一种称量方案。容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。做出判断之前,谁也无法预知哪个球是次品，每个都有可能是我们的目标；因此一个有意义的判定树应该具有至少n个叶子节点。n个叶子节点的树的深度h≥，故而可以证明，f（n）=是最优的。至此完整的解决了问题1。我们的结论是：有n（n≥3)个球,其中一个是次品，次品的重量比其他的要重一些。给一架天平，至少称次,就能找出那个次品.具体的方案是将球每次都尽量均匀的三分。（详见上文）让我们总结一下.“三分”是整个算法的核心。我们选择三分，而不是二分或者四分是有原因的,它的本质是由判定树的特殊结构——三叉树——所决定的。同时还必须注意一点,我们在三分的时候有两个字很讲究:“均匀”。实际上h≥中的“=”当且仅当球被均匀的分配时才能达到。这里说的“均匀"是指“在最坏情况下获得最好的效果”.因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀"分配的理论根据。或许你觉得这些总结是显然的、多余的废话。面对一个简单的问题，你当然能够游刃有余，也不需要提炼出什么经验、方法；可是当问题被复杂化、隐蔽化,你还能如此得心应手吗？称球问题的拓展问题的提出与初步分析问题4有n（n≥3）个球,其中一个是次品，已知：次品的重量与其他的球不同，不知道轻重。你有一架天平和一个标准球问至少要称多少次，才能找出那个次品，并且知道次品是轻还是重？我们很自然的联想到问题1，试着应用三分。把n个球分成三堆，第一堆放在天平左边、第二堆放在天平右边。天平平衡,毫无疑问,次品在第三堆中；但问题是如果天平发生了偏移，既可能第一堆中混入了一个重球、也可能第二堆中混入了一个轻球.我们根本无法准确地判断次品具体在哪堆中。问题4较之问题1最大的困