13球称重问题Java实现
/**
* 13球称重问题Java实现
* <p>Copyright: Copyright (c) 2004</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;
}
}