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