我列出十三个的求法,其中13号是不知大小的。if 1-4 > 5-8 then
if 1,2,3,5,6>9-13 then
if 1>2 then
1
elseif 1<2 then
2
else
3
endif
elseif 1,2,3,5,6=9-13 then
if 4>7 then
4
else if 4=7 then
8
endif
endif
elseif 1-4=5-8 then
if 1,2,3 > 9,10,11 then
if 9 <10 then
9
elseif 9>10 then
10
else
11
endif
else if 1,2,3=9,10,11 then
if 1>12 then
12
else
13 ''''''''这时13号是不知道偏大还是偏小.
endif
else
'与1,2,3 > 9,10,11相反
endif
else
'与1-4 > 5-8 相反
end if
if 1,2,3,5,6>9-13 then
if 1>2 then
1
elseif 1<2 then
2
else
3
endif
elseif 1,2,3,5,6=9-13 then
if 4>7 then
4
else if 4=7 then
8
endif
endif
elseif 1-4=5-8 then
if 1,2,3 > 9,10,11 then
if 9 <10 then
9
elseif 9>10 then
10
else
11
endif
else if 1,2,3=9,10,11 then
if 1>12 then
12
else
13 ''''''''这时13号是不知道偏大还是偏小.
endif
else
'与1,2,3 > 9,10,11相反
endif
else
'与1-4 > 5-8 相反
end if
if 1,2,3,5,6>9-13 then
if 1>2 then
1
elseif 1<2 then
2
else
3
endif
elseif 1,2,3,5,6=9-13 then
if 4>7 then
有兩種情況或者4偏大,或者7偏小
else if 4=7 then
8
endif
endif
elseif 1-4=5-8 then
if 1,2,3 > 9,10,11 then
if 9 <10 then
9
elseif 9>10 then
10
else
11
endif
else if 1,2,3=9,10,11 then
if 1>12 then
12
else
13 ''''''''这时13号是不知道偏大还是偏小.
endif
else
'与1,2,3 > 9,10,11相反
endif
else
'与1-4 > 5-8 相反
end if
|--右--( 1轻)
|--右--(1 ; 2)|--平--( 5重)
| |--左--( )
|
| |--右--( 2轻)
|--右--(1,6-8; |--平--(2 ; 3)|--平--( 4轻)
| 5,9-11)| |--左--( 3轻)
| |
| | |--右--( 7重)
| |--左--(6 ; 7)|--平--( 8重)
| |--左--( 6重)
|
| |--右--(10重)
| |--右--(9 ;10)|--平--(11重)
| | |--左--( 9重)
| |
| | |--右--(12重)
(1-4;5-8)|--平--(1-3; |--平--(1 ;12)|--平--(13轻, 13重)*
| 9-11)| |--左--(12轻)
| |
| | |--右--( 9轻)
| |--左--(9 ;10)|--平--(11轻)
| |--左--(10轻)
|
| |--右--( 6轻)
| |--右--(6 ; 7)|--平--( 8轻)
| | |--左--( 7轻)
| |
| | |--右--( 3重)
|--左--(1,6-8; |--平--(2 ; 3)|--平--( 4重)
5,9-11)| |--左--( 2重)
|
| |--右--( )
|--左--(1 ; 2)|--平--( 5轻)
|--左--( 1重)
(*:对应十三个球的情形。)
这里“右”、“平”和“左”分别表示称量的结果为“右重”、“平
衡”和“左重”所对应的分支。在树的叶子(就是最右边没有子节点
的那些节点)部分,我们标出了“能够到达”这些节点的布局,也就
是说在进行每一节点上的称量时,这个布局所给的结果和通往相对应
的叶子的道路上所标出的“右”、“平”和“左”相符合。从这个图
我们也可以清楚地看到,根下的左分支和右分支是对称的:只需要把
所有的“右”改成“左”,“左”改成“右”,“轻”改成“重”,
“重”改成“轻”;节点(1-3; 9-11)下的左分支和右分支也有这个
特点。 (如果有朋友对树理论感兴趣,可以参考随便哪一本图论或者离
散数学的书。在这里我们只用到树理论里最基本的知识,所用的名词
和结论都是相当直观的。所以如果你不知道树理论,用不着特别去学
也可以看懂这里的论证。) 所以给定一棵三分树(就是说除了叶子以外其他的节点都有三个
子节点的树),在每个不是叶子的节点上给定一个称量,并且规定这
个节点下的三个分支(子树)分别对应右重、平衡、左重的情况,我
们就得到了一种称球的方法。我们把这样一棵三分树称为一个“策略”
或一棵“策略树”。你可以给出一个平凡的策略,比如说无论发生了
什么事总是把1号和2号球放在左右两侧来称(在叶子上我们没有写出
相应的布局,用@来代替): |--右--@A
|--右--(1; 2)|--平--@
| |--左--@
|
| |--右--@
(1; 2)|--平--(1; 2)|--平--@
| |--左--@
|
| |--右--@B
| |--右--(1; 2)|--平--@
| | |--左--@
| |
| | |--右--@
|--左--(1; 2)|--平--(1; 2)|--平--@
| |--左--@
|
| |--右--@
|--左--(1; 2)|--平--@
|--左--@当然这么个策略没什么用场,只能让我们知道1号球和2号球之间的轻
重关系。另外我们看到,每个分支不一定一样长,上面这棵策略树根
下面左分支就比较长。 一棵树的高度是叶子到根之间的结点数的最大值加一。比如说上
面这个图中,叶子A和根间有1个节点,而叶子B和根间有2个节点,没
有和根之间的节点数超过2的叶子。所以它的高度是2+1=3。前面十二
球解法策略树的高度也是3。一棵没有任何分支,只有根节点的树,我
们定义它的高度是0。 显然,策略树的高度就是实行这个策略所需要的称量的次数。我
们的目的,就是找到一棵“好”的策略树,使得它的高度最小。 什么是“好”策略?我们回过头来再看十二球解法策略树。我们
说过,叶子上的那些布局都是从根开始通向叶子的。比如说布局(7重),
它之所以在那片叶子上是因为按照这个策略,三次称量的结果是“右
左右”;又比如说布局(11重),它之所以在那片叶子上是因为按照这
个策略,三次称量的结果是“平右平”。如果两个布局通向同一片叶
子,那么就是说按照这个策略,三次称量的结果是完全一样的,于是
我们就不能通过这个策略来把这两种布局区分开来。比如说在十三个
球的情况下,(13轻)和(13重)都通向和“平平平”相对应的叶子,这
两个布局中13号球或者轻或者重,于是我们知道13号球一定是坏球,
但是通过这个策略我们不可能知道它到底是轻还是重。 所以对于标准的称球问题(找出坏球并知其比标准球重或轻)的
“好”策略,就是那些能使不同的布局通向不同的叶子的策略。