Re: [問題] 8枚便士，7枚一樣重、1枚比較輕，你有1 …

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者AIdrifter (交錯地帶)時間14年前 (2011/07/15 21:09)推噓2(2推 0噓 3→)

留言5則, 2人參與討論串2/2 (看更多)

※ 引述《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