欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Given n coins and a pan balance,find the only counterfeit 3 博客分类: algorithms  

程序员文章站 2024-03-07 12:17:45
...
In the 1-ball case, if the status flag is already set, then we don't need to weight anymore. Otherwise, we need to find a good ball to compare.
java 代码
 
  1. package solve;  
  2.   
  3. import scale.Ball;  
  4. import scale.Scale;  
  5.   
  6. import java.util.Set;  
  7.   
  8. /** 
  9.  * 1-ball case: we need a good reference ball and at most one trial 
  10.  */  
  11. public class OneBallCaseSolver  
  12. {  
  13.     private Scale scale;  
  14.     private Set originalBallSet;  
  15.   
  16.     public void findWeight(Set ballSet)  
  17.     {  
  18.         if (ballSet.size() != 1)  
  19.             throw new IllegalArgumentException("scale.Ball set size is not 1: size=" + ballSet.size());  
  20.   
  21.         Ball ball = (Ball)ballSet.iterator().next();  
  22.   
  23.         if (!ball.getStatus().equals(Ball.UNKNOWN)) return;  
  24.   
  25.         // in order to figure it's good or bad, we need a good reference ball.  
  26.         Ball goodBall = Utils.findGoodBall(originalBallSet);  
  27.         if (goodBall == null)  
  28.         {  
  29.             throw new RuntimeException("can't findBallBall a good reference ball to use for the judgement");  
  30.         }  
  31.   
  32.         // flag conversion  
  33.         int result = scale.weigh(ball, goodBall);  
  34.         ball.setStatus(Utils.convertToBallStatus(result));  
  35.     }  
  36.   
  37.     public void setScale(Scale scale) { this.scale = scale; }  
  38.     public void setOriginalBallSet(Set originalBallSet) { this.originalBallSet = originalBallSet; }  
  39. }  

In the 2-ball case, we need to check whether the status flags for both are set. If not, then we need two weighings.

java 代码
 
  1. package solve;  
  2.   
  3. import scale.Scale;  
  4. import scale.Ball;  
  5.   
  6. import java.util.Iterator;  
  7. import java.util.Set;  
  8.   
  9. /** 
  10.  * 2-ball case: we need a good reference ball and one or two weighings. 
  11.  */  
  12. public class TwoBallCaseSolver  
  13. {  
  14.     private Scale scale;  
  15.     private Set originalBallSet;  
  16.   
  17.     public void findWeight(Set ballSet)  
  18.     {  
  19.         if (ballSet.size() != 2)  
  20.             throw new IllegalArgumentException("scale.Ball set size is not 2: size=" + ballSet.size());  
  21.   
  22.         Iterator it = ballSet.iterator();  
  23.         Ball balla = (Ball)it.next();  
  24.         Ball ballb = (Ball)it.next();  
  25.   
  26.         Ball goodBall = Utils.findGoodBall(originalBallSet);  
  27.         int result = scale.weigh(balla, goodBall);  
  28.         balla.setStatus(Utils.convertToBallStatus(result));  
  29.   
  30.         if (!balla.getStatus().equals(Ball.NORMAL))  
  31.         {  
  32.             ballb.setStatus(Ball.NORMAL);  
  33.         }  
  34.         else if (ballb.getStatus().equals(Ball.UNKNOWN))  
  35.         {  
  36.             result = scale.weigh(ballb, goodBall);  
  37.             ballb.setStatus(Utils.convertToBallStatus(result));  
  38.         }  
  39.     }  
  40.   
  41.     public void setScale(Scale scale) { this.scale = scale; }  
  42.     public void setOriginalBallSet(Set originalBallSet) { this.originalBallSet = originalBallSet; }  
  43. }  

In the above two cases, whenever we need to weigh, we need a good ball as the reference. In the 3-ball case, we don't need a good ball.

java 代码
 
  1. package solve;  
  2.   
  3. import scale.Scale;  
  4. import scale.Ball;  
  5.   
  6. import java.util.Set;  
  7. import java.util.Iterator;  
  8.   
  9. /** 
  10.  * 3-ball case: we need two trials if all of the balls are not marked, otherwise 
  11.  * we need only one trial. 
  12.  */  
  13. public class ThreeBallCaseSolver  
  14. {  
  15.     private Scale scale;  
  16.   
  17.     public void findWeight(Set ballSet)  
  18.     {  
  19.         if (ballSet.size() != 3)  
  20.             throw new IllegalArgumentException("scale.Ball set size is not 3: size=" + ballSet.size());  
  21.   
  22.         // In the 3-ball case, we can figure out which one is good.  
  23.         // Here, we assume there is only one bad ball.  
  24.         Iterator it = ballSet.iterator();  
  25.         Ball balla = (Ball)it.next();  
  26.         Ball ballb = (Ball)it.next();  
  27.         Ball ballc = (Ball)it.next();  
  28.   
  29.         if (balla.getStatus().equals(Ball.UNKNOWN)) // This means we start with 3 balls  
  30.         {  
  31.             // In this case we need two trials  
  32.             int result = scale.weigh(balla, ballb);  
  33.             if (result == Scale.EVEN)  
  34.             {  
  35.                 // This means balla and ballb are good, ballc is bad.  
  36.                 balla.setStatus(Ball.NORMAL);  
  37.                 ballb.setStatus(Ball.NORMAL);  
  38.                 if (scale.weigh(balla, ballc) == Scale.HEAVIER)  
  39.                     ballc.setStatus(Ball.LIGHTER);  
  40.                 else  
  41.                     ballc.setStatus(Ball.HEAVIER);  
  42.             }  
  43.             else //if (result == Scale.HEAVIER)  
  44.             {  
  45.                 // This means ballc is good  
  46.                 ballc.setStatus(Ball.NORMAL);  
  47.                 int result1 = scale.weigh(balla, ballc);  
  48.                 if (result1 == Scale.EVEN) // a is also good  
  49.                 {  
  50.                     balla.setStatus(Ball.NORMAL);  
  51.                     if (result == Scale.HEAVIER)  
  52.                         ballb.setStatus(Ball.LIGHTER);  
  53.                     else  
  54.                         ballb.setStatus(Ball.HEAVIER);  
  55.                 }  
  56.                 else if (result1 == Scale.HEAVIER) // b is good, a is heavier  
  57.                 {  
  58.                     balla.setStatus(Ball.HEAVIER);  
  59.                     ballb.setStatus(Ball.NORMAL);  
  60.                 }  
  61.                 else  
  62.                 {  
  63.                     balla.setStatus(Ball.LIGHTER);  
  64.                     ballb.setStatus(Ball.NORMAL);  
  65.                 }  
  66.             }  
  67.         }  
  68.         else // This means we start with more than 3 balls and markWeight is marked.  
  69.         {  
  70.             // In this case we need only 1 trial with the marked info.  
  71.             // At this stage, all 3 balls are marked with either lighter or heavier.  
  72.             // From the Pigeon Principle, we can choose two balls with the same mark.  
  73.             Ball w1;  
  74.             Ball w2;  
  75.             Ball w3;  
  76.   
  77.             if (balla.getStatus().equals(ballb.getStatus()))  
  78.             {  
  79.                 w1 = balla;  
  80.                 w2 = ballb;  
  81.                 w3 = ballc;  
  82.             }  
  83.             else if (balla.getStatus().equals(ballc.getStatus()))  
  84.             {  
  85.                 w1 = balla;  
  86.                 w2 = ballc;  
  87.                 w3 = ballb;  
  88.             }  
  89.             else if (ballb.getStatus().equals(ballc.getStatus()))  
  90.             {  
  91.                 w1 = ballb;  
  92.                 w2 = ballc;  
  93.                 w3 = balla;  
  94.             }  
  95.             else  
  96.             {  
  97.                 throw new RuntimeException("The balls are not marked properly");  
  98.             }  
  99.   
  100.             int result = scale.weigh(w1, w2);  
  101.             if (result == Scale.EVEN)  
  102.             {  
  103.                 w1.setStatus(Ball.NORMAL);  
  104.                 w2.setStatus(Ball.NORMAL);  
  105.             }  
  106.             else if (result == Scale.HEAVIER)  
  107.             {  
  108.                 w3.setStatus(Ball.NORMAL);  
  109.                 if (w1.getStatus().equals(Ball.HEAVIER)) // heavier is bad  
  110.                 {  
  111.                     w2.setStatus(Ball.NORMAL);  
  112.                 }  
  113.                 else // lighter is bad  
  114.                 {  
  115.                     w1.setStatus(Ball.NORMAL);  
  116.                 }  
  117.             }  
  118.             else  
  119.             {  
  120.                 w3.setStatus(Ball.NORMAL);  
  121.                 if (w1.getStatus().equals(Ball.HEAVIER))  
  122.                 {  
  123.                     w1.setStatus(Ball.NORMAL);  
  124.                 }  
  125.                 else  
  126.                 {  
  127.                     w2.setStatus(Ball.NORMAL);  
  128.                 }  
  129.             }  
  130.         }  
  131.     }  
  132.   
  133.     public void setScale(Scale scale) { this.scale = scale; }  
  134. }