作者AIdrifter (交錯地帶)
看板puzzle
標題[問題] 8枚便士，7枚一樣重、1枚比較輕，你有1個【秤】
時間Sat Jul 2 21:33:53 2011
英特爾公司（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
1F：→ cj6u40:感覺好麻煩，不是有更快的方法嗎 07/02 21:51
2F：→ cj6u40:抱歉只是我個人頭腦比較簡單一點 Orz 07/02 21:51
3F：推 AlexCYW:我怎麼認為是兩次.. 07/02 21:54
4F：推 walkwall:兩次是天平 07/02 21:56
5F：→ walkwall:我記得不是討論過了嗎? 07/02 21:56
6F：推 AlexCYW:也對 07/02 21:59
7F：推 walkwall:不過上次討論好像不是討論重量秤的部分 07/02 22:01
8F：推 rehearttw:唉！還是要先定義「秤」... 07/02 22:33
9F：→ killyou:請問是電子秤還是天平秤? 主試官:有看到河邊那條木船嗎? 07/02 23:02
10F：→ AIdrifter:我寫的是電子秤得解阿....@@ 會很複雜嗎? 07/03 01:55
11F：→ AIdrifter:只要拿n1~n4 n3~n6最後來個計算 就可以判斷剩下的是哪 07/03 01:56
12F：→ AIdrifter:2顆了............... 07/03 01:57
13F：→ AIdrifter:想法是利用交集會產生2個球 最後再做判斷.... 07/03 02:00
14F：推 walkwall:基本上這個接看起來應該是對的 不過主要是秤的定義 07/03 06:58
15F：→ walkwall:(上行更正->這個解) 不過秤要能夠乘除就要有精確刻度 07/03 07:00
16F：→ walkwall:一般來說題目說明秤 預設往往是只能比較大小而無刻度的 07/03 07:01
17F：→ walkwall:所以就如同許老師所言 又回到定義問題 07/03 07:03
18F：推 walkwall:有興趣可以打 /秤 找到之前的討論 07/03 07:10
19F：→ walkwall:還有 [閒聊] 八卦板的「超怪面試問題」 這個討論串 07/03 07:13
20F：→ puzzlez:/ 面試 就行了 文章沒有很多～ 07/03 07:14
21F：推 turtleqqq:有印象~ 記得可以證明無解.. 07/03 15:19
22F：→ AIdrifter:sorry 我這case如果是 n7輕是不行的 失敗orz 07/04 00:40
23F：推 michaeldrum:(奸笑) 07/04 08:03
24F：推 fjjkk:分一半 再一半 再一半 07/08 10:25
25F：→ walkwall:-.- 樓上沒看懂我們的討論 07/08 10:48
26F：推 SansWord:可以看一下我之前發的文章(搜尋id)，我覺得無解 07/13 16:57
27F：推 SansWord:我解的很不踏實，想聽聽你們的看法。 07/13 17:02