From Gossip@caterpillar

Algorithm Gossip: 八枚銀幣

說明

現有八枚銀幣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表示銀幣，範例程式可以讓您輸入假幣重量，但您無法事先得知假幣是哪一枚，程式可得知假幣是哪一枚，且它比真幣輕或重。

實作

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
 
void compare(int[], int, int, int); 
void eightcoins(int[]); 
 
int main(void) { 
    int coins[8] = {0}; 
    int i; 

    srand(time(NULL)); 

    for(i = 0; i < 8; i++) 
        coins[i] = 10; 

    printf("\n輸入假幣重量(比10大或小)："); 
    scanf("%d", &i); 
    coins[rand() % 8] = i; 

    eightcoins(coins); 

    printf("\n\n列出所有錢幣重量："); 
    for(i = 0; i < 8; i++) 
        printf("%d ", coins[i]); 

    printf("\n"); 

    return 0; 
} 

void compare(int coins[], int i, int j, int k) { 
    if(coins[i] > coins[k]) 
        printf("\n假幣 %d 較重", i+1); 
    else 
        printf("\n假幣 %d 較輕", j+1); 
} 

void eightcoins(int coins[]) { 
    if(coins[0]+coins[1]+coins[2] == 
       coins[3]+coins[4]+coins[5]) { 
        if(coins[6] > coins[7]) 
            compare(coins, 6, 7, 0); 
        else 
            compare(coins, 7, 6, 0); 
    } 
    else if(coins[0]+coins[1]+coins[2] > 
            coins[3]+coins[4]+coins[5]) { 
        if(coins[0]+coins[3] == coins[1]+coins[4]) 
            compare(coins, 2, 5, 0); 
        else if(coins[0]+coins[3] > coins[1]+coins[4]) 
            compare(coins, 0, 4, 1); 
        if(coins[0]+coins[3] < coins[1]+coins[4]) 
            compare(coins, 1, 3, 0); 
    } 
    else if(coins[0]+coins[1]+coins[2] <
            coins[3]+coins[4]+coins[5]) { 
        if(coins[0]+coins[3] == coins[1]+coins[4]) 
            compare(coins, 5, 2, 0); 
        else if(coins[0]+coins[3] > coins[1]+coins[4]) 
            compare(coins, 3, 1, 0); 
        if(coins[0]+coins[3] < coins[1]+coins[4]) 
            compare(coins, 4, 0, 1); 
    } 
}

Java

public class Coins {
    private int[] coins;
    
    public Coins() {
        coins = new int[8];
        for(int i = 0; i < 8; i++) 
            coins[i] = 10; 
    }
    
    public void setFake(int weight) {
        coins[(int) (Math.random() * 7)] = weight;
    }
    
    public void fake() {
        if(coins[0]+coins[1]+coins[2] == 
           coins[3]+coins[4]+coins[5]) { 
            if(coins[6] > coins[7]) 
                compare(6, 7, 0); 
            else 
                compare(7, 6, 0); 
        } 
        else if(coins[0]+coins[1]+coins[2] > 
                coins[3]+coins[4]+coins[5]) { 
            if(coins[0]+coins[3] == coins[1]+coins[4]) 
                compare(2, 5, 0); 
            else if(coins[0]+coins[3] > coins[1]+coins[4]) 
                compare(0, 4, 1); 
            if(coins[0]+coins[3] < coins[1]+coins[4]) 
                compare(1, 3, 0); 
        } 
        else if(coins[0]+coins[1]+coins[2] < 
                coins[3]+coins[4]+coins[5]) { 
            if(coins[0]+coins[3] == coins[1]+coins[4]) 
                compare(5, 2, 0); 
            else if(coins[0]+coins[3] > coins[1]+coins[4]) 
                compare(3, 1, 0); 
            if(coins[0]+coins[3] < coins[1]+coins[4]) 
                compare(4, 0, 1); 
        } 
    }
    
    protected void compare(int i, int j, int k) {
        if(coins[i] > coins[k]) 
            System.out.print("\n假幣 " + (i+1) + " 較重"); 
        else 
            System.out.print("\n假幣 " + (j+1) + " 較輕"); 
    }
    
    public static void main(String[] args) {
        if(args.length == 0) {
            System.out.println("輸入假幣重量（比10大或小）");
            System.out.println("ex. java Coins 5");
            return;
        }
        
        Coins eightCoins = new Coins();
        eightCoins.setFake(Integer.parseInt(args[0]));
        eightCoins.fake();
    }
}