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;
  }

}

本文地址：http://com.8s8s.com/it/it13979.htm