用天平3下可将它称出
如何证明答案（即称法）的唯一性？
（注：答案为
1，2，3，4， 5，6，7，8， 9，10，11，12
三组
称其中两组（比如1，2，3，4 vs 5，6，7，8）
如质量相等->容易得到结果
若不等则：
将其中一组中的3个拿掉，另一组中的三个那过来，剩下的4个中拿三个进来补到这组
接下去容易分析出结果）
最好用程序实现
7 个解决方案
#1
路过
#2
这个太容易了。分成三组，取两组放天平两边。如平衡则在另外一个中。
如不平衡则在轻的一个中。（假定那一个轻）
然后将一组中的四个分成两组重复以上。则三次可完成。
如不平衡则在轻的一个中。（假定那一个轻）
然后将一组中的四个分成两组重复以上。则三次可完成。
#3
兄弟，这是个关于对称性的遍历设计难题，没象你说得这么容易，而且正确解法之一我已经给出了。
#4
偶不知道咯，偶知道前两天有人问过咯
呵呵
呵呵
#5
俺有个问题不明白，你说
“称其中两组（比如1，2，3，4 vs 5，6，7，8）
如质量相等->容易得到结果”
怎么得到结果啊？你又没说那个特殊的球的质量是大还是小，
如果最后得到9质量小于10，谁是特殊的啊？？
“称其中两组（比如1，2，3，4 vs 5，6，7，8）
如质量相等->容易得到结果”
怎么得到结果啊？你又没说那个特殊的球的质量是大还是小，
如果最后得到9质量小于10，谁是特殊的啊？？
#6
转载......
称球问题算法分析
称球问题是中学生计算机竞赛中经常碰到的一类问题，下面我们就称球问题的算法分析一下。
问题：设有ｎ 个形状相同的球，其中有一个球的重量和其他的球不同，我们称此球为坏球，同时有一个无刻度无砝码的天平，要求用天平称最少的次数找出此坏球。下面分两种情况分别讨论。
一、坏球比一般球重（轻的情况类似）
ｎ（球的个数）称法（每次称时，天平两边球数相同）１０次称重，本身为坏球，不用称２１次称重，称两个球，较重的球为坏球３１次称重，称两个球（１）若平衡，则未称的球为坏球（２）不平衡，则较重的球为坏球由上可知，１次可保证称出坏球的球总数最多为３。４２次称重，第一次称两个球（１）若平衡，坏球在未称的２个球中，第二次称这２个球，较重者为坏球（２）不平衡，较重者为坏球……９２次称重，第一次称６个球（１）若平衡，则坏球在未称的三个球中，从上面ｎ ＝３的情况可知，再称一次可称出坏球（２）不平衡，则坏球在较重的一边，同样再称一次可称出坏球由上可知，２次最多能保证称出总数为９个球中的坏球。可以推导出球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（ｎ －１）＋１（其中表示向下取整运算）例如３次最多可称出２７个球中的坏球，称法为第一次先称１８个球：（１）若平衡，则坏球在未称的９个球中，同时９个球最多称２次即可找出坏球；（２）不平衡，则坏球在较重的９个球中，同时９个球最多称２次即可找出坏球。
二、未知坏球的轻重
这类问题较上面的情况要复杂得多，如下：ｎ（球的个数）称法１０次，即本身是坏球，不用称２不可能问题，无论如何都称不出坏球３２次称重，第一次称①②两球，③不称可能出现三种情况：（１）相等，③为坏球（２）①＜②，此时①轻或②重第二次称①③：平衡，②为坏球（重）不平衡，①为坏球（轻）（３）①＞②，情况类似（２）４２次称重，第一次称①②两球，③④不称（１）平衡，则坏球在③④中，①②为好球第二次称①③：平衡，则④为坏球；不平衡，则③为坏球（２）不平衡，则①②中有一个坏球，③④为好球第二次称①③：平衡，则②为坏球；不平衡，则①为坏球可以看出，２次最多能保证称出４个球中的坏球。
在此情况下，球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（２ｎ）＋１例如ｎ ＝１３时，ｌｏｇ３（２＊１３）＋３，即３次可称出。算法如下：第一次称①②③④和⑤⑥⑦⑧８个球，⑨⑩不称。可能出现三种情况：Ⅰ平衡，则①②③④⑤⑥⑦⑧为好球，坏球在⑨⑩中。第二次称⑨⑩和①，又可能有三种情况：（１）平衡，则坏球在中。第三次称①和：平衡，则为坏球；不平衡，则为坏球。（２）⑨⑩〉①，则此时有两种可能性：Ａ ⑨⑩中有一个重的；Ｂ 为轻的。第三次称⑨和⑩：平衡，则为坏球；不平衡，则重者为坏球。（３）⑨⑩＜①，方法与２类同。Ⅱ①②③④＞⑤⑥⑦⑧此时可知⑨⑩为好球，且有两种可能：①②③④中有一个重的，或⑤⑥⑦⑧中有一个轻的。第二次称⑨⑩⑤④和③⑥⑦８个球，①②⑧不称。此时又有三种情况：（１）平衡，则坏球在①②⑧中。第三次称①和②：平衡，⑧为坏球；不平衡，重者为坏球。（２）⑨⑩⑤④＞③⑥⑦，可知⑤③①②⑧均为好球，坏球在④⑥⑦中。第三次称⑥和⑦：平衡，坏球为④；不平衡，轻者为坏球。（３）⑨⑩⑤④＜③⑥⑦，可知在③⑤中有一个坏球。第三次称③和⑩：平衡，⑤为坏球；不平衡，③为坏球。Ⅲ①②③④＜⑤⑥⑦⑧，其方法与Ⅱ类同。由上面的例子可以看出求解称球问题的算法基本上是将球分成大体相等的三份，其中两份数目相同用于第一次称重，第三份球的个数与前两份的个数最多相差一个，这样就可以尽快地把坏球限制在最小的范围里。另外还要充分利用球的轻重和球的搭配。掌握了这些基本技巧，加以灵活运用，就可以解决各种类型的称球问题。下面我们再看一个例子。在ｎ ＝５的情况下：１．若不知球的重量，也无好球作标准，最多需要三次可称出坏球。算法如下：第一次称①②和③④：（１）平衡，⑤为坏球；（２）①②＞③④，则在①②中有一个重的，或③④中有一个轻的。第二次称①和②：不平衡，重者为坏球；平衡，则第三次称③和④：轻者为坏球。（３）①②＜③④，称法与（２）类同。２．若有好球作为标准，则称２次就可找出坏球。算法如下（设◎为好球）：第一次称①②和③◎：（１）平衡，坏球在④⑤中。第二次称④和◎：平衡，⑤为坏球；不平衡，④为坏球。（２）不平衡，又分两种情况：①②＞③◎，表示①②中有一个重的，或③为轻的第二次称①和②：平衡，③为坏球；不平衡，重者为坏球。①②＜③◎，方法与上类同。（江苏王剑星）
称球问题算法分析
称球问题是中学生计算机竞赛中经常碰到的一类问题，下面我们就称球问题的算法分析一下。
问题：设有ｎ 个形状相同的球，其中有一个球的重量和其他的球不同，我们称此球为坏球，同时有一个无刻度无砝码的天平，要求用天平称最少的次数找出此坏球。下面分两种情况分别讨论。
一、坏球比一般球重（轻的情况类似）
ｎ（球的个数）称法（每次称时，天平两边球数相同）１０次称重，本身为坏球，不用称２１次称重，称两个球，较重的球为坏球３１次称重，称两个球（１）若平衡，则未称的球为坏球（２）不平衡，则较重的球为坏球由上可知，１次可保证称出坏球的球总数最多为３。４２次称重，第一次称两个球（１）若平衡，坏球在未称的２个球中，第二次称这２个球，较重者为坏球（２）不平衡，较重者为坏球……９２次称重，第一次称６个球（１）若平衡，则坏球在未称的三个球中，从上面ｎ ＝３的情况可知，再称一次可称出坏球（２）不平衡，则坏球在较重的一边，同样再称一次可称出坏球由上可知，２次最多能保证称出总数为９个球中的坏球。可以推导出球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（ｎ －１）＋１（其中表示向下取整运算）例如３次最多可称出２７个球中的坏球，称法为第一次先称１８个球：（１）若平衡，则坏球在未称的９个球中，同时９个球最多称２次即可找出坏球；（２）不平衡，则坏球在较重的９个球中，同时９个球最多称２次即可找出坏球。
二、未知坏球的轻重
这类问题较上面的情况要复杂得多，如下：ｎ（球的个数）称法１０次，即本身是坏球，不用称２不可能问题，无论如何都称不出坏球３２次称重，第一次称①②两球，③不称可能出现三种情况：（１）相等，③为坏球（２）①＜②，此时①轻或②重第二次称①③：平衡，②为坏球（重）不平衡，①为坏球（轻）（３）①＞②，情况类似（２）４２次称重，第一次称①②两球，③④不称（１）平衡，则坏球在③④中，①②为好球第二次称①③：平衡，则④为坏球；不平衡，则③为坏球（２）不平衡，则①②中有一个坏球，③④为好球第二次称①③：平衡，则②为坏球；不平衡，则①为坏球可以看出，２次最多能保证称出４个球中的坏球。
在此情况下，球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（２ｎ）＋１例如ｎ ＝１３时，ｌｏｇ３（２＊１３）＋３，即３次可称出。算法如下：第一次称①②③④和⑤⑥⑦⑧８个球，⑨⑩不称。可能出现三种情况：Ⅰ平衡，则①②③④⑤⑥⑦⑧为好球，坏球在⑨⑩中。第二次称⑨⑩和①，又可能有三种情况：（１）平衡，则坏球在中。第三次称①和：平衡，则为坏球；不平衡，则为坏球。（２）⑨⑩〉①，则此时有两种可能性：Ａ ⑨⑩中有一个重的；Ｂ 为轻的。第三次称⑨和⑩：平衡，则为坏球；不平衡，则重者为坏球。（３）⑨⑩＜①，方法与２类同。Ⅱ①②③④＞⑤⑥⑦⑧此时可知⑨⑩为好球，且有两种可能：①②③④中有一个重的，或⑤⑥⑦⑧中有一个轻的。第二次称⑨⑩⑤④和③⑥⑦８个球，①②⑧不称。此时又有三种情况：（１）平衡，则坏球在①②⑧中。第三次称①和②：平衡，⑧为坏球；不平衡，重者为坏球。（２）⑨⑩⑤④＞③⑥⑦，可知⑤③①②⑧均为好球，坏球在④⑥⑦中。第三次称⑥和⑦：平衡，坏球为④；不平衡，轻者为坏球。（３）⑨⑩⑤④＜③⑥⑦，可知在③⑤中有一个坏球。第三次称③和⑩：平衡，⑤为坏球；不平衡，③为坏球。Ⅲ①②③④＜⑤⑥⑦⑧，其方法与Ⅱ类同。由上面的例子可以看出求解称球问题的算法基本上是将球分成大体相等的三份，其中两份数目相同用于第一次称重，第三份球的个数与前两份的个数最多相差一个，这样就可以尽快地把坏球限制在最小的范围里。另外还要充分利用球的轻重和球的搭配。掌握了这些基本技巧，加以灵活运用，就可以解决各种类型的称球问题。下面我们再看一个例子。在ｎ ＝５的情况下：１．若不知球的重量，也无好球作标准，最多需要三次可称出坏球。算法如下：第一次称①②和③④：（１）平衡，⑤为坏球；（２）①②＞③④，则在①②中有一个重的，或③④中有一个轻的。第二次称①和②：不平衡，重者为坏球；平衡，则第三次称③和④：轻者为坏球。（３）①②＜③④，称法与（２）类同。２．若有好球作为标准，则称２次就可找出坏球。算法如下（设◎为好球）：第一次称①②和③◎：（１）平衡，坏球在④⑤中。第二次称④和◎：平衡，⑤为坏球；不平衡，④为坏球。（２）不平衡，又分两种情况：①②＞③◎，表示①②中有一个重的，或③为轻的第二次称①和②：平衡，③为坏球；不平衡，重者为坏球。①②＜③◎，方法与上类同。（江苏王剑星）
#7
我不要答案，答案我早有了。
我要答案的唯一性证明
faint~~~
我要答案的唯一性证明
faint~~~
#1
路过
#2
这个太容易了。分成三组，取两组放天平两边。如平衡则在另外一个中。
如不平衡则在轻的一个中。（假定那一个轻）
然后将一组中的四个分成两组重复以上。则三次可完成。
如不平衡则在轻的一个中。（假定那一个轻）
然后将一组中的四个分成两组重复以上。则三次可完成。
#3
兄弟，这是个关于对称性的遍历设计难题，没象你说得这么容易，而且正确解法之一我已经给出了。
#4
偶不知道咯，偶知道前两天有人问过咯
呵呵
呵呵
#5
俺有个问题不明白，你说
“称其中两组（比如1，2，3，4 vs 5，6，7，8）
如质量相等->容易得到结果”
怎么得到结果啊？你又没说那个特殊的球的质量是大还是小，
如果最后得到9质量小于10，谁是特殊的啊？？
“称其中两组（比如1，2，3，4 vs 5，6，7，8）
如质量相等->容易得到结果”
怎么得到结果啊？你又没说那个特殊的球的质量是大还是小，
如果最后得到9质量小于10，谁是特殊的啊？？
#6
转载......
称球问题算法分析
称球问题是中学生计算机竞赛中经常碰到的一类问题，下面我们就称球问题的算法分析一下。
问题：设有ｎ 个形状相同的球，其中有一个球的重量和其他的球不同，我们称此球为坏球，同时有一个无刻度无砝码的天平，要求用天平称最少的次数找出此坏球。下面分两种情况分别讨论。
一、坏球比一般球重（轻的情况类似）
ｎ（球的个数）称法（每次称时，天平两边球数相同）１０次称重，本身为坏球，不用称２１次称重，称两个球，较重的球为坏球３１次称重，称两个球（１）若平衡，则未称的球为坏球（２）不平衡，则较重的球为坏球由上可知，１次可保证称出坏球的球总数最多为３。４２次称重，第一次称两个球（１）若平衡，坏球在未称的２个球中，第二次称这２个球，较重者为坏球（２）不平衡，较重者为坏球……９２次称重，第一次称６个球（１）若平衡，则坏球在未称的三个球中，从上面ｎ ＝３的情况可知，再称一次可称出坏球（２）不平衡，则坏球在较重的一边，同样再称一次可称出坏球由上可知，２次最多能保证称出总数为９个球中的坏球。可以推导出球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（ｎ －１）＋１（其中表示向下取整运算）例如３次最多可称出２７个球中的坏球，称法为第一次先称１８个球：（１）若平衡，则坏球在未称的９个球中，同时９个球最多称２次即可找出坏球；（２）不平衡，则坏球在较重的９个球中，同时９个球最多称２次即可找出坏球。
二、未知坏球的轻重
这类问题较上面的情况要复杂得多，如下：ｎ（球的个数）称法１０次，即本身是坏球，不用称２不可能问题，无论如何都称不出坏球３２次称重，第一次称①②两球，③不称可能出现三种情况：（１）相等，③为坏球（２）①＜②，此时①轻或②重第二次称①③：平衡，②为坏球（重）不平衡，①为坏球（轻）（３）①＞②，情况类似（２）４２次称重，第一次称①②两球，③④不称（１）平衡，则坏球在③④中，①②为好球第二次称①③：平衡，则④为坏球；不平衡，则③为坏球（２）不平衡，则①②中有一个坏球，③④为好球第二次称①③：平衡，则②为坏球；不平衡，则①为坏球可以看出，２次最多能保证称出４个球中的坏球。
在此情况下，球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（２ｎ）＋１例如ｎ ＝１３时，ｌｏｇ３（２＊１３）＋３，即３次可称出。算法如下：第一次称①②③④和⑤⑥⑦⑧８个球，⑨⑩不称。可能出现三种情况：Ⅰ平衡，则①②③④⑤⑥⑦⑧为好球，坏球在⑨⑩中。第二次称⑨⑩和①，又可能有三种情况：（１）平衡，则坏球在中。第三次称①和：平衡，则为坏球；不平衡，则为坏球。（２）⑨⑩〉①，则此时有两种可能性：Ａ ⑨⑩中有一个重的；Ｂ 为轻的。第三次称⑨和⑩：平衡，则为坏球；不平衡，则重者为坏球。（３）⑨⑩＜①，方法与２类同。Ⅱ①②③④＞⑤⑥⑦⑧此时可知⑨⑩为好球，且有两种可能：①②③④中有一个重的，或⑤⑥⑦⑧中有一个轻的。第二次称⑨⑩⑤④和③⑥⑦８个球，①②⑧不称。此时又有三种情况：（１）平衡，则坏球在①②⑧中。第三次称①和②：平衡，⑧为坏球；不平衡，重者为坏球。（２）⑨⑩⑤④＞③⑥⑦，可知⑤③①②⑧均为好球，坏球在④⑥⑦中。第三次称⑥和⑦：平衡，坏球为④；不平衡，轻者为坏球。（３）⑨⑩⑤④＜③⑥⑦，可知在③⑤中有一个坏球。第三次称③和⑩：平衡，⑤为坏球；不平衡，③为坏球。Ⅲ①②③④＜⑤⑥⑦⑧，其方法与Ⅱ类同。由上面的例子可以看出求解称球问题的算法基本上是将球分成大体相等的三份，其中两份数目相同用于第一次称重，第三份球的个数与前两份的个数最多相差一个，这样就可以尽快地把坏球限制在最小的范围里。另外还要充分利用球的轻重和球的搭配。掌握了这些基本技巧，加以灵活运用，就可以解决各种类型的称球问题。下面我们再看一个例子。在ｎ ＝５的情况下：１．若不知球的重量，也无好球作标准，最多需要三次可称出坏球。算法如下：第一次称①②和③④：（１）平衡，⑤为坏球；（２）①②＞③④，则在①②中有一个重的，或③④中有一个轻的。第二次称①和②：不平衡，重者为坏球；平衡，则第三次称③和④：轻者为坏球。（３）①②＜③④，称法与（２）类同。２．若有好球作为标准，则称２次就可找出坏球。算法如下（设◎为好球）：第一次称①②和③◎：（１）平衡，坏球在④⑤中。第二次称④和◎：平衡，⑤为坏球；不平衡，④为坏球。（２）不平衡，又分两种情况：①②＞③◎，表示①②中有一个重的，或③为轻的第二次称①和②：平衡，③为坏球；不平衡，重者为坏球。①②＜③◎，方法与上类同。（江苏王剑星）
称球问题算法分析
称球问题是中学生计算机竞赛中经常碰到的一类问题，下面我们就称球问题的算法分析一下。
问题：设有ｎ 个形状相同的球，其中有一个球的重量和其他的球不同，我们称此球为坏球，同时有一个无刻度无砝码的天平，要求用天平称最少的次数找出此坏球。下面分两种情况分别讨论。
一、坏球比一般球重（轻的情况类似）
ｎ（球的个数）称法（每次称时，天平两边球数相同）１０次称重，本身为坏球，不用称２１次称重，称两个球，较重的球为坏球３１次称重，称两个球（１）若平衡，则未称的球为坏球（２）不平衡，则较重的球为坏球由上可知，１次可保证称出坏球的球总数最多为３。４２次称重，第一次称两个球（１）若平衡，坏球在未称的２个球中，第二次称这２个球，较重者为坏球（２）不平衡，较重者为坏球……９２次称重，第一次称６个球（１）若平衡，则坏球在未称的三个球中，从上面ｎ ＝３的情况可知，再称一次可称出坏球（２）不平衡，则坏球在较重的一边，同样再称一次可称出坏球由上可知，２次最多能保证称出总数为９个球中的坏球。可以推导出球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（ｎ －１）＋１（其中表示向下取整运算）例如３次最多可称出２７个球中的坏球，称法为第一次先称１８个球：（１）若平衡，则坏球在未称的９个球中，同时９个球最多称２次即可找出坏球；（２）不平衡，则坏球在较重的９个球中，同时９个球最多称２次即可找出坏球。
二、未知坏球的轻重
这类问题较上面的情况要复杂得多，如下：ｎ（球的个数）称法１０次，即本身是坏球，不用称２不可能问题，无论如何都称不出坏球３２次称重，第一次称①②两球，③不称可能出现三种情况：（１）相等，③为坏球（２）①＜②，此时①轻或②重第二次称①③：平衡，②为坏球（重）不平衡，①为坏球（轻）（３）①＞②，情况类似（２）４２次称重，第一次称①②两球，③④不称（１）平衡，则坏球在③④中，①②为好球第二次称①③：平衡，则④为坏球；不平衡，则③为坏球（２）不平衡，则①②中有一个坏球，③④为好球第二次称①③：平衡，则②为坏球；不平衡，则①为坏球可以看出，２次最多能保证称出４个球中的坏球。
在此情况下，球的总数（ｎ）和最少称重次数（ｋ）的关系的一般公式为：ｋ＝ｌｏｇ ３（２ｎ）＋１例如ｎ ＝１３时，ｌｏｇ３（２＊１３）＋３，即３次可称出。算法如下：第一次称①②③④和⑤⑥⑦⑧８个球，⑨⑩不称。可能出现三种情况：Ⅰ平衡，则①②③④⑤⑥⑦⑧为好球，坏球在⑨⑩中。第二次称⑨⑩和①，又可能有三种情况：（１）平衡，则坏球在中。第三次称①和：平衡，则为坏球；不平衡，则为坏球。（２）⑨⑩〉①，则此时有两种可能性：Ａ ⑨⑩中有一个重的；Ｂ 为轻的。第三次称⑨和⑩：平衡，则为坏球；不平衡，则重者为坏球。（３）⑨⑩＜①，方法与２类同。Ⅱ①②③④＞⑤⑥⑦⑧此时可知⑨⑩为好球，且有两种可能：①②③④中有一个重的，或⑤⑥⑦⑧中有一个轻的。第二次称⑨⑩⑤④和③⑥⑦８个球，①②⑧不称。此时又有三种情况：（１）平衡，则坏球在①②⑧中。第三次称①和②：平衡，⑧为坏球；不平衡，重者为坏球。（２）⑨⑩⑤④＞③⑥⑦，可知⑤③①②⑧均为好球，坏球在④⑥⑦中。第三次称⑥和⑦：平衡，坏球为④；不平衡，轻者为坏球。（３）⑨⑩⑤④＜③⑥⑦，可知在③⑤中有一个坏球。第三次称③和⑩：平衡，⑤为坏球；不平衡，③为坏球。Ⅲ①②③④＜⑤⑥⑦⑧，其方法与Ⅱ类同。由上面的例子可以看出求解称球问题的算法基本上是将球分成大体相等的三份，其中两份数目相同用于第一次称重，第三份球的个数与前两份的个数最多相差一个，这样就可以尽快地把坏球限制在最小的范围里。另外还要充分利用球的轻重和球的搭配。掌握了这些基本技巧，加以灵活运用，就可以解决各种类型的称球问题。下面我们再看一个例子。在ｎ ＝５的情况下：１．若不知球的重量，也无好球作标准，最多需要三次可称出坏球。算法如下：第一次称①②和③④：（１）平衡，⑤为坏球；（２）①②＞③④，则在①②中有一个重的，或③④中有一个轻的。第二次称①和②：不平衡，重者为坏球；平衡，则第三次称③和④：轻者为坏球。（３）①②＜③④，称法与（２）类同。２．若有好球作为标准，则称２次就可找出坏球。算法如下（设◎为好球）：第一次称①②和③◎：（１）平衡，坏球在④⑤中。第二次称④和◎：平衡，⑤为坏球；不平衡，④为坏球。（２）不平衡，又分两种情况：①②＞③◎，表示①②中有一个重的，或③为轻的第二次称①和②：平衡，③为坏球；不平衡，重者为坏球。①②＜③◎，方法与上类同。（江苏王剑星）
#7
我不要答案，答案我早有了。
我要答案的唯一性证明
faint~~~
我要答案的唯一性证明
faint~~~