原题是在13个乒乓球中有1个次品,外表和正品一样,但重量不同,不知道是轻是重,试给出一个算法,用不带砝码的天平以尽可能少的次数将次品挑出来.


我查了些文章大约知道怎么挑,但是用程序代码模拟不出来.以下是我用二分查找法求解的.

/**
* 从13个乒乓球中挑次品
*/
import java.io.*;
public class PickBalls{ 
  public static void main(String[] args){
    System.out.println("*********挑选乒乓球次品*********");
    System.out.println("*            Emote             *");
    System.out.println("********************************");
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    int count=0;
    try{
      System.out.println("请输入球数:");
      count=Integer.valueOf(in.readLine()).intValue();
    }catch(Exception e){
        System.out.println("输入有误退出.");System.exit(0);
    }
    if(count<1) {System.out.println("输入有误退出.");System.exit(0);}
    int[] balls=new int[count+1];
    //for(int i=0;i<count;i++) balls[i]=1;
    int rand=(int)(Math.random()*count+0.5);//使次品球可能为最后一个.
    balls[(rand==0)?rand=1:rand]=1;
   // balls[count]=1;
    System.out.println("将球排好并编号,随机使"+rand+"号球为次品球(1仅代表次品不做挑选依据).");
    for(int i=1;i<=count;i++) System.out.print(i+"  ");
    System.out.println();
    for(int i=1;i<=count;i++) {String s="";if(i>=9) s=" "; System.out.print(balls[i]+"  "+s);}
    System.out.println();
    //2分查找法
    System.out.println("使用二分查找法挑选次品.");
 
    int low=1,high=count,middle=0;
    while(low<high){
         middle=(int)(low+high)/2;
         System.out.println(low+","+middle+" -> "+middle+","+high);
         if(low==middle) {System.out.println("查找结束.次品球号为:"+low);break;}
         if(PickBalls(balls,low,middle,high)>0) 
           {System.out.println("两边球重量不一样.将左边按序号分两组再测试.");
               int r=PickBalls(balls,low,(int)(low+middle)/2,middle);
               if(r>0) {high=middle;System.out.println("左边分两组测试重量不相等,次品在左边"+low+","+middle);}//左边再分两次测仍然不一样，则说明次品在左部分左半边
          //如果左部分分两边测试结果一样，那么结果就在右部分
          else {low=middle;System.out.println("左边分两组测试重量相等,次品在右边"+middle+","+high);}
         }
         //球数为奇数，并且最后一个球为次品
         else{ System.out.println("前面"+(count-1)+"个球重量相等,最后一个球"+count+"为次品");break;}     
    //    t++;if(t>10) break;
    }
  }
  //两部分相等返回0，否则返回1
  public static int PickBalls(int[] balls,int from,int mid,int to){
      int t1=0,t2=0;
      for(;from<mid;from++) t1+=balls[from];
      for(;mid<to;mid++) t2+=balls[mid];
      if(t1==t2) return 0;
    else return 1; 
  }
}

我数据结构学的不是很好,还请大家给一个好的解法,谢谢