【精品】一类称球问题的解法
一类称球问题的解法
长沙雅礼中学 何林
关键字
判定树 三分 均匀
摘要
本文对一类天平称球问题提出了完整、严谨的解法，在此基础上总结了研究过程中的一些心得和
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。
引言
有n(n?3)个球，其中一个是次品，你有一架天平。现在要称出哪个次品来。
问题1 已知次品的重量比其他的要重一些。
问题2 不知道次品的重量。
问题3 不知道次品的重量。不仅要求出次品，还要求次品的轻重。
问题4 不知道次品的重量，要求次品和次品的轻重。另外你手里还得到了一个
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
球。
面对这一系列类似的问题，我们该从何入手,
简单问题的
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
先来考虑最简单的问题1。为了方便叙述，把n个球按1,2,…,n顺次编号。
若n=3，把一号球放在天平左边、二号球放在天平右边。如果天平:
1、左偏，一号重，是次品。
2、右偏，二号重，是次品。
3、保持平衡，那么一、二都是正常的球，因此就只有可能三号球是次品了。
因此n=3，至多一次就能称出哪个是次品。记作f(3)=1。
下面考虑n=9。把所有的球分成三组:A{1,2,3},B{4,5,6},C{7,8,9}。A组的球放在左边、B组放在右边。如果天平:
1、左偏，则次品在A组里面。
2、右偏，则次品在B组里面。
3、保持平衡，次品在C组里面。
无论在哪个组里面，我们已经把次品的范围从“9”缩小到了“3”，也就是
减少到原来的1/3。之前我们已经研究过，3个球1次就能称出来，故而f(9)=2。 不难推广到一般的情况:
n定理1.1 f(3)=n。
k证明:n=1,2时，已证。设n=k成立，则f(3)=k;下面考虑n=k+1的情况。
k+1k将3个球分成三堆A, B, C，使得|A|=|B|=|C|=3。把A放在天平左边、B放
在右边，天平:
1、左偏，次品在A
2、右偏，次品在B
3、平衡，次品在C
kk无论哪种结果，我们都把次品的范围缩小到了3个球里面。而f(3)=k，故k+1而f(3)=k+1。
综上，定理1.1成立。
稍经分析不难得到:
logn定理1.2 f(n)= ，，3
这个的证明和定理1.1完全类似，分n mod 3 = 0, 1, 2适当讨论即可。
logn我们必须注意到是可行的，因为我们能够构造出这样一个
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。问，，3
题是它是否最优,
我们采取的方案是每次将球尽量均匀的三分，这样做的根据就是天平只有三
种结果:左偏、右偏、平衡。于是就能保证无论次品在哪一份都能将结果的范围
logn缩小到原来的1/3。从感性上认识，应该就是最优解了。 ，，3
logn为了更加严格的证明的最优性，我们引进判定树的概念。 ，，3
下图就是n=9时的一种判定树:
比较(1,2,3)与(4,5,6)
> < =
比较(4)与(5) 比较(1)与(2) 比较(7)与(8)
> = < > = < > = <
5 4 6 1 3 2 7 9 8
此题的判定树是这样一棵树:
1、叶子节点代表一种可能的结果。
2、非叶子节点代表一次称量。
3、非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情
况。
任意一种称量方案都能唯一的表示成一棵判定树;反过来一棵判定树也唯一对应一种称量方案。
容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。
做出判断之前，谁也无法预知哪个球是次品，每个都有可能是我们的目标;因此一个有意义的判定树应该具有至少n个叶子节点。
n个叶子节点的树的深度h ? logn，故而可以证明，f(n)= logn是最，，，，33优的。
至此完整的解决了问题1。
我们的结论是:有n(n?3)个球，其中一个是次品，次品的重量比其他的要重一些。给一架天平，至少称logn次，就能找出那个次品。 ，，3
具体的方案是将球每次都尽量均匀的三分。(详见上文)
让我们总结一下。
“三分”是整个算法的核心。我们选择三分，而不是二分或者四分是有原因的，它的本质是由判定树的特殊结构——三叉树——所决定的。
同时还必须注意一点，我们在三分的时候有两个字很讲究:“均匀”。实际上
lognh ? 中的“=”当且仅当球被均匀的分配时才能达到。 ，，3
这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀”分配的理论根据。
或许你觉得这些总结是显然的、多余的废话。面对一个简单的问题，你当然能够游刃有余，也不需要提炼出什么经验、方法;可是当问题被复杂化、隐蔽化，你还能如此得心应手吗,
称球问题的拓展
一、 问题的提出与初步分析
问题4 有n(n?3)个球，其中一个是次品，已知:
1、次品的重量与其他的球不同，不知道轻重。
2、你有一架天平和一个标准球
问至少要称多少次，才能找出那个次品，并且知道次品是轻还是重,
我们很自然的联想到问题1，试着应用三分。
把n个球分成三堆，第一堆放在天平左边、第二堆放在天平右边。
天平平衡，毫无疑问，次品在第三堆中;但问题是如果天平发生了偏移，既可能第一堆中混入了一个重球、也可能第二堆中混入了一个轻球。我们根本无法
准确地判断次品具体在哪堆中。
问题4较之问题1最大的困难就在于不知道次品的轻重，因此一次称量之后根本无法马上将次品缩小到理想的范围。
因此经过一次称量，如果天平不平衡，问题就被转化为一个新的结构，我们将其归纳、强化成如下引理:
有两堆球，第一堆有n个、第二堆有m个，其中有一个是次品。并且引理
次品如果在第一堆中只可能是重球、在第二堆中只可能是轻球。只要称log(n，m)次就可以找到次品。 ，，3
(这是一条重要结论，之后会反复引用，请注意)
为了解决问题4，我们先探讨这个引理的证明。
二、 引理的证明
总共n+m个球，每个球都可能是次品，所以判定树有n+m个叶子节点。于
log(n，m)log(n，m)是判定树的深度h >= ，由此可知是一个最优的界。 ，，，，33
下面我们通过归纳构造，证明这个界是可以达到的。
达到最优界必需且仅需满足一条原则:均匀分配叶子节点。
为了方便叙述，约定:
1、S表示标准球。
2、nH表示第n个球是重球
3、nL表示第n个球是轻球
4、
表示将集合A中的球放在天平左边，集合B中的球放在天平右边
的称量结果。=Left、Right或者Middle，分别表示左偏、右偏和平
衡。
用归纳法证明，归纳n+m。
n+m=2。如果n=m=1，根据题设只有可能是1H, 2L。判定树如下:
比较S与1
> < =
1H / 2L
如果n=2, m=0，只有可能是1H、2H，判定树如下:
比较S与1
> < =
1H / 2H
若n=0, m=2，只有可能是1L、2L，判定树如下
比较S与1
> < =
1L 2L /
无论n, m如何取值，均只需要1次称量即可。而log(n，m)=1，因此n+m=2，，3
时引理成立。
假设n+m，若:
1、=Middle。次品在C或者C’中，问题归结到p+q时的引理。
、=Left。由于次品在A’中只有可能是轻球、在B中只有可能2
是重球，所以次品必不在这两者中。可以把范围缩小到A和B’中，问题又归结到p+q时的引理。
3、=Right。类似于2，可以把次品的范围缩小到A’和B中，问题也归结到p+q时的引理。
无论如何，一次称量后都可以把问题归结到p+q时的引理。根据归纳假设还
log(p，q)log(p，q)log(n，m)要称次。所以原问题总共称+1=次即可。 ，，，，，，333
于是情况一引理成立。
情况二:n=3p+1, m=3q+2。
将第一堆n球分成三堆A, B, C，使得 |A|=p, |B|=p, |C|=p+1。
第二堆m个球也分成三堆A’, B’, C’，使得|A’|=q+1, |B’|=q+1, |C’|=q。
称，根据天平偏移的情况做出适当的判断即可。此不赘述。
我们之所以把A+A’, B+B’, C+C’分别作为一组，就是因为:
1.天平左偏，次品只有可能在A, B’中，有p+q+1种可能的结果。
2.天平右偏，次品只有可能在A’, B中，有p+q+1种可能的结果。
3.天平平衡，次品只有可能在C, C’中，有p+q+1种可能的结果。
也就是说无论天平怎么偏，我们总可以把原来的n+m=3(p+q)+3种可能的结果，缩减到p+q+1种;换一个角度看，也就是把3(p+q)+3 个叶子节点分摊到三棵子树上，每棵分摊到的节点个数都是p+q+1～这是是准确意义上的均匀，保证了在最坏的情况下也能得到最好的结果。
总之无论你怎么分，只要保证了“均匀”，就是一种可行的方案。所谓的均匀就是“最坏的情况下的结果达到最优”。
另外还有四种情况(见下表)都可以按照以上的方法类似证明，结构完全相同，关键是抓着“均匀”的原则不放。下表是这几种情况的具体划分方法:
a的划分，三个数依次代b的划分，三个数依次代
表|A|, |B|,|C| 表|A’|, |B’|,|C’| n=3p, m=3q+1 p, p, p q, q, q+1 n=3p, m=3q-1 p, p, p q, q, q-1 n=3p+1, m=3q+1 p, p+1, p q+1, q, q n=3p+1, m=3q+2 p, p, p+1 q+1, q+1, q
需要特别说明的是，这里的均分的是“可能的结果”(即判定树的叶子节点)，而不是单纯的均分球。
综上，对于任意的自然数n, m(n+m>=2)，引理成立～
三、 问题4的解决
回顾一下问题4。
问题4 有n(n?3)个球，其中一个是次品，已知:
1、次品的重量与其他的球不同，不知道轻重。
2、你有一架天平和一个标准球
问至少要称多少次，才能找出那个次品，并且知道次品是轻还是重,
问题1中每个球都有可能是次品，所以有n个叶子节点;我们必须注意到问题4不仅每个球都有可能是次品，而且次品还有两种情况:轻或者重～所以本题实际上有2n种不同的可能结果，而不是n种。
log2n所以此问题的判定树至少要有2n个叶子节点，它的深度h ? 。 ，，3
比如n=3，有如下6种结果:
1、1号是次品，且比标准求重。记作1H(H是heavy的缩写)
2、2H
3、3H
4、1号是次品，且比标准球轻。记作1L(L是light的缩写)
5、2L
6、3L
log6拥有6个叶子的判定树的深度 h ? =2，所以3个球至少要称2次，，3
才能找到次品并知道轻重，而不是我们想象的1次。
实际上n=3时2次也就足够了，判定树如下:
比较1与2
> < =
比较1与S 比较1与S 比较3与S
> = < > = < > = <
1L / 2H 1H 2L / 3H / 3L
我们很自然的联想:是不是log2n就是问题的解,log2n的最优性是毋，，，，33
庸置疑的，可是可行性呢,我们是不是总能构造出这样的一棵判定树呢, 将这个想法归纳一下就是
猜想 给定一个标准球，一架天平。有n个球，其中一个是次品。每个球既
log2n有可能轻、也有可能重。只需要次就能称出次品，并且知道它是轻还是，，3
重。
仿照之前解决的问题，采用归纳构造。
log2nn=2时判定树如下，2次即出解。 =2，因此n=2时成立。 ，，3
比较S与1
> < =
1L 1H 比较S与2
> = <
2L / 2H
假设n。若: I. =Left。结果可能是AH或者BL，问题归结到p+p时的引理，还要log2plog2plog6plog2k称次。总共要称+1==次。 ，，，，，，，，3333
II. =Middle。次品在C中，问题归结到n=p时的猜想，根据归纳假设
log2plog2plog6plog2k还要称次。所以总共称+1==次即可。 ，，，，，，，，3333
log2kIII. =Right。类似I，总共称次。 ，，3
无论如何称次即可。综上k mod 3 = 0时猜想成立。 log2k，，3
情况二:k mod 3 = 2。可以设k=3p+2。
分成三堆A, B, C，使得|A|=p+1, |B|=p+1, |C|=p。将6p+4个叶子节点分摊为2p+2,2p+2,2p，是均匀的。
然后称，和情况一完全类似，此不赘述。
:k mod 3 = 1。可以设k=3p+1。 情况三
先看一种错误的想法。
分成三堆A, B, C，使|A|=p, |B|=p, |C|=p+1，这样看起来是“均匀”的。接着称:
1、=Middle。次品在C中，可能是CH或者CL这2p+2种结果。
2、=Left。可能是AH或者BH这2p种结果。
3、=Right。可能是AL或者BH这2p种结果。
不难发现原问题的6p+2个叶子节点被分摊成2p+2, 2p, 2p。这是均匀的吗,显然不是～
比如p=1，n=4，共有8种可能的结果，根据猜想只需要2次即可得出解答。可是如果把球划成1,1,2三堆，2个球需要2次才能称出，整个问题就至少需要称3次～
我们往往容易被表面的假象所迷惑，把3p+1个球分成p、p、(p+1)这三堆看似是均匀的，然而我们必须时时谨记:均分的不是球，而是判定树的叶子节点——那才是保证结果最优的充要条件。
既然有6p+2个叶子节点，我们就应该按照2p+1, 2p+1, 2p的方式均分。
可以如此划分:A{S,1,2,…,p}, B{p+1,p+2,…,2p,2p+1}, C{2p+2, 2p+3, …,
3p+1}。即|A|=p+1, |B|=p+1, |C|=p。特别注意的是在A中加入了一个标准球。
然后称，若:
1、=Middle。 次品在C中，问题归结到n=p的猜想，根据归纳假设，
log2plog2plog6plog6p，2log2k还要称次。既总共称+1 = ==，，，，，，，，，，33333次。
2、=Left。有可能是1H, 2H, …, pH, (p+1)L, (p+1)L, …, (2p+1)L这2p+1种结果(由于S是标准球，所以不在我们的筛选范围之内。因此参加称量的虽然有2p+2个球，但是实际有可能是次品的却只有2p+1个。这也是此方案和之前
log2p，1错误想法的根本区别)，可以归结到p+(p+1)时的引理，还要称次。，，3
log2p，1log6p，3log6p，2log2n总共称+1===次即可。 ，，，，，，，，3333
3、=Right。类似于2，不赘述。
综上，k mod 3 = 1，猜想成立。
综上，对于任意的自然数n(n>=2)，猜想成立～
于是问题4解决了，我们的结论是:
给定一架天平，一个标准球。称出n个球中的次品并且知道轻重，需要且仅
需要次。 log2n，，3
四、 小结
在已经研究过问题1的基础上，我们很自然的把解决问题1的一系列方法和主观经验搬到此题来;这对启迪思路起了很重要的作用。
然而由于问题的相异性，表面的规律和经验却在进一步的应用中失败了。我们以“判定树”为桥，深入的研究了问题1中间方案的本质规律，得到了两条重要原则:
1、均匀三分。
2、均分的是叶子节点，而不是球。
正是这两条原则引导我们迅速的构造出完整的称量方案，得以正确的解决问题。
称球问题的其他变化形式，也完全遵循上述两个原则。所谓万变不离其宗，只要我们牢牢抓住上述两条原则，以判定树为研究的桥梁，无论问题形式怎么变，都能手到擒来。
称球问题的一些其他变化形式
问题3 有n(n?3)个球，其中一个是次品。已知:
1、次品的重量与其他的球不同，不知道轻重。
2、你只有一架天平。
问至少要称多少次，才能找出那个次品、并且知道次品到底是轻还是重,
问题3 和 问题4 相比，唯一的不同就是没有标准球。
实际上一次称量之后，无论天平怎么偏，我们至少可以得到一个标准球。具体地说，第一次称量:
1、天平平衡。放在天平上的都是标准球。
2、天平不平衡。没放在天平上的球都是标准球。
因此，从第二次称量开始，问题3就完全等价与问题4。只要考虑第一次称量。
解决问题4时，n mod 3=0, 2我们没用标准球即达到最优解;唯有n mod 3 =1时需要借助标准球实现叶子节点的均摊。
稍加试验就会发现，n mod 3 = 1无论如何也无法在没有标准球的前提下均分叶子节点，只能舍而求次，采用一种次优的划分方案。
设n=3k+1，划分成A, B, C，使得|A|=|B|=k, |C|=k+1，然后称。具体的判断和计算并不复杂，留给读者完成。
我们的结论是:
log2n，2给定一架天平，有n个球，其中一个是次品。称次就可以找到，，3
次品，并且知道次品的轻重。
容易发现n个球只有2n种可能的结果，因此从理论上说，判定树的最优下界是。此处的结论为什么要次呢,原因就在于缺少一个标log2nlog2n，2，，，，33
准球，使得n mod 3 = 1时，第一次我们无论如何也不可能实现完美意义上的均分，只能采取了一种次优的方案，因此最优界也是不可能达到的。
以上的问题都要求次品的轻重，可有时候我们关心的是哪个球是次品。至于具体是轻还是重，倒是无关紧要的。
因此我们提出一个新问题:
问题5 有n(n?3)个球，其中一个是次品。已知:
1、次品的重量与其他的球不同，不知道轻重。
2、给你一架天平、一个标准球。
问至少要称多少次，才能找出那个次品,
这个问题又复杂一点。
首先是下界不好估计。客观上说每个球都有可能是次品，且能轻能重，似乎有2n个叶子节点;可是我们关心的是哪个是次品，具体的轻重无关紧要，因此n个不同的叶子节点足矣。
到底算n个还是2n个呢,之前的研究方法行不通了，要另辟蹊径。
设f(n)表示n个球时的最少称量次数。
先假设有无穷多个标准球，第一次取a个球在天平左边，b个球在天平右边(a?b)。由于天平两边的球数必须相等，所以在左边还补进b-a个标准球。
如果天平:
1、 左偏。有可能是左边a个球中有重球、或者右边b个球里有轻球，根
log(a，b)log(a，b)据上节引理，还要称次，因此总共称+1次。 ，，，，33
log(a，b)2、 右偏。类似1，也是称+1次。 ，，3
3、 平衡。次品必然在剩下的n-a-b个球中，要称f(n-a-b)次。
loga，b综上，此时称量次数是:max{, f(n-a-b)}+1次。 ，，3
注意到最后的称量次数只和a+b有关，因此可以对a, b适量调整，使得|a-b|?1，于是补充的标准球顶多1个，完全满足题目要求。
设a+b=p，则:
logpf(n) = min{max{, f(n-p)}+1} (1?p?n) ，，3
f(0)=0, f(1)=0, f(2)=1
这就是此问题的一个递推式，若对时间复杂度要求不高，如此既可求解。但是当n较大时，时空效率都是不能令人满意的，因此我们求出部分f(n)的值: N f(n)
1 0
2 1
3—5 2
6—14 3
15—41 4
42—122 5
很容易发现:f(n)= 。 log(2n,1)，，3
考虑从递推式入手来证明这个猜想。同样采用归纳法。
n=1,2时候容易验证猜想成立。
设n:
1. =Middle。次品在C中，问题归结到n=p时的问题5，还要称log(2p,1)log(2p,1)log(6p,3)log(2k,3)次。所以总共称+1==次。 ，，，，，，，，33332. =Left。可能是AH或者BL，问题归结到p+p时的引理，还要称log2plog2plog2k次。所以总共要称+1=次。 ，，，，，，333
log2k3. =Left。类似2，总共称次。 ，，3
log2klog(2k,1)综上，k=3p要称=次。 ，，，，33
情况二:k mod 3 = 1。设k=3p+1。
分成三堆A{S, 1, 2, …, p}, B{p+1,p+3,…,2p+1}, C{2p+2,2p+4,…,3p+1}，此时 |A|=p+1, |B|=p+1, |C|=p。特别注意在A中加入了一个标准球。称: 1. =Middle。次品在C中，问题归结到n=p时的问题5，还要称log(2p,1)log(2p,1)log(6p,3)log(2k,3)次。所以总共称+1==次。 ，，，，，，，，3333
2. =Left。可能是AH或者BL，问题归结到p+(p+1)时的引理(因为标准球不要考虑，所以是2p+1而不是2p+2)，还要称次。所以总共log(2p，1)，，3
要称log(2p，1)+1=log(2k，1)次。 ，，，，33
3. =Left。类似2，总共称log(2k，1)次。 ，，3
综上，k=3p+1要称log(2k，1)=log(2k,1)次。 ，，，，33
情况三:k mod 3 = 2。设k=3p+2。
分成三堆A{S, 1, 2, …, p}, B{p+1,p+3,…,2p+1}, C{2p+2,2p+4,…,3p+2}，此时 |A|=p+1, |B|=p+1, |C|=p+1。特别注意在A中加入了一个标准球。称:
1. =Middle。次品在C中，问题归结到n=p+1时的问题5，根据归纳假设还要称log[2(p，1),1]次。所以总共称，，3
log(2p，1)log(6p，3)log(2k,1)+1==次。 ，，，，，，333
2. =Left。可能是AH或者BL，问题归结到p+(p+1)时的猜想II(因为
log(2p，1)标准球不要考虑，所以是2p+1而不是2p+2)，还要称次。所以总，，3
log(2p，1)log(2k,1)共要称+1=次。 ，，，，33
log(2k,1)3. =Left。类似2，总共称次。 ，，3
log(2k,1)综上，k=3p+2要称次。 ，，3
log(2k,1)综合三种情况，f(n) ?。 ，，3
log(2k,1)最优性和可行性均证，故而f(n)= 。 ，，3
我们的结论是:
给定一架天平和一个标准球，从n个球中找出不知道轻重的次品至少要称log(2n,1)次。 ，，3
我们还可以把问题5中的标准球去掉(也就是变成本文一开始提出的问题2)，有兴趣的读者可以自己推导一下看看。
研究方法总结
本文的有关结论如下:(n?3)
给定一架天平，有n个球，其中一个是次品。
结论1 次品的重量比其他的重，称次就能找出那个次品。 logn，，3
结论2 轻重不详。有一个标准球。称log2n次就可以找到次品，并且知道，，3
轻重。
结论3 轻重不详。称log(2n，2)次就可以找到次品，并且次品的轻重。 ，，3
结论4 轻重不详。有一个标准球，称log(2n,1)次就可以找出次品。 ，，3
当然，还可以变化出一些其他的形式，但是万变不离其宗，只要牢牢抓住以一个原则:“均匀”，任何此类问题都能迎刃而解。
本文全面而严格的提出了“天平称物”这一类问题的统一解法;在给出解法和有关结论的同时，特别重视对思路的产生过程作重点地阐述。
在研究此类问题的过程中我们得到了不少有益的经验:
、从简单入手。这是本文的构篇基础。从简单的问题1步步深入，一直到1
;从有标准球开始研究，进而推广到无标准球的情况;从要求次较复杂的问题5
品的轻重情况，到只要求次品„„这些无不包含着“从简单入手”这一重要研究手段。
2、总结经验，合理外推。通过将研究问题1而获得的部分经验进行合理的推广，我们在解决其后的难题时都能够很快的产生初步思路、迅速踏上正轨。
3、求同存异。世界上没有两片相同的叶子。哪怕是一个条件发生了细微的改动，题目的结构也许就发生了本质的变化。因此在推广的同时必须谨慎的考虑问题的相异性，做出积极的调整。
4、大胆猜想，严格证明。思路不甚明朗的时候，猜想就是一个很好的突破口。本文最重要的几个结论以及最后的问题5，都是通过猜想取得进一步进展的。
附录
1、本文作者针对问题3，编写了一个简单的模拟程序。Game.pas
2、判定树还可以用来证明:任何一个借助“比较”进行排序的算法，在最
logn!坏情况下所需要的比较次数至少为;根据斯特林公式，有，，2
logn!=O(nlogn)。因此O(nlogn)是借助比较法排序的理论时间复杂度下，，2
界(快速排序、堆排序均是这个数量级的)。本文借助了这一思想，用来
证明某些天平称物问题的最优性。具体的判定树
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
可以在参考书籍的
P292找到。
参考书籍
数据结构(第二版)，清华大学出版社，严蔚敏 吴伟民 编著
浙公网安备 33021202002483