[ Algorithm in Java ] 老掉牙 : 八枚銀幣

轉載自 這裡 
前言 : 
現有八枚銀幣a b c d e f g h，已知其中一枚是假幣，其重量不同於真幣，但不知是較輕或較重，如何使用天平以最少的比較次數，決定出哪枚是假幣，並得知假幣比真幣較輕或較重. 

解法 : 
單就求假幣的問題是不難，但問題限制使用最少的比較次數，所以我們不能以單純的迴圈比較來求解，我們可以使用決策樹（decision tree），使用分析與樹狀圖來協助求解。 
一個簡單的狀況是這樣的，我們比較a+b+c與d+e+f ，如果相等，則假幣必是g或h，我們先比較g或h哪個較重，如果g較重，再與a比較（a是真幣），如果g等於a，則g為真幣，則h為假幣，由於h比g輕而 g是真幣，則h假幣的重量比真幣輕。 
完整的比較決策樹如下圖所示 : 
 
為了方便使用迴圈，使用號碼0至7表示銀幣，範例程式可以讓您輸入假幣重量，但您無法事先得知假幣是哪一枚，程式可得知假幣是哪一枚，且它比真幣輕或重. 

實作 : 

- Java solution : 透過類別 EightCoins 設定假幣位子與比其他七枚硬幣重還是輕. 並透過函式 startCheck() 找出假幣!

view plaincopy to clipboardprint?

1. package john.algorithms;  
2.   
3. public class EightCoins {  
4.     final static int a = 0, b = 1, c = 2, d = 3, e = 4, f = 5, g = 6, h = 7;  
5.     int[] eightCoins;  
6.   
7.     public EightCoins(int findex, boolean isLight) {  
8.         eightCoins = new int[8];  
9.         for (int i = 0; i < 8; i++)  
10.             eightCoins[i] = 10;  
11.         if (isLight)  
12.             eightCoins[findex] = 8;  
13.         else  
14.             eightCoins[findex] = 12;  
15.     }  
16.   
17.     private void compare(int a, int b, int c) {  
18.         if (eightCoins[a] > eightCoins[b])  
19.             System.out.printf("Fake coin in %d is heavy!\n", a);  
20.         else  
21.             System.out.printf("Fake coin in %d is light!\n", c);  
22.     }  
23.   
24.     public void startCheck() {  
25.         int abc = eightCoins[a] + eightCoins[b] + eightCoins[c];  
26.         int def = eightCoins[d] + eightCoins[e] + eightCoins[f];  
27.         int ad = eightCoins[a] + eightCoins[d];  
28.         int be = eightCoins[b] + eightCoins[e];  
29.         if (abc > def) {  
30.             if (ad > be) {  
31.                 // a,e is suspected and b is safe.  
32.                 compare(a, b, e);  
33.             } else if (ad < be) {  
34.                 // b,e is suspected and a is safe.  
35.                 compare(b, a, e);  
36.             } else {  
37.                 // c,f is suspected and a is safe.  
38.                 compare(c, a, f);  
39.             }  
40.         } else if (abc == def) {  
41.             if (eightCoins[g] > eightCoins[h]) {  
42.                 // g, h is suspected and a is safe.  
43.                 compare(g, a, h);  
44.             } else {  
45.                 // g, h is suspected and a is safe  
46.                 compare(h, a, g);  
47.             }  
48.         } else {  
49.             if (ad > be) {  
50.                 // d, b is suspected and a is safe  
51.                 compare(d, a, b);  
52.             } else if (ad < be) {  
53.                 // e, a is suspected and b is safe  
54.                 compare(e, b, a);  
55.             } else {  
56.                 // f, c is suspected and a is safe  
57.                 compare(f, a, c);  
58.             }  
59.         }  
60.     }  
61.       
62.     public static void main(String args[]) {  
63.         EightCoins eightCoins = new EightCoins(4, false); // Put light fake coin in position 2.  
64.         eightCoins.startCheck();  
65.     }  
66. }