把13个球分成6个,6个,1个,把天平左右各放入6个,如果相等,则多于的1个是不同的.如果不相等,则把重的那边的6个分成3:3再称,再把重的那过的3个球分成1:1还剩1个,这样结果就出来了,一个三次比较.用递归就行,源吗如下 public class test{ public static int[] ball = new int[13]; public static int aver = 0; public static void main(String args[]){
for(int j = 0; j < ball.length; j++){ ball[j] = 1; if(j == 7) //假设有一个是2,其它全是1 ball[j] = 2; } aver = ball.length/2; result(aver); } public static void result(int num){ int a = 0; int b = 0; for(int i = 0; i < num ; i++){ a = a + ball[i]; b = b + ball[i+num]; } if(a == b){ System.out.println("MAX is :" + ball[num*2+1]); } else{ result(num/2); } } }
关注ing!!!!
* 13球称重问题Java实现
* <p>Title: </p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2004</p>
* <p>Company: </p>
* @author treerot
* @version 1.0
*/
public class ThirteenBall {
private static class Ball {
private int weight;
public int getWeight() {
return weight;
} public void setWeight(int weight) {
this.weight = weight;
} Ball(int weight) {
this.weight = weight;
}
} public static void main(String[] args) throws InterruptedException {
Ball[] balls = new Ball[13];
/*
for (int i = 0; i < 13; i++) {
for (int j = 0; j < 13; j++) {
balls[j] = new Ball(10);
}
//设置一个轻球
balls[i].setWeight(8);
System.out.println(findBall(balls));
//设置一个重球
balls[i].setWeight(12);
System.out.println(findBall(balls));
}
*/
} static int compare(Ball[] b,int[] b1, int[] b2) {
int left = 0, right = 0;
for (int i = 0; i < b1.length; i++) {
left += b[b1[i]].getWeight();
right += b[b2[i]].getWeight();
}
return left - right;
} static void print(int flag) {
String s = (flag == 0) ? "无法判断轻重!" :
(flag < 0) ? "目标球比其他轻" : "目标球比其他重";
System.out.println(s);
} static int findBall(Ball[] b) {
//天平每边放四个球:b[0],b[1],b[2],b[3] VS b[4],b[5],b[6],b[7]
//目标球
int result = 0; int cmp1 = 0, cmp2 = 0, cmp3 = 0;
cmp1 = compare(b,new int[]{0,1,2,3},new int[]{4,5,6,7}); if (cmp1 == 0) {
//目标球在后面5个中:前面八个球正常,比较 8,9 VS 10,0(也可以是其他0..7)
cmp2 = compare(b,new int[]{8,9},new int[] {10,0});
if (cmp2 == 0) {
//目标球在11,12中:比较 11 VS 0
cmp3 = compare(b,new int[] {11}, new int[] {0});
if (cmp3 == 0) {
//目标球是12
result = 12;
print(0); //这里无法判断轻重
}
else {
//目标球就是11
result = 11;
print(cmp3);
}
}
else if (cmp2 < 0) {
//8,9轻或者10重,比较 8 VS 9
cmp3=compare(b,new int[]{8},new int[]{9});
if(cmp3==0){
//10重
result=10;
print(1);
}
else if(cmp3<0){
//8轻
result=8;
print(-1);
}
else{
//9轻
result=9;
print(-1);
}
}
else{
//8,9重或者10轻
cmp3=compare(b,new int[]{8},new int[]{9});
if(cmp3==0){
//10轻
result=10;
print(-1);
}
else if(cmp3<0){
//9重
result=9;
print(1);
}
else{
//8重
result=8;
print(1);
} }
}
else if (cmp1 < 0) {
//0,1,2,3轻或者4,5,6,7重 比较:0,1,4 VS 2,3,5
cmp2=compare(b,new int[]{0,1,4},new int[]{2,3,5});
if(cmp2==0){
//6,7重,比较 6 VS 0
cmp3=compare(b,new int[]{6},new int[]{0}); //cmp3不会小于0
if(cmp3==0){
//7重
result=7;
print(1);
}
else{
//6重
result=6;
print(1);
}
}
else if(cmp2<0){
//0,1轻或者5重 比较 0 VS 1
cmp3=compare(b,new int[]{0},new int[]{1});
if(cmp3==0){
//5重
result=5;
print(1);
}
else if(cmp3<0){
//0轻
result=0;
print(-1);
}
else{
//1轻
result=1;
print(-1);
}
}
else{
//2,3轻或者4重 比较 2 VS 3
cmp3=compare(b,new int[]{2},new int[]{3});
if(cmp3==0){
//4重
result=4;
print(1);
}
else if(cmp3<0){
//2轻
result=2;
print(-1);
}
else{
//3轻
result=3;
print(-1);
}
}
}
else {
//和上面对称 0,1,2,3重或者4,5,6,7轻 比较:0,1,4 VS 2,3,5
//实现不愿在写了,这里用递归的话就不止比较三次了
Ball[] b2=new Ball[13];
System.arraycopy(b,4,b2,0,4);
System.arraycopy(b,0,b2,4,4);
result=findBall(b2)-1;
if(result>=4) result-=4;
else result+=4;
} return result+1;
}}
小球分三组：4 4 5。
第一次：天平两边各放四个。
结果：a：两边相等。
b：一边重，一边轻。
结论：a：这八个球都无问题。有问题的在剩下的5个中。
b：剩下的5个球没问题。有问题的在这八个中。
第二次：a种情况：
将剩下的5个球中的3个与无问题的3个放在天平两边。
结果：a1：两边相等。
b1：一边重，一边轻。
结论：a1：5个球中又排除了3个，只剩下没称到的2个。
b1：剩下的2个没问题。有问题的特殊球在比标准球重或轻的一边。
第三次：a种情况：
a1种情况：
将剩下的2个有问题的当中的1个与1个无问题的标准球放在天平上比较。
结果：a2： 两边相等。
b2：一边重，一边轻。
结论：a2：剩下的那个既是特殊球。
b2：剩下的那个球无问题。比标准球重或轻的球既是特殊球。
第二次：b种情况：
将重的一边拿下3个，将轻的一边拿过3个放在重的一边，将无问题的
标准球拿3个放在原来轻的一边。
结果：x：两边相等。
y：重的一边还是重。
z：重的一边变轻。
结论：x：这些球都无问题。有问题的在拿下去的3个当中，而且当中
有一个是重的。
y：拿下去的3个无问题。原来轻的一边拿过去的3个也无问题。
有问题的可能是原来重的这个重或原来轻的那个轻。
z：拿下去的3个无问题。原来重的和原来轻的一边的这两个也
无问题。有问题的在原来轻现拿到重的一边的这3个当中。
有1个轻的特殊球。
第三次：b种情况：
x种情况：拿下去的3个球当中的两个在天平的两边各放一个。
结果：x1：两边相等。
x2：一边重，一边轻。
结论：x1：这两个球无问题。剩下的那个球是特殊球。他比其它球重。
x2：重的一边的球是特殊球。
y：种情况：用一个标准球与原来重的一边的那棵球比较。
结果：y1：两边相等。
y2：重的那棵球还重。
结论：y1：重的一边的那个球无问题。特殊球是原来轻的一边的那颗球。
y2：原来轻的一边的那颗球无问题。特殊球是原来重的一边的那
棵球。
z种情况：将原来轻的一边的3个球当中的两个在天平两边各放一个。
结果：z1：两边相等。
z2：一边重，一边轻。
结论：z1：这两个球无问题。剩下的那个球是特殊球。他比其它球轻。
z2：剩下的那个球无问题。特殊球是轻的一边的那颗。
public class test{
public static int[] ball = new int[13];
public static int aver = 0;
public static void main(String args[]){
for(int j = 0; j < ball.length; j++){
ball[j] = 1;
if(j == 7) //假设有一个是2,其它全是1
ball[j] = 2;
}
aver = ball.length/2;
result(aver);
}
public static void result(int num){
int a = 0;
int b = 0;
for(int i = 0; i < num ; i++){
a = a + ball[i];
b = b + ball[i+num];
}
if(a == b){
System.out.println("MAX is :" + ball[num*2+1]);
}
else{
result(num/2);
}
}
}