說明
現有八枚銀幣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假幣的重量比真幣輕。
完整的比較決策樹如下圖所示：
實作：Toy C Java
Python Scala
Ruby JavaScript
Haskell Prolog
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])#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},
// JDK8 Lambda
(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: 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)
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.