八枚銀幣


 說明

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

實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell    Prolog

  • C
#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);
}
}

  • Java
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},
// JDK8 Lambda
(index, isBigger) -> {
System.out.printf("硬幣 %d 較%s", index, isBigger ? "大" : "小");
}
);
}
}

  • Python
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='')

  • Scala
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 "輕")

  • Ruby
# encoding: Big5
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)

  • JavaScript
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 ? '重' : '輕'));

  • Haskell
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.