八銀幣

November 30, 2021

現有八枚銀幣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 fake(int[]); 
 
int main(void) { 
    srand(time(NULL)); 

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

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

    fake(coins); 

    printf("\n\n列出所有錢幣重量:"); 
    for(i = 0; i < 8; i++) {
        printf("%d ", coins[i]); 
    }
    
    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 fake(int coins[]) { 
    int c1 = coins[0] + coins[1] + coins[2] - coins[3] - coins[4] - coins[5];
    int c2 = coins[0] + coins[3] - coins[1] - coins[4];
    
    if(!c1) {
        if(coins[6] > coins[7]) compare(coins, 6, 7, 0);
        else                    compare(coins, 7, 6, 0); 
    }
    else if(c1 > 0) { 
        if(!c2)                 compare(coins, 2, 5, 0); 
        else if(c2 > 0)         compare(coins, 0, 4, 1); 
        else                    compare(coins, 1, 3, 0); 
    } 
    else { 
        if(!c2)                 compare(coins, 5, 2, 0); 
        else if(c2 > 0)         compare(coins, 3, 1, 0); 
        else                    compare(coins, 4, 0, 1); 
    } 
}
interface Fake {
    void doAction(int index, boolean isBigger);
}

public class Coins {
    public static void compare(int[] coins, int i, int j, int k, Fake fake) {
        if(coins[i] > coins[k]) fake.doAction(i + 1, true);
        else                    fake.doAction(j + 1, false);
    }
    
    public static void compare(int[] coins, Fake fake) {
        Integer h1 = coins[0] + coins[1] + coins[2];
        Integer h2 = coins[3] + coins[4] + coins[5];
        Integer h3 = coins[0] + coins[3];
        Integer h4 = coins[1] + coins[4];
        
        switch(h1.compareTo(h2)) {
            case  0: if(coins[6] > coins[7]) 
                                  compare(coins, 6, 7, 0, fake);
                     else         
                                  compare(coins, 7, 6, 0, fake);
                     break;
            case  1: switch(h3.compareTo(h4)) {
                         case  0: compare(coins, 2, 5, 0, fake); break;
                         case  1: compare(coins, 0, 4, 1, fake); break;
                         case -1: compare(coins, 1, 3, 0, fake); 
                     } break;
            case -1: switch(h3.compareTo(h4)) {
                         case  0: compare(coins, 5, 2, 0, fake); break;
                         case  1: compare(coins, 3, 1, 0, fake); break;
                         case -1: compare(coins, 4, 0, 1, fake); 
                     }
        }
    }

    public static void main(String[] args) {
        compare(new int[] {10, 10, 11, 10, 10, 10, 10, 10},
          (index, isBigger) -> {
             System.out.printf("硬幣 %d 較%s", index, isBigger ? "大" : "小");
          }
        );
    }
}
def compare(coins, i, j, k):
    return (i + 1, True) if coins[i] > coins[k] else (j + 1, False)
    
def coins(coins):
    c1 = sum(coins[0:3]) - sum(coins[3:6])
    c2 = sum([coins[0], coins[3]]) - sum([coins[1], coins[4]])
    return (                           (compare(coins, 6, 7, 0) 
            if coins[6] > coins[7] else compare(coins, 7, 6, 0)) 
        if c1 == 0 else (((             compare(coins, 2, 5, 0) 
            if c2 == 0 else             compare(coins, 0, 4, 1)) 
            if c2 > 0 else              compare(coins, 1, 3, 0)) 
        if c1 > 0 else (                compare(coins, 5, 2, 0)
            if c2 == 0 else (           compare(coins, 3, 1, 0)
            if c2 > 0 else              compare(coins, 4, 0, 1)))))
    
i, isBigger = coins([10, 10, 10, 10, 2, 10, 10, 10])
print('硬幣', i, '重' if isBigger else '輕', end='')
def coins(coins: List[Int]) = {
    def compare(coins: List[Int], i: Int, j: Int, k: Int) = {
        if(coins(i) > coins(k)) (i + 1, true) else (j + 1, false)
    }

    val h1 = coins.slice(3, 6).sum
    val h2 = coins.slice(3, 6).sum
    val h3 = coins(0) + coins(3);
    val h4 = coins(1) + coins(4);
    
    h1.compareTo(h2) match {
        case  0 => if(coins(6) > coins(7)) compare(coins, 6, 7, 0)
                   else                    compare(coins, 7, 6, 0)
        case  1 => h3.compareTo(h4) match {
                       case  0 =>          compare(coins, 2, 5, 0)
                       case  1 =>          compare(coins, 0, 4, 1)
                       case -1 =>          compare(coins, 1, 3, 0)
                   }
        case -1 => h3.compareTo(h4) match {
                       case  0 =>          compare(coins, 5, 2, 0)
                       case  1 =>          compare(coins, 3, 1, 0)
                       case -1 =>          compare(coins, 4, 0, 1)
                   }
    }
}

val (i, isBigger) = coins(List(10, 10, 11, 10, 10, 10, 10, 10))
printf("硬幣 %d 較%s", i, if(isBigger) "重" else "輕")
# encoding: UTF-8
def compare(coins, i, j, k)
   if coins[i] > coins[k]
       {index: i + 1, isBigger: true} 
   else 
       {index: j + 1, isBigger: false} 
   end
end

def coins(coins)
    h1 = coins.take(3).reduce(:+)
    h2 = coins[3...6].reduce(:+)
    h3 = coins[0] + coins[3]
    h4 = coins[1] + coins[4]
    
    case h1 <=> h2
    when  0; if coins[6] > coins[7]
                      compare(coins, 6, 7, 0)
             else
                      compare(coins, 7, 6, 0) 
             end
    when  1; case h3 <=> h4
             when  0; compare(coins, 2, 5, 0)
             when  1; compare(coins, 0, 4, 1)
             when -1; compare(coins, 1, 3, 0)
             end
    when -1; case h3 <=> h4
             when  0; compare(coins, 5, 2, 0)
             when  1; compare(coins, 3, 1, 0)
             when -1; compare(coins, 4, 0, 1)
             end
    end
end

fake = coins [10, 10, 10, 10, 2, 10, 10, 10]
printf("假幣 %d 較%s", fake[:index], if fake[:isBigger]; "重" else "輕" end)
var coins = function() {
    function compare(coins, i, j, k) {
        return coins[i] > coins[k] ? {index: i + 1, isBigger: true} : 
                                     {index: j + 1, isBigger: false};
    }
    return function(coins) {
        var c1 = coins[0] + coins[1] + coins[2] - 
                 coins[3] - coins[4] - coins[5];
        var c2 = coins[0] + coins[3] - coins[1] - coins[4];
        return (c1 === 0 ? (coins[6] > coins[7] ? compare(coins, 6, 7, 0)  : 
                                                  compare(coins, 7, 6, 0)) : 
               (c1 > 0 ? 
                   (c2 === 0 ?                    compare(coins, 2, 5, 0)  : 
                   (c2 > 0 ?                      compare(coins, 0, 4, 1)  : 
                                                  compare(coins, 1, 3, 0))): 
                   (c2 === 0 ?                    compare(coins, 5, 2, 0)  : 
                   (c2 > 0 ?                      compare(coins, 3, 1, 0)  : 
                                                  compare(coins, 4, 0, 1))))
               );
    };
}();

var fake = coins([10, 10, 10, 2, 10, 10, 10, 10]);
print('假幣 ' + fake.index + ' 較' + (fake.isBigger ? '重' : '輕'));
import Text.Printf

coins cs = case h1 `compare` h2 of
               EQ -> if cs !! 6 > cs !! 7 then comp cs 6 7 0
                                          else comp cs 7 6 0
               GT -> case h3 `compare` h4 of
                         EQ -> comp cs 2 5 0
                         GT -> comp cs 0 4 1
                         LT -> comp cs 1 3 0
               LT -> case h3 `compare` h4 of
                         EQ -> comp cs 5 2 0
                         GT -> comp cs 3 1 0
                         LT -> comp cs 4 0 1
    where h1 = sum \$ take 3 cs
          h2 = sum \$ take (5 - 3) \$ drop 3 cs
          h3 = cs !! 0 + cs !! 3
          h4 = cs !! 1 + cs !! 4
          comp cs i j k= if cs !! i > cs !! k then (i + 1, True) 
                                              else (j + 1, False)
          
main = printf "Coin %d is %s" index (if isHeavy then "heavy" else "light")
    where (index, isHeavy) = coins [10, 10, 10, 10, 2, 10, 10, 10]
round3(Coins, I, _, K, [I, heavier]) :-
    nth1(I, Coins, CI), nth1(K, Coins, CK), CI > CK, !.
round3(_, _, J, _, [J, lighter]).

ordercases((>), (=), Coins, Fake) :- round3(Coins, 3, 6, 1, Fake), !.
ordercases((>), (>), Coins, Fake) :- round3(Coins, 1, 5, 2, Fake), !.
ordercases((>), (<), Coins, Fake) :- round3(Coins, 2, 4, 1, Fake), !.
ordercases((<), (=), Coins, Fake) :- round3(Coins, 6, 3, 1, Fake), !.
ordercases((<), (>), Coins, Fake) :- round3(Coins, 4, 2, 1, Fake), !.
ordercases((<), (<), Coins, Fake) :- round3(Coins, 5, 1, 2, Fake).

round2(Coins, (=), Fake) :-
    nth1(7, Coins, C7), nth1(8, Coins, C8), 
    compare(Order, C7, C8), (
       Order == (>) -> round3(Coins, 7, 8, 1, Fake);
       round3(Coins, 7, 8, 1, Fake)
    ).

round2(Coins, H12Order, Fake) :-
    [C1, C2, _, C4, C5, _, _, _] = Coins,
    H3 is C1 + C4, 
    H4 is C2 + C5,
    compare(H34Order, H3, H4), 
    ordercases(H12Order, H34Order, Coins, Fake).

which(Coins, Fake) :-
    [C1, C2, C3, C4, C5, C6, _, _] = Coins,
    H1 is C1 + C2 + C3, 
    H2 is C4 + C5 + C6,
    compare(Order, H1, H2),
    round2(Coins, Order, Fake).
    
main(_) :- 
    which([1, 1, 1, 2, 1, 1, 1, 1], Fake),
    write(Fake), nl.round3(Coins, I, _, K, [I, heavier]) :-
    nth1(I, Coins, CI), nth1(K, Coins, CK), CI > CK, !.
round3(_, _, J, _, [J, lighter]).

ordercases((>), (=), Coins, Fake) :- round3(Coins, 3, 6, 1, Fake), !.
ordercases((>), (>), Coins, Fake) :- round3(Coins, 1, 5, 2, Fake), !.
ordercases((>), (<), Coins, Fake) :- round3(Coins, 2, 4, 1, Fake), !.
ordercases((<), (=), Coins, Fake) :- round3(Coins, 6, 3, 1, Fake), !.
ordercases((<), (>), Coins, Fake) :- round3(Coins, 4, 2, 1, Fake), !.
ordercases((<), (<), Coins, Fake) :- round3(Coins, 5, 1, 2, Fake).

round2(Coins, (=), Fake) :-
    nth1(7, Coins, C7), nth1(8, Coins, C8), 
    compare(Order, C7, C8), (
       Order == (>) -> round3(Coins, 7, 8, 1, Fake);
       round3(Coins, 7, 8, 1, Fake)
    ).

round2(Coins, H12Order, Fake) :-
    [C1, C2, _, C4, C5, _, _, _] = Coins,
    H3 is C1 + C4, 
    H4 is C2 + C5,
    compare(H34Order, H3, H4), 
    ordercases(H12Order, H34Order, Coins, Fake).

which(Coins, Fake) :-
    [C1, C2, C3, C4, C5, C6, _, _] = Coins,
    H1 is C1 + C2 + C3, 
    H2 is C4 + C5 + C6,
    compare(Order, H1, H2),
    round2(Coins, Order, Fake).
    
main(_) :- 
    which([1, 1, 1, 2, 1, 1, 1, 1], Fake),
    write(Fake), nl.
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

from '/lib/math' import sum

def compare(coins, i, j, k) { 
    if coins.get(i) > coins.get(k) {
        println('The fake coin {0} is heavier.'.format(i + 1))
    } 
    else {
        println('The fake coin {0} is lighter.'.format(j + 1))
    }                   
} 

def coins(coins) {
    c1 = sum(coins.slice(0, 3)) - sum(coins.slice(3, 6))
    c2 = sum(coins.get(0), coins.get(3)) - sum(coins.get(1), coins.get(4))

    if c1 == 0 {
        compare67(coins)
    }
    else {
        compare1To5(coins, c1, c2)
    }
}

def compare67(coins) {
    if coins.get(6) > coins.get(7) {
        compare(coins, 6, 7, 0)
    }
    else {
        compare(coins, 7, 6, 0)
    }
}

def compare1To5(coins, c1, c2) {
    if c1 > 0 {
        c1GreaterThan0(coins, c2)
    } 
    else { 
        c1NotGreaterThan0(coins, c2)
    } 
}

def c1GreaterThan0(coins, c2) {
    if c2 == 0 {
        compare(coins, 2, 5, 0) 
    }
    else {
        if c2 > 0 {
            compare(coins, 0, 4, 1) 
        }
        else {
            compare(coins, 1, 3, 0)
        }
    } 
}

def c1NotGreaterThan0(coins, c2) {
    if c2 == 0 {
        compare(coins, 5, 2, 0)
    }
    else {
        if c2 > 0 {
            compare(coins, 3, 1, 0)
        }
        else {
            compare(coins, 4, 0, 1)
        }
    } 
}

coins([5, 5, 5, 4, 5, 5, 5, 5])