作者AIdrifter (交錯地帶)
看板Math
標題[其他] 用電子秤分出8枚便士中較輕的一個~
時間Sun Jul 3 02:11:51 2011
英特爾在面試系統驗證工程師:
你有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
1F：推 wree45 :第一次左右各放4個 重的那邊拿下 第2次把第一次留著 07/03 12:47
2F：→ wree45 :的4個 各分配到兩邊 一樣重的拿下 07/03 12:47
3F：→ wree45 :第三次類推 07/03 12:48
4F：→ wree45 :不對不是天秤! 07/03 12:48
5F：→ wree45 :以上 別理我... 07/03 12:49
6F：推 ioriblood :目前只算出七個~~八個還在努力= = 07/04 10:11
7F：→ ownlai :我的想法跟妳前面完全一樣 然後最後一步就卡住 07/04 13:01
8F：→ ownlai :而妳最後一步我覺得是錯的 那單顆重量並非絕對正確 07/04 13:02