天平称球问题

称小球问题终结----关于所能解决的上限     现在来求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k> 3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，
只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明：很显然，若k> 3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k> 3^L知不可能一定分辨出哪个球是坏球。引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作 "砝码 "用）?br   />   则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是
两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)> =2。
而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用
过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下
的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1) <3。
由N1max(1) <3和N1max(1)> =2知，N1max=2。
设当m <=k-1时命题都成立，则考虑m=k的情况。
第一次称不能使用超过3^(k-1)个未知球，否则如果坏球在这超过3^(k-1)个
球中的话，由引理一，在剩下的(k-1)次中不能肯定找出这个坏球来?br   />   另外，若第一次称碰到的都是好球，则第一次称后的结果就是多提供了一些
标准球（这个结果对已经提供了任意个标准球的情况是毫无意义的）和缩小
坏球的范围到剩下的球中。由归纳假设，剩下的球的数目不超过N1max(k-1)
才能保证一定能称出来。所以：N1max(k) <=3^(k-1)+N1max(k-1)=(3^k+1)/2。
如果有(3^k+1)/2个未知球，则第一次将3^(k-1)个未知球和提供的3^(k-1)个
未知球比较：如果相等，则坏球在剩下的N1max(k-1)个中，由归纳假设能分
出来；如果不等，则坏球在这3^(k-1)个中，但是同时知道了坏球是轻还是
重，由三分法可以很容易用k-1次找出来。所以对于(3^k+1)/2个未知球的情
况，是能够用k次找出坏球来的。即N1max(k)> =(3^k+1)/2.
由前面的推导知，N1max(k)=(3^k+1)/2。所以m=k时命题也成立。
由数学归纳法,所以N1max(k)=(3^k+1)/2对所有的自然数k都成立。
引理二得证。引理三：Nmax(m) <=(3^m-1)/2。(m> =2)
证明：在原来的称小球问题中，起初没有提供标准球，所以第一次称的数目必须是偶数，
由和引理二中推导N1max(m)时类似，有如下结论：
Nmax(m) <=N1max(m-1)   +   [3^(m-1)-1]   若第一次称平衡了最多剩下的球数   第一次称最多使用的球数，必须是偶数
所以Nmax(m) <=(3^m-1)/2=N1max(m)-1。命题得证。到此为止，我们求出了称小球问题的一个上界Nmax(m) <=(3^m-1)/2。（m> =2)
在后面我们将证明这是一个上确界，即Nmax(m)=(3^m-1)/2。
对于m=1的情况，由于必须有两个以上球（否则无所谓好坏球），所以一次是怎么也称不
出来的，因此我们不讨论m=1的情况。对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很
简单，在此略去?br   />   其次，若m?lt;=k-1时，假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
现在来考虑m=k的情况。
第一次称取[3^(k-1)-1]个球放在天平天平两端，则：
如果平衡，获得[3^(k-1)-1]个标准球，坏球在剩下的[3^(k-1)+1]/2个中。由于
[3^(k-1)-1]> =[3^(k-1)+1]/2，（k> =2),即已知的标准球数不小于未知球数?br   />   所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
对于[3^(k-1)+1]/2的情况(k-1)次可解。
如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.
则现在我们有[3^(k-1)-1]/2个A球和B球，有[3^(k-1)+1]/2个C球。
第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?br   />   3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
如果左边大于右边，则说明是在左边的3^(k-2)个A球中质量大的为坏球；
如果左边等于右边，则说明是在第二次称时没用的3^(k-2)个B球中质量轻
的为坏球。以上两种情况都可以再用三分法(k-2)次解决，加上前两
次共k次解决。
如果左边小于右边，则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
数目的A球中。此时的情况和第二次开始时类似（只不过是k-1变成k-2).
用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况，这时
只需拿A球和标准球比较以下就行了。
因此在这种情况下也是可以最终用k次解决的。
由以上两步加上数学归纳法知，对于N(m)=(3^m-1)/2的情况，称m次是可以称出来的。由这个解法加上前面所给出的上界Nmax(m) <=(3^m-1)/2，知称m次能解决的最大的小球数
Nmax(m)=(3^m-1)/2。
有兴趣的人可以验证一下m=3,N=13的情况----该情况已经被反复拿出来讨论过了。

楼主你这n个球算法不怎么好写但是我写过12个球的问题你这拓展成N个球就有点难度了上班那没时间研究你的N个球了其实楼主可以先研究一下12个球知道答题思路就ok了因为牵扯到不同个数的球分组方案也不一样楼主直接来一个N个球那就太夸张了感觉没必要这么深入毕竟算法只是活动大脑而不是摧残大脑

n>2,弱弱的问这是不是有什么规律呀~

import java.util.Arrays;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
public class Test2 {

static Map<Integer,String> map = new TreeMap<Integer,String>();
static StringBuffer sb = new StringBuffer();
static int count = 0;

public static void main(String[] args) {
int[] arr = input();
boolean flag = check(arr);
if(!flag) {
weigh(arr);
}

//打印结果
Set<Integer> keys = map.keySet();
Iterator<Integer> iterator = keys.iterator();
Integer key = iterator.next();
System.out.println("所称的次数为：" + key + ",所用的方案是：\n" + map.get(key));
}

/**
* 输入小球的个数，生成小球的数组，给每个小球一个质量，然后随机出一个不标准的小球，给其一个不同于其他的质量。
* @return 小球质量的数组
*/
private static int[] input() {
Scanner input = new Scanner(System.in);
System.out.println("请输入一个小球的个数(n>=3):");
int num = input.nextInt();
if(num < 3) {
System.out.println("小球数必须大于等于3！");
System.exit(0);
}

int[] arr = new int[num];
for(int i=0; i<arr.length; i++) {
arr[i] = 10;//假设每个小球的标准重量为10
}

//随机改变某个小球的重量,当i为偶数时增加重量，否则减少重量
Random random = new Random();
int i = random.nextInt(arr.length);
if(i % 2 == 0) {
arr[i] += 5;
} else {
arr[i] -= 5;
}
System.out.print("小球的重量：");
System.out.println(Arrays.toString(arr));
return arr;
}

/**
* 先取前三个小球称，要么称出标准的小球的重量，要么称出不标准的球，在这种情况下，称的次数已经是最小的了。
* @param arr 待称的小球的数组
* @param start 称的小球的开始小标
* @return 若找出了不标准的小球，返回true，否则返回false
*/
private static boolean check(int[] arr) {
boolean flag = false;

if(arr[0] == arr[1]) {
count++;
sb.append("称第1个和第2个球;");
if(arr[0] == arr[2]) {
//不标准的球在剩下的分组中
count++;
sb.append("称第1个和第3个球;");
} else {
//不标准的球为3
count++;
sb.append("称第1个和第3个球,不标准的球为3!");
map.put(count,sb.toString());
}
} else {
count++;
sb.append("称第1个和第2个球;");
if(arr[0] == arr[2]) {
//不标准的球为2
count++;
sb.append("称第1个和第3个球,不标准的球为2!");
map.put(count,sb.toString());
} else {
//不标准的球为1
count++;
sb.append("称第1个和第3个球,不标准的球为1!");
map.put(count,sb.toString());
}
}

if(map.size() > 0) {
flag = true;
}

return flag;
}

/**
* 三个为一组进行称,剩余的不足三个的单独处理；若在一组中发现了不同的，就在这组里面继续找。
* @param arr
*/
private static void weigh(int[] arr) {
int num = count;
int standard = arr[0] + arr[1] + arr[2];//标准的三个小球的重量

//处理三个为一整组的情况
for(int j=1; j<arr.length/3; j++) {
if((arr[j*3] + arr[j*3+1] + arr[j*3+2]) == standard) {
//在这一组中未找到，继续在下面的组中找
num++;
sb.append("三个球为一组，称第1组(前三个球)和第" + (j+1) + "组;");
continue;
} else {
//在这一组中找到了，现在就来找是那个球不标准
num++;
sb.append("不标准的球在这三个里面，第" +(j * 3 + 1) + "个到第" + (j * 3 + 3) + "个小球;");
if(arr[0] == arr[j * 3]) {
num++;
sb.append("称第1个和第" + (j * 3 + 1) + "个球;");
if(arr[0] == arr[j * 3 + 1]) {
num++;
sb.append("称第1个和第" + (j * 3 + 2) + "个球,不标准的球为" + (j * 3 + 3) + "!");
map.put(num, sb.toString());
return;
} else {
num++;
sb.append("称第1个和第" + (j * 3 + 2) + "个球,不标准的球为" + (j * 3 + 2) + "!");
map.put(num, sb.toString());
return;
}
} else {
num++;
sb.append("称第1个和第" + (j * 3 + 1) + "个球,不标准的球为" + (j * 3 + 1) + "!");
map.put(num, sb.toString());
return;
}
}
}

//处理不足三个的情况，也就是多出来一个或两个的情况
if(arr.length % 3 == 1) {
sb.append("不标准的球为" + arr.length + "!");
map.put(num,sb.toString());
} else if(arr.length % 3 == 2) {
if(arr[0] == arr[arr.length - 1]) {
num++;
sb.append("称第1个和第" + arr.length + "个球,不标准的球为" + (arr.length - 1) + "!");
map.put(num, sb.toString());
} else {
num++;
sb.append("称第1个和第" + arr.length + "个球,不标准的球为" + arr.length + "!");
map.put(num, sb.toString());
}
}
}
}这里实现的是从N各小球中找出质量不同的一个小球的方法。

这道题不是单纯的随机设置某个球，然后查找出来即可，单纯从算法角度来看，要穷举所有情况以及所有方案，然后取出最佳方案12个球查找很简单
假设球编号为abcd efgh ijkl
我们分为3个组，每个if是一次比较，也就表示一次称量
if (weight(abcd)=weight(efgh)) { //第1次
    if (weight(abc) == weight(ijk)) { //第2次
        if (weight(a)>weight(l)) { //第3次
            System.out.println("l轻");
        } else if (weight(a)<weight(l)) { //第3次
            System.out.println("l重");
        } else { //第3次
            System.out.println("没有怀球");
        }
    } else if (weight(abc) > weight(ijk)) { //第2次
        if (weight(i) == weight(j)) { //第3次
            System.out.println("k轻");
        } else if (weight(i) > weight(j)) { //第3次
            System.out.println("j轻");
        } else { //第3次
            System.out.println("i轻");
        }
    } else { //第2次
        if (weight(i) == weight(j)) { //第3次
            System.out.println("k重");
        } else if (weight(i) > weight(j)) { //第3次
            System.out.println("i重");
        } else { //第3次
            System.out.println("j重");
        }
    }
} else if (weight(abcd)>weight(efgh)) { //第1次
    if (weight(chi) == weight(fgd)) {//第2次
        if (weight(ae) == weight(jk)) {//第3次
            System.out.println("b重");
        } else if (weight(ae) > weight(jk)) {//第3次
            System.out.println("a重");
        } else {//第3次
            System.out.println("e轻");
        }
    } else if (wight(chi) > weight(fgd)) {//第2次
        if (weight(cf) == weight(jk)) {//第3次
            System.out.println("g轻");
        } else if (weight(cf) > weight(jk)) {//第3次
            System.out.println("c重");
        } else {//第3次
            System.out.println("f轻");
        }
    } else {//第2次
        if (weight(d) == weight(j)) {//第3次
            System.out.println("h轻");
        } else if (weight(d) > weight(j)) {//第3次
            System.out.println("d重");
        } else {//第3次
            System.out.println("这是不可能的，你肯定错了");
        }
    }
} else { //第1次
    if (weight(chi) == weight(fgd)) {//第2次
        if (weight(ae) == weight(jk)) {//第3次
            System.out.println("b轻");
        } else if (weight(ae) > weight(jk)) {//第3次
            System.out.println("e重");
        } else {//第3次
            System.out.println("a轻");
        }
    } else if (wight(chi) < weight(fgd)) {//第2次
        if (weight(cf) == weight(jk)) {//第3次
            System.out.println("g重");
        } else if (weight(cf) > weight(jk)) {//第3次
            System.out.println("f重");
        } else {//第3次
            System.out.println("c轻");
        }
    } else {//第2次
        if (weight(d) == weight(j)) {//第3次
            System.out.println("h重");
        } else if (weight(d) < weight(j)) {//第3次
            System.out.println("d轻");
        } else {//第3次
            System.out.println("这是不可能的，你肯定错了");
        }
    }
}

我补充解释下呵，题目的意思是找到一种称法，无论次品球是怎么分布的，都能被找出来。
即这种称法能处理任何情况，并且无论何种情况下，所称的次数不超过X
这种称法的X小于等于其它任何称法的X，即称此X为最少需要的称量次数因为要逻辑严密地表达这个意思要多打很多字，所以题目选择了一种简单的说法，希望不要导致误会

这是学java 的必经之路么？

把12个球编成1，2......12号，则可设计下面的称法：左盘 *** 右盘第一次 1，5，6，12 *** 2，3，7，11 第二次 2，4，6，10 *** 1，3，8，12 第三次 3，4，5，11 *** 1，2，9，10 每次都可能有平、左重、右重三种结果，搭配起来共有27种结果，但平、平、平的结果不会出现，因为总有一个球是不相等的。同样左、左、左，右、右、右的结果也不回出现，因为根据设计的称法，没有一个球是三次都在左边或右边的。剩下的24种结果就可以判断出哪种情况是哪一个球了。例如：如果结果是平、平、左或是平、平、右，就可判断出是9号球，因为第一次与第二次都没有9号球，唯独第三次有9号球，而第一次与第二次都是平的，只有第三次是失衡的，说明9号球的重量与其它的球不同。可依据此原理判断出其它的各种情况分别是哪个球。有12个球，而坏球又可能比好球轻也可能比好球重，所以总共有12x2=24种可能，24可能结果如下表：
************ ********** ************ **********
* 可能 * －* 结果 * * 可能 *－* 结果 *
************ ********** ************ **********
1号球，且重－左、右、右 1号球，且轻－右、左、左
2号球，且重－右、左、右 2号球，且轻－左、右、左
3号球，且重－右、右、左 3号球，且轻－左、左、右
4号球，且重－平、左、左 4号球，且轻－平、右、右
5号球，且重－左、平、左 5号球，且轻－右、平、右
6号球，且重－左、左、平 6号球，且轻－右、右、平
7号球，且重－右、平、平 7号球，且轻－左、平、平
8号球，且重－平、右、平 8号球，且轻－平、左、平
9号球，且重－平、平、右 9号球，且轻－平、平、左
10号球，且重－平、左、右 10号球，且轻－平、右、左
11号球，且重－右、平、左 11号球，且轻－左、右、平
12号球，且重－左、右、平 12号球，且轻－左、右、平上面的24种结果里面没有一个重复的，也可以把上面的结果反过来当成可能，也可唯一的推出那个球为坏球，证明此方法可行。
第2种答案
12个球和一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑)
参考答案1：
首先，把12个小球分成三等份，每份四只。
拿出其中两份放到天平两侧称（第一次）
情况一：天平是平衡的。
那么那八个拿上去称的小球都是正常的，特殊的在四个里面。
把剩下四个小球拿出三个放到一边，另一边放三个正常的小球（第二次）
如天平平衡，特殊的是剩下那个。
如果不平衡，在天平上面的那三个里。而且知道是重了还是轻了。
剩下三个中拿两个来称，因为已经知道重轻，所以就可以知道特殊的了。（第三次）
情况二：天平倾斜。
特殊的小球在天平的那八个里面。
把重的一侧四个球记为A1A2A3A4，轻的记为B1B2B3B4。
剩下的确定为四个正常的记为C。
把A1B2B3B4放到一边，B1和三个正常的C小球放一边。（第二次）
情况一：天平平衡了。
特殊小球在A2A3A4里面，而且知道特殊小球比较重。
把A2A3称一下，就知道三个里面哪个是特殊的了。（第三次）
情况二：天平依然是A1的那边比较重。
特殊的小球在A1和B1之间。
随便拿一个和正常的称，就知道哪个特殊了。（第三次）
情况三：天平反过来，B1那边比较重了。
特殊小球在B2B3B4中间，而且知道特殊小球比较轻。
把B2B3称一下，就知道哪个是特殊的了。（第三次）
参考答案2：
此称法称三次就保证找出那个坏球，并知道它比标准球重还是轻。
将十二个球编号为1-12。
第一次，先将1-4号放在左边，5-8号放在右边。
1.如果右重则坏球在1-8号。
第二次将2-4号拿掉，将6-8号从右边移到左边，把9-11号放
在右边。就是说，把1,6,7,8放在左边，5,9,10,11放在右边。
1.如果右重则坏球在没有被触动的1,5号。如果是1号，
则它比标准球轻；如果是5号，则它比标准球重。
第三次将1号放在左边，2号放在右边。
1.如果右重则1号是坏球且比标准球轻；
2.如果平衡则5号是坏球且比标准球重；
3.这次不可能左重。
2.如果平衡则坏球在被拿掉的2-4号，且比标准球轻。
第三次将2号放在左边，3号放在右边。
1.如果右重则2号是坏球且比标准球轻；
2.如果平衡则4号是坏球且比标准球轻；
3.如果左重则3号是坏球且比标准球轻。
3.如果左重则坏球在拿到左边的6-8号，且比标准球重。
第三次将6号放在左边，7号放在右边。
1.如果右重则7号是坏球且比标准球重；
2.如果平衡则8号是坏球且比标准球重；
3.如果左重则6号是坏球且比标准球重。
2.如果天平平衡，则坏球在9-12号。
第二次将1-3号放在左边，9-11号放在右边。
1.如果右重则坏球在9-11号且坏球较重。
第三次将9号放在左边，10号放在右边。
1.如果右重则10号是坏球且比标准球重；
2.如果平衡则11号是坏球且比标准球重；
3.如果左重则9号是坏球且比标准球重。
2.如果平衡则坏球为12号。
第三次将1号放在左边，12号放在右边。
1.如果右重则12号是坏球且比标准球重；
2.这次不可能平衡；
3.如果左重则12号是坏球且比标准球轻。
3.如果左重则坏球在9-11号且坏球较轻。
第三次将9号放在左边，10号放在右边。
1.如果右重则9号是坏球且比标准球轻；
2.如果平衡则11号是坏球且比标准球轻；
3.如果左重则10号是坏球且比标准球轻。
3.如果左重则坏球在1-8号。
第二次将2-4号拿掉，将6-8号从右边移到左边，把9-11号放
在右边。就是说，把1,6,7,8放在左边，5,9,10,11放在右边。
1.如果右重则坏球在拿到左边的6-8号，且比标准球轻。
第三次将6号放在左边，7号放在右边。
1.如果右重则6号是坏球且比标准球轻；
2.如果平衡则8号是坏球且比标准球轻；
3.如果左重则7号是坏球且比标准球轻。
2.如果平衡则坏球在被拿掉的2-4号，且比标准球重。
第三次将2号放在左边，3号放在右边。
1.如果右重则3号是坏球且比标准球重；
2.如果平衡则4号是坏球且比标准球重；
3.如果左重则2号是坏球且比标准球重。
3.如果左重则坏球在没有被触动的1,5号。如果是1号，
则它比标准球重；如果是5号，则它比标准球轻。
第三次将1号放在左边，2号放在右边。
1.这次不可能右重。
2.如果平衡则5号是坏球且比标准球轻；
3.如果左重则1号是坏球且比标准球重；
参考答案3：
|--右--( 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重)

我又想到了用2分，分成2堆，不一定要完全相等的两堆，至少要一堆与n/2差不多的偶数，这样能保证之后检查的次数更少。假设是n/2，那么继续把n/2分成2个n/4，比较两个n/4的重量，相同，那么就在剩下没有比较的两堆里面，不同，那么就在这两堆里面。那么至少保证了每次能够排除一半。上面三分的最理想状况，也就是刚好是3^n次的话，就可以n+1次，如果不是的话，就要n+2次。而2分，2^n需要n次，如果不是需要n+1次。
12个球，不知道轻重的话，我想不出怎么用3次找出来。三分法终究要变成3个球的问题，3个球有可能1次，有可能2次。

能称出次品的次数为
最少4次：
     第一次：首先称出n个球的总总量假设为m。
     第二次：随机在选择一个称出重量假设为x，令m%x得到的数值为R
     第三次：再选出一个没有称过的球称出重量为y，令m%y得到的数值为P
     第四次：再选出一个没用称过的求  称出重量为z，令m%z得到的数值为Q
     如果有一个球是次品，即与其他球重量不一致，那么总的总重量%它之后的那个数值一定和总重量来%他    的求之后得到的数值不一样。这样即可找到那个次品。

这里有个算法http://wenku.baidu.com/view/0bf7e8543c1ec5da51e27005.html

最少如果是奇数，运气好的话，就一次就可以了！如果是偶数的话那就 n = 2 的 z次幂那就是需要称z次就可以了

不知道轻重的话，如果球足够多，也就是秤的次数足够多，那么每次排除的球为1/2，三分法有可能排除掉1/3，也有可能2/3，总的来说还是1/2，也就是2n个球要秤n+1次，2n+1个球要秤n+1次。n个球要秤n/2+1。想不出更好的解决方法了

static class Group {
      public static String BIG = "BIG";
      public static String SMALL = "SMALL";
      public static String EQUAL = "EQUAL";
      private String compareResult;
      private List<Ball> ballList;      public Group() {
         ballList = new ArrayList<Ball>();
      }      public Group(List<Ball> list) {
         ballList = list;
      }      public void addBall(Ball ball) {
         ballList.add(ball);
      }      public void allAllBall(List<Ball> list) {
         ballList.addAll(list);
      }      public int size() {
         return ballList.size();
      }      public int getGroupWeight() {
         return getSumWeight(ballList);
      }      /**
       * @return the ballList
       */
      public List<Ball> getBallList() {
         return ballList;
      }      /**
       * @param ballList the ballList to set
       */
      public void setBallList(List<Ball> ballList) {
         this.ballList = ballList;
      }      /**
       * @return the compareResult
       */
      public String getCompareResult() {
         return compareResult;
      }      /**
       * @param compareResult the compareResult to set
       */
      public void setCompareResult(String compareResult) {
         this.compareResult = compareResult;
      }      public String toString() {
         return java.util.Arrays.toString(ballList.toArray());
      }
   }

static class Ball {
      private String index;
      private int weight;      public Ball(String index, int weight) {
         this.index = index;
         this.weight = weight;
      }      /**
       * @return the index
       */
      public String getIndex() {
         return index;
      }      /**
       * @param index the index to set
       */
      public void setIndex(String index) {
         this.index = index;
      }      /**
       * @return the weight
       */
      public int getWeight() {
         return weight;
      }      /**
       * @param weight the weight to set
       */
      public void setWeight(int weight) {
         this.weight = weight;
      }      public String toString() {
         return index + "_" + weight;
      }
   }

public class FindBall {
   private static int compareCount = 0;
   private static int getSumWeight(List<Ball> group) {
      int sum = 0;
      for(int i = 0; i < group.size(); i++) {
         sum += group.get(i).getWeight();
      }
      return sum;
   }
   private Group[] getGruops(List<Ball> list, int split) {
      Group[] groups = new Group[split];
      for(int i = 0; i < list.size(); i++) {
         if(groups[i % split] == null) {
            groups[i % split] = new Group();
         }
         groups[i % split].addBall(list.get(i));
      }
      return groups;
   }
   private int compare(Group group1, Group group2) {
      compareCount++;
      return group1.getGroupWeight() - group2.getGroupWeight();
   }
   private Group find(Group group) {
      int num = group.getBallList().size();
      int r = num % 3;
      System.err.println(group.getCompareResult() + ", " + group.getBallList());
      if(num == 1) {
         System.err.println(group.getCompareResult() + ", " + group.getBallList().get(0));
         return group;
      }
      if(r == 0) {
         Group[] groups = getGruops(group.getBallList(), 3);
         int compareResult = compare(groups[0], groups[1]);
         if(compareResult == 0) {
            return find(groups[2]);
         }
         else if(compareResult > 0) {
            groups[0].setCompareResult(Group.BIG);
            groups[1].setCompareResult(Group.SMALL);
            compareResult = compare(groups[0], groups[2]);
            if(compareResult == 0) {
               groups[2].setCompareResult(Group.BIG);
               return find(groups[1]);
            }
            else if (compareResult > 0) {
               groups[2].setCompareResult(Group.SMALL);
               return find(groups[0]);
            }
         }
         else if(compareResult < 0) {
            groups[0].setCompareResult(Group.SMALL);
            groups[1].setCompareResult(Group.BIG);
            compareResult = compare(groups[1], groups[2]);
            if(compareResult == 0) {
               groups[2].setCompareResult(Group.BIG);
               return find(groups[0]);
            }
            else if (compareResult > 0) {
               groups[2].setCompareResult(Group.SMALL);
               return find(groups[2]);
            }
         }
      }
      else if(r == 1) {
         Ball first = group.getBallList().remove(0);
         Group g = new Group();
         g.addBall(first);
         Group[] groups = getGruops(group.getBallList(), 3);
         int compareResult = compare(groups[0], groups[1]);
         if(compareResult == 0) {
            if(groups[2].size() == 1) {
               int f = compare(g, groups[1]);
               int s = compare(g, groups[2]);               if(f > 0 && s > 0 || f < 0 && s < 0) {
                  return g;
               }
               else {
                  return groups[2];
               }
            }            return find(groups[2]);
         }
         else if(compareResult > 0) {
            groups[0].setCompareResult(Group.BIG);
            groups[1].setCompareResult(Group.SMALL);
            compareResult = compare(groups[0], groups[2]);            if(compareResult == 0) {
               groups[2].setCompareResult(Group.BIG);
               return find(groups[1]);
            }
            else if (compareResult > 0) {
               groups[2].setCompareResult(Group.SMALL);
               return find(groups[0]);
            }
         }
         else if(compareResult < 0) {
            groups[0].setCompareResult(Group.SMALL);
            groups[1].setCompareResult(Group.BIG);
            compareResult = compare(groups[1], groups[2]);            if(compareResult == 0) {
               groups[2].setCompareResult(Group.BIG);
               return find(groups[0]);
            }
            else if (compareResult > 0) {
               groups[2].setCompareResult(Group.SMALL);
               return find(groups[2]);
            }
         }
      }
      else if(r == 2) {
      }
      return null;
   }

   public void findBall(int num) {
      List<Ball> list = new ArrayList<Ball>();
      for(int i = 0; i < num; i++) {
         if(i == 0) {
            list.add(new Ball(i + "", 1));
         }
         else {
            list.add(new Ball(i + "", 2));
         }
      }      java.util.Collections.shuffle(list);
      Group all = new Group(list);
      find(all);
   }   public static void main(String[] args) {
      new FindBall().findBall(12);
   }
没写完

看来是没人解了，上代码：
package balance;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class WeightBall {
static int round = 1;
static int maxSteps;
public static void run(Status root, List<Status> list) { //求解
long time = System.currentTimeMillis();
List<Status> newlist = new ArrayList<Status>();
for (int i=0; i<list.size(); i++) {
Status status = list.get(i);
status.produceBalances();
for (int j=0; j<status.bls.size(); j++) {
Balance bl = status.bls.get(j);
bl.weight();
if (root.succeed()) {
System.out.println("第" + round + "轮: 计算至上轮第" + (i+1) + "个节点得解，之前获得节点" + newlist.size() + "个，用时" + (double)(System.currentTimeMillis()-time)/1000 + "秒"); return;
}
if (bl.out1.isUnknown()) newlist.add(bl.out1);
if (bl.out2.isUnknown()) newlist.add(bl.out2);
if (bl.out3.isUnknown()) newlist.add(bl.out3);
}
}
System.out.println("第" + round + "轮: 获得节点" + newlist.size() + "个，用时" + (double)(System.currentTimeMillis()-time)/1000 + "秒");
round++;
run(root, newlist);
}
public static void print(Status st, int depth) { //输出结果
String indent="";
for (int i=0; i<depth-1; i++) indent = indent+"\t";
Balance bl=null;
for (int i=0; i<st.bls.size(); i++)
if (st.bls.get(i).unresolved==0) bl=st.bls.get(i);
if (bl!=null) {
if (depth>maxSteps) maxSteps=depth;
System.out.println(indent + "第" + depth + "步称重: " + bl + "\r\n");
System.out.println(indent + "如果一样重: " + bl.out1 + (bl.out1.getConclusion()==Status.RESOLVED?"  *解决*":(bl.out1.getConclusion()==Status.REDICULOUS?"  ×不可能×":"")) + "\r\n");
print(bl.out1, depth+1);
System.out.println(indent + "如果左边重: " + bl.out2 + (bl.out2.getConclusion()==Status.RESOLVED?"  *解决*":(bl.out2.getConclusion()==Status.REDICULOUS?"  ×不可能×":"")) + "\r\n");
print(bl.out2, depth+1);
System.out.println(indent + "如果右边重: " + bl.out3 + (bl.out3.getConclusion()==Status.RESOLVED?"  *解决*":(bl.out3.getConclusion()==Status.REDICULOUS?"  ×不可能×":"")) + "\r\n");
print(bl.out3, depth+1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入小球个数（大于2，超过14请调整JVM内存）：");
int n = sc.nextInt();
Status root = new Status(n);
ArrayList<Status> list = new ArrayList<Status>();
list.add(root);
System.out.println("***** 开始求解......");
run(root, list);
System.out.println("\r\n***** 步骤说明：");
maxSteps = 0;
print(root, 1);
System.out.println("\r\n***** 总计" + maxSteps + "步可解！");
}
}package balance;import java.util.ArrayList;
import java.util.List;public class Status {
public static int RESOLVED=1, UNKNOWN=2, REDICULOUS=3, RESOLVABLE=4;
public int count=0;
public int[] data;
public List<Balance> parents = new ArrayList<Balance>();
public List<Balance> bls = new ArrayList<Balance>();
private int conclusion;

public Status(int c) {
count = c;
int[] data1 = {0,c,0,0};
data = data1;
int conc = data[0]<count-1?UNKNOWN:(data[0]==count-1?RESOLVED:REDICULOUS);
setConclusion(conc);
}
public Status(int[] is) {
data = is;
for (int i=0; i<is.length; i++) count+=is[i];
int conc = data[0]<count-1?UNKNOWN:(data[0]==count-1?RESOLVED:REDICULOUS);
setConclusion(conc);
}
public void addParent(Balance bl) {
parents.add(bl);
if (conclusion==RESOLVED || conclusion==RESOLVABLE || conclusion==REDICULOUS) bl.prop();
}
public String toString() {
return "正常" + data[0] + "、不明" + data[1] + "、或重" + data[2] + "、或轻" + data[3];
}
public void setConclusion(int conc) {
if (conclusion == conc) return;
conclusion = conc;
if (conclusion==RESOLVED || conclusion==RESOLVABLE || conclusion==REDICULOUS)
for (int i=0; i<parents.size(); i++)
parents.get(i).prop();
}
public int getConclusion() {return conclusion;}
public boolean succeed() {return conclusion==RESOLVED || conclusion==RESOLVABLE;}
public boolean isUnknown(){return conclusion==UNKNOWN;}

public void produceBalances() {//得到当前状况下所有可能的称重方案
List<int[]> bldata = getBalanceDataArray(data);
bls = new ArrayList<Balance>();
for (int i=0; i<bldata.size(); i++) {
Balance bl = new Balance(bldata.get(i));
bl.in = this;
bls.add(bl);
}
}
private List<int[]> getBalanceDataArray(int[] src) {
List<int[]> list = new ArrayList<int[]>();
list.add(new int[src.length*2]);
return getBalanceDataArray(src,0,list);
}
private List<int[]> getBalanceDataArray(int[] src, int id, List<int[]> list) {
int total=0,left,right;
if (id>=src.length) {
for (int i=list.size()-1; i>=0; i--) {
int[] is = list.get(i);
left=0;
right=0;
for (int j=0; j<src.length; j++) left+=is[j];
for (int j=src.length; j<src.length*2; j++) right+=is[j];
if (left!=right || left==0 || is[0]>0&&is[is.length/2]>0)
list.remove(i);
}
return list;
}
List<int[]> r = new ArrayList<int[]>();
for (int i=0; i<src.length; i++) total += src[i];
int half = total/2;
for (int i=0; i<list.size(); i++) {
int[] is = list.get(i);
left=0;
right=0;
for (int j=0; j<src.length; j++) left+=is[j];
for (int j=src.length; j<src.length*2; j++) right+=is[j];
for (int j=0; j<=Math.min(half-left, src[id]); j++) {
for (int k=0; k<=Math.min(half-right, src[id]-j); k++) {
int[] iis = list.get(i).clone();
iis[id] = j;
iis[id+src.length] = k;
r.add(iis);
}
}
}
return getBalanceDataArray(src,id+1,r);
}
}package balance;public class Balance {
public int[] data;
public Status in,out1,out2,out3;
public int unresolved = 3;

public Balance(int[] data) {
this.data = data.clone();
}
public void weight() {//称重量，推理出三种可能的结果
int[] temp;
// 一样重
temp = in.data.clone();
for (int i=1; i<4; i++) { //所有参与称重的球都移入正常球集合
temp[0] = temp[0] + data[i] + data[i+4];
temp[i] = temp[i] - data[i] - data[i+4];
}
out1 = new Status(temp);
out1.addParent(this);

//左边重
temp = in.data.clone();
for (int i=1; i<4; i++) {
temp[0] = temp[0] + temp[i] - data[i] - data[i+4]; //未参与称重的球  -->> 正常球
}
temp[0] += data[3] + data[6]; //左边的疑似轻球、右边的疑似重球  -->> 正常球
temp[1] = 0;
temp[2] = data[1] + data[2]; //左边的不明轻重球移入疑似重球集合
temp[3] = data[5] + data[7]; //右边的不明轻重球移入疑似轻球集合
out2 = new Status(temp);
out2.addParent(this);

//右边重
temp = in.data.clone();
for (int i=1; i<4; i++) {
temp[0] = temp[0] + temp[i] - data[i] - data[i+4]; //未参与称重的球  -->> 正常球
}
temp[0] += data[2] + data[7]; //左边的疑似重球、右边的疑似轻球  -->> 正常球
temp[1] = 0;
temp[2] = data[5] + data[6]; //右边的不明轻重球移入疑似重球集合
temp[3] = data[1] + data[3]; //左边的不明轻重球移入疑似轻球集合
out3 = new Status(temp);
out3.addParent(this);
}
public String toString(){
return "（" + (data[0]>0?"正常球×"+data[0]+"个 ":"") + (data[1]>0?"不明球×"+data[1]+"个 ":"")
+(data[2]>0?"疑似重球×"+data[2]+"个 ":"") + (data[3]>0?"疑似轻球×"+data[3]+"个 ":"")
+ "） --天平-- （"
+ (data[4]>0?"正常球×"+data[4]+"个 ":"") + (data[5]>0?"不明球×"+data[5]+"个 ":"")
+(data[6]>0?"疑似重球×"+data[6]+"个 ":"") + (data[7]>0?"疑似轻球×"+data[7]+"个 ":"") + "）";
}
public void prop() {
if (unresolved <= 0) return;
unresolved--;
if (unresolved == 0) in.setConclusion(Status.RESOLVABLE);
}
}

先平均分为两组A，B。在将A,B 平均分成两份A1，A2;B1,B2。将A组的两份球放天平上称量假设不平就说明次品在A组，而B组都是好的，这时将B1拿出分别和A1，A2比较重量，一定是有一个不和B1重量相等，另一个和B1相等（假设A1和B1不等），注意A1和B1的重量以B1为标准判断A1中存在的劣质球是轻的还是重的。判断完后再用二分法来找出A1中的劣质球。
（以上是假设球的总量是四的倍数，并且A1是二的倍数，要是和假设不同则减少或增加球的数量削平或补齐。）

public class Ball {

public int[] balls;

public Ball(int N) {
balls = new int[N];
for (int i = 0; i < N; i++) {
balls[i] = 100;
}
// 随机生成非标准球
balls[Integer.parseInt(Math.round(N * Math.random() * 10) + "") / 10] = 999;
for (int i = 0; i < N; i++) {
System.out.print(balls[i] + ",");
}
System.out.println();
}
}public class MainTest {

public static void main(String[] args) {
MainTest test = new MainTest();
Ball ball = new Ball(50);
System.out.println("非标准球:" + test.findBall(ball.balls) + "  次数:" + times);
}

// 记录标准重
private int standardWight = -1;
// 遍历次数，每使用天平一次加１
private static int times = 0;

// 递归查找
private int findBall(int[] balls) {

// 只剩最后一个球则一定是非标准球
if (balls.length == 1) return standardWight;
times++;
// 如果是两个球
if (balls.length == 2) {
if (balls[0] == balls[1]) {
return 0;
}
return standardWight == balls[0] ? balls[1] : balls[0];
} // 折半找中间轴
int middle = balls.length / 2 + balls.length % 2;
if (middle % 2 == 1) middle += 1;
int endPos = middle / 2;
// 判断左半部分是否有非标准球
if (sumWeight(balls, 0, endPos - 1) == sumWeight(balls, endPos, endPos * 2 - 1)) {
standardWight = balls[0];
// if (middle % 2 == 1) {
// times++;
// if (balls[middle - 1] != balls[0]) return balls[middle - 1];
// }
return findBall(getFocusBall(balls, middle, balls.length));
// 判断是否只有３个球，且有非标准球的情况
} else if (middle == 3) {
times++;
return balls[1] == balls[2] ? balls[0] : balls[1];
} else {
// 判断右半部分是否有非标准球
standardWight = balls[middle];
return findBall(getFocusBall(balls, 0, middle));
}

}

private static int sumWeight(int[] balls, int startPos, int endPos) {
int total = 0;
for (int i = startPos; i <= endPos; i++) {
total += balls[i];
}
return total;
}

/**
* 生成新的目标球
* @param balls
* @param startPos
* @param endPos
* @return
*/
private int[] getFocusBall(int[] balls, int startPos, int endPos) {
int[] focusBall = new int[endPos - startPos];
System.out.println("生成新的目标球  起始下标:" + startPos + " 终止坐标:" + (endPos - 1));
for (int i = 0; i < focusBall.length; i++) {
focusBall[i] = balls[i + startPos];
System.out.print(focusBall[i] + ",");
}
System.out.println();
return focusBall;
}
}
随机输出结果：
100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,999,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,
生成新的目标球  起始下标:26 终止坐标:49
100,100,999,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,
生成新的目标球  起始下标:0 终止坐标:11
100,100,999,100,100,100,100,100,100,100,100,100,
生成新的目标球  起始下标:0 终止坐标:5
100,100,999,100,100,100,
生成新的目标球  起始下标:0 终止坐标:3
100,100,999,100,
生成新的目标球  起始下标:2 终止坐标:3
999,100,
非标准球:999  次数:6

// 只剩最后一个球则一定是非标准球
if (balls.length == 1) return standardWight;
上面代码应该是:
if (balls.length == 1) return balls[0];大意了

调试易

天平称球问题

解决方案 »