[問題] 8枚便士，7枚一樣重、1枚比較輕，你有1個【秤】

[AIdrifter (交錯地帶)]

英特爾公司（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
→ cj6u40:感覺好麻煩，不是有更快的方法嗎
→ cj6u40:抱歉只是我個人頭腦比較簡單一點 Orz
推 AlexCYW:我怎麼認為是兩次..
推 walkwall:兩次是天平
→ walkwall:我記得不是討論過了嗎?
推 AlexCYW:也對
推 walkwall:不過上次討論好像不是討論重量秤的部分
推 rehearttw:唉！還是要先定義「秤」...
→ killyou:請問是電子秤還是天平秤?   主試官:有看到河邊那條木船嗎?
→ AIdrifter:我寫的是電子秤得解阿....@@ 會很複雜嗎?
→ AIdrifter:只要拿n1~n4 n3~n6最後來個計算 就可以判斷剩下的是哪
→ AIdrifter:2顆了...............
→ AIdrifter:想法是利用交集會產生2個球 最後再做判斷....
推 walkwall:基本上這個接看起來應該是對的  不過主要是秤的定義
→ walkwall:(上行更正->這個解) 不過秤要能夠乘除就要有精確刻度
→ walkwall:一般來說題目說明秤  預設往往是只能比較大小而無刻度的
→ walkwall:所以就如同許老師所言  又回到定義問題
推 walkwall:有興趣可以打  /秤  找到之前的討論
→ walkwall:還有  [閒聊] 八卦板的「超怪面試問題」  這個討論串
→ puzzlez:/ 面試 就行了 文章沒有很多～
推 turtleqqq:有印象~ 記得可以證明無解..
→ AIdrifter:sorry 我這case如果是 n7輕是不行的 失敗orz
推 michaeldrum:(奸笑)
推 fjjkk:分一半 再一半 再一半
→ walkwall:-.- 樓上沒看懂我們的討論
推 SansWord:可以看一下我之前發的文章(搜尋id)，我覺得無解
推 SansWord:我解的很不踏實，想聽聽你們的看法。