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

The problem is:

There is one counterfeit coin among 12 coins. It is unknown whether the counterfeit is lighter or heavier than a genuine coin(all genuine coins weigh the same). Using 3 weighings on a pan balance, how can the counterfeit be identified and determined to be lighter or heavier than a genuine coin.
 
To generalize this, given n coins with only one counterfeit, how many weighings are needed in order to find the counterfeit and determine whether it's lighter or heavier?

I first encountered this problem in the book "The USSR Olympiad problem book"(from Dover, check amazon site). There is also a Chinese translation from *.

It's the #6 problem in the book. The 12 and 13-coin case is well known. The complete solution is given in the book. Here I am more interested in the programming solution.

Apparently, we have balls and a scale, so naturally, we should create two classes. Let's look at the Scale class. The functionality of a scale is to weigh both sides, so we should have a weigh() function, that could take two sets of balls, or just two balls. Also we want to count how many times we use the scale, so we have an internal counter for this. The last thing is to flag whether both sides are equal or not, therefore we need some constants to indicate whether the first set is heavier/lighter/equal to the second set.

Then we definitely need a Ball class. In this class, we need a weight field for the problem. A simple approach is to use an int type to indicate whether it's normal/heavier/lighter. However, all we need for this type is to be able to add up weights in a set of balls and compare weights from two sets of balls on the scale.  So we could encapsulate these in a class, called Weight.

java 代码

 

1. package scale;  
2. /** 
3.  * The only behaviors we care are the add and compare methods. 
4.  */  
5. public class Weight implements Comparable  
6. {  
7.     private int amount;  
8.   
9.     public Weight(int amount)  
10.     {  
11.         this.amount = amount;  
12.     }  
13.   
14.     public void add(Weight weight)  
15.     {  
16.         if (weight == null) throw new IllegalArgumentException("weight is null");  
17.   
18.         amount += weight.amount;  
19.     }  
20.   
21.     public boolean equals(Object obj)  
22.     {  
23.         if (!(obj instanceof Weight)) return false;  
24.   
25.         Weight weight = (Weight)obj;  
26.         return this.amount == weight.amount;  
27.     }  
28.   
29.     public int hashCode() { return amount; }  
30.   
31.     public int compareTo(Object obj)  
32.     {  
33.         // this is arguable  
34.         if (!(obj instanceof Weight)) return -1;  
35.   
36.         Weight weight = (Weight)obj;  
37.         if (this.amount == weight.amount) return 0;  
38.         else  
39.         {  
40.             return this.amount > weight.amount ? 1 : -1;  
41.         }  
42.     }  
43.   
44.     public String toString() { return "(weight=" + amount + ")"; }  
45. }  

Now, let's look at the Ball class.

java 代码

 

1. package scale;  
2.   
3. public class Ball  
4. {  
5.     // These constants are totally ordered(compared), can be sum'd up.  
6.     // So if we want replace this type, we have to have these two features.  
7.     // Also this is the input: scale.Scale can use the sum method only.  
8.     public static final Weight WEIGHT_HEAVIER = new Weight(1);  
9.     public static final Weight WEIGHT_LIGHTER = new Weight(-1);  
10.     public static final Weight WEIGHT_NORNAL  = new Weight(0);  
11.   
12.     // These flags can be of any type.  
13.     // This is the result. Though this is 1-1 mapping to the enums in the scale.Scale class,  
14.     // we want to keep it seperate since this is our output.  
15.     public static final String NORMAL  = "Normal";  
16.     public static final String HEAVIER = "Heavier";  
17.     public static final String LIGHTER = "Lighter";  
18.     public static final String UNKNOWN = "unknown";  
19.   
20.     private String id = "";  
21.     private Weight weight = WEIGHT_NORNAL;  
22.   
23.     private String status = UNKNOWN;  
24.   
25.     public Ball(String id, Weight weight)  
26.     {  
27.         this.id = id;  
28.         this.weight = weight;  
29.     }  
30.   
31.     public String toString()  
32.     {  
33.         return "Ball[id=" + id + " " + weight.toString() + " status=" + status + "]";  
34.     }  
35.   
36.     // make this package level so solvers don't have access to cheat on this.  
37.     Weight getWeight() { return weight; }  
38.   
39.     public String getStatus() { return status; }  
40.     public void setStatus(String status) { this.status = status; }  
41.   
42.     public boolean validate()  
43.     {  
44.         return (this.weight.equals(WEIGHT_HEAVIER) && status.equals(HEAVIER)) ||  
45.                (this.weight.equals(WEIGHT_LIGHTER) && status.equals(LIGHTER)) ||  
46.                (this.weight.equals(WEIGHT_NORNAL) && status.equals(NORMAL));  
47.     }  
48. }  

Here I treat the weight as input, and create another field status to detect the ball's weight. This is more like a flag field that we will set later. It's an output. Note that the getWeight() method is package access, so only the Scale class will use this knowledge.