[其他] 用電子秤分出8枚便士中較輕的一個~
英特爾在面試系統驗證工程師:
你有8枚便士，7枚一樣重、1枚比較輕，你有1個【秤】，
你要如何在3次機會中找出那個最輕的？
note:所謂的秤 就像體重計一樣 只能量重量而已
不是像天平一樣有2邊喔~
小弟的想法如下 不知道正不正確 希望版友給些意見 謝謝:)
假定球序號為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
故得證
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.1.102
推
07/03 12:47, , 1F
07/03 12:47, 1F
→
07/03 12:47, , 2F
07/03 12:47, 2F
→
07/03 12:48, , 3F
07/03 12:48, 3F
→
07/03 12:48, , 4F
07/03 12:48, 4F
→
07/03 12:49, , 5F
07/03 12:49, 5F
推
07/04 10:11, , 6F
07/04 10:11, 6F
→
07/04 13:01, , 7F
07/04 13:01, 7F
→
07/04 13:02, , 8F
07/04 13:02, 8F