程式扎記: [ Algorithm in Java ] 老掉牙 : 八枚銀幣

標籤

2011年1月21日 星期五

[ 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() 找出假幣!
  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(4false); // Put light fake coin in position 2.  
  64.         eightCoins.startCheck();  
  65.     }  
  66. }  

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!