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

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