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呢?
:

小弟接續case3有另外想法

但只能在輕球必須少於一般球的1/3才有解

至於鴿籠方面 電子磅秤並沒有平手的概念@@ 所以我不會用tree去想

因該是說沒有頭緒才對....怕漏掉什麼條件

因為可以算出"當下放上去的球"平均重



目前想到其解如下

case3部分特別討論



令一般重為a 較輕者為a-i

若a-i 在 n3~n4中 step1+step2=8a-2i

不在 n3~n4中 step1+step2=8a

而我們知n3+n7必為2a-i

所以
step1+step2-4(2a-i)=2i if (a-i)在n3~n4中
step1+step2-4(2a-i)=4i if (a-i)不在n3~n4中

兩邊同除二 各得i 和2i

與n3+n7相減
各得2a-2i 和 2a-3i

考慮i的範圍
if (0<=i<=2a/3)

2a-2i>=2a/3>=0
2a-3i>=0

---->發現沒屁用

if(2a/3<i<=a)

2a-2i>=0 輕 is n3
2a-3i<0 輕 is n7

---->似乎出現一絲曙光??

也就是說 如果 今天少掉的重量 有佔單一球的2/3
換句話說 就是較輕的那顆比一般球的1/3還要少
這情況下是有解的 所以如果出現負我們要很高興
代表答案出來了 而且 if and only if 輕球<=1/3a
最輕必為n7

但是如果是正的話?
很抱歉 我也想不到其他方法0.0
這是我目前想到的最佳解了...

除非他題目有規定 輕球<=a/3
我們才能用正負判斷


--