題目:有12個(gè)小球，其中有１個(gè)是不合格的，其他１１個(gè)都合格，請你找出來．要求只能要天平稱３次，并指出不合格的小球是比合格的重還是輕.
CU上的斑竹win_hate已經(jīng)給出了這個(gè)問題的一個(gè)算法,我把它貼在這里:
設(shè)數(shù)據(jù)分為三組 A[1..4],B[1..4],C[1..4]
1 如果 sum(A, 1..4) == sum(B, 1..4) // 目標(biāo)在 C 中
1.1 如果 sum (A, 1..3) == sum (C, 1..3)
目標(biāo)為 C[4] 再作一次比較可知輕重，退出。
1.2 如果 sum (A, 1..3) > sum (C, 1..3)
目標(biāo)較輕，比較 C[1], C[2] 可推出目標(biāo)之索引，退出。
1.3 如果 sum (A, 1..3) < sum (C, 1..3) 同1.2
2 如果 sum(A, 1..4) > sum (B, 1..4) // 目標(biāo)不在 C 中，若目標(biāo)在A中，則重，在B中，則輕。
2.1 如果 A[3]+B[3] +B[4] == A[4] + B[1] + B[2]
目標(biāo)在 A[1]A[2] 中，且目標(biāo)較重，比較 A[1], A[2] 可得目標(biāo)索引，退出。
2.2 如果 A[3]+B[3] +B[4] > A[4] + B[1] + B[2] // (X)
2.2.1 如果 B[1]!=B[2], 則目標(biāo)在 B 中，較輕，從比較結(jié)果可知索引，退出。
2.2.2 如果 B[1]==B[2], 則目標(biāo)不為 B[1], B[2]。
同時(shí)，目標(biāo)也不為 A[4]，因?yàn)槿裟繕?biāo)在A中，必定較重，這與(X) 相悖。
目標(biāo)不為 B[3], B[4]，因?yàn)槿裟繕?biāo)在 B 中，必定較輕，這與(X) 相悖.
故目標(biāo)為 A[3](其實(shí)此時(shí)(X) 可化為A[3]>A[4] 了), 退出。
2.3 如果 A[3]+B[3] +B[4] < A[4] + B[1] + B[2]
同 2.2
3 如果 sum(A, 1..4) > sum (B, 1..4)
同 2
q.e.d
原文的鏈接:
http://bbs.chinaunix.net/viewthread.php?tid=644659&fpage=1&highlight=