8枚便士，7枚一樣重、1枚比較輕，你有1個【秤】 - 拼圖

英特爾公司（Intel）如何面試系統驗證工程師？

他們問：「你有8枚便士，7枚一樣重、1枚比較輕，你有1個秤
，你要如何在3次機會中找出那個最輕的？」




小弟想法如下 想請各位板友幫忙看看有沒有矛盾的地方~

假定球序號為n1 n2....n8

step1.先取n1~n4

step2 再取n3~n6

這樣會有下列case

1.第一次>第二次 那就代表n5~n6其中一顆
2.第一次<第二次 那就是n1~n2其中一顆
以上這兩種case只要挑一個出來稱就結束了


3.第一次=第二次 那就是n7~n8其中一顆了 或是 n3~n4

case3部分特別討論

令a={n3,n4} b={n7,n8}
自a,b兩set中挑n3,n7出來
放在磅稱上面秤
if (n3+n7) =(n1~n4)/2 ->n8即為所求
(n3+n7) >(n1~n4)/2 ->n4即為所求


(n3+n7) <(n1~n4)/2 分成兩情形討論
如何判斷是n3 還是n7呢?
我們用(step1+step2-(n3+n7)*2)/4 即可得到單顆的重量
接著將(step1-單顆重量*4)
if=0 代表n1=n2=n3=n4 所以就是n7
if<0 代表n3<單顆重量 所以就是n3

故得證

--