作者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