※ 引述《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 我們才能用正負判斷 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.163.1.63