題目:有12個小球，其中有１個是不合格的，其他１１個都合格，請你找出來．要求只能要天平稱３次，并指出不合格的小球是比合格的重還是輕.
CU上的斑竹win_hate已經(jīng)給出了這個問題的一個算法,我把它貼在這里:
設數(shù)據(jù)分為三組 A[1..4],B[1..4],C[1..4]
1 如果 sum(A, 1..4) == sum(B, 1..4) // 目標在 C 中
1.1 如果 sum (A, 1..3) == sum (C, 1..3)
目標為 C[4] 再作一次比較可知輕重，退出。
1.2 如果 sum (A, 1..3) > sum (C, 1..3)
目標較輕，比較 C[1], C[2] 可推出目標之索引，退出。
1.3 如果 sum (A, 1..3) < sum (C, 1..3) 同1.2
2 如果 sum(A, 1..4) > sum (B, 1..4) // 目標不在 C 中，若目標在A中，則重，在B中，則輕。
2.1 如果 A[3]+B[3] +B[4] == A[4] + B[1] + B[2]
目標在 A[1]A[2] 中，且目標較重，比較 A[1], A[2] 可得目標索引，退出。
2.2 如果 A[3]+B[3] +B[4] > A[4] + B[1] + B[2] // (X)
2.2.1 如果 B[1]!=B[2], 則目標在 B 中，較輕，從比較結果可知索引，退出。
2.2.2 如果 B[1]==B[2], 則目標不為 B[1], B[2]。
同時，目標也不為 A[4]，因為若目標在A中，必定較重，這與(X) 相悖。
目標不為 B[3], B[4]，因為若目標在 B 中，必定較輕，這與(X) 相悖.
故目標為 A[3](其實此時(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=