[問題] 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
故得證
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.1.102
→
07/02 21:51, , 1F
07/02 21:51, 1F
→
07/02 21:51, , 2F
07/02 21:51, 2F
推
07/02 21:54, , 3F
07/02 21:54, 3F
推
07/02 21:56, , 4F
07/02 21:56, 4F
→
07/02 21:56, , 5F
07/02 21:56, 5F
推
07/02 21:59, , 6F
07/02 21:59, 6F
推
07/02 22:01, , 7F
07/02 22:01, 7F
推
07/02 22:33, , 8F
07/02 22:33, 8F
→
07/02 23:02, , 9F
07/02 23:02, 9F
→
07/03 01:55, , 10F
07/03 01:55, 10F
→
07/03 01:56, , 11F
07/03 01:56, 11F
→
07/03 01:57, , 12F
07/03 01:57, 12F
→
07/03 02:00, , 13F
07/03 02:00, 13F
推
07/03 06:58, , 14F
07/03 06:58, 14F
→
07/03 07:00, , 15F
07/03 07:00, 15F
→
07/03 07:01, , 16F
07/03 07:01, 16F
→
07/03 07:03, , 17F
07/03 07:03, 17F
推
07/03 07:10, , 18F
07/03 07:10, 18F
→
07/03 07:13, , 19F
07/03 07:13, 19F
→
07/03 07:14, , 20F
07/03 07:14, 20F
推
07/03 15:19, , 21F
07/03 15:19, 21F
→
07/04 00:40, , 22F
07/04 00:40, 22F
推
07/04 08:03, , 23F
07/04 08:03, 23F
推
07/08 10:25, , 24F
07/08 10:25, 24F
→
07/08 10:48, , 25F
07/08 10:48, 25F
推
07/13 16:57, , 26F
07/13 16:57, 26F
推
07/13 17:02, , 27F
07/13 17:02, 27F
討論串 (同標題文章)
以下文章回應了本文:
完整討論串 (本文為第 1 之 2 篇):