作者AIdrifter (交错地带)
看板Math
标题[其他] 用电子秤分出8枚便士中较轻的一个~
时间Sun Jul 3 02:11:51 2011
英特尔在面试系统验证工程师:
你有8枚便士，7枚一样重、1枚比较轻，你有1个【秤】，
你要如何在3次机会中找出那个最轻的？
note:所谓的秤 就像体重计一样 只能量重量而已
不是像天平一样有2边喔~
小弟的想法如下 不知道正不正确 希望版友给些意见 谢谢:)
假定球序号为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：推 wree45 :第一次左右各放4个 重的那边拿下 第2次把第一次留着 07/03 12:47
2F：→ wree45 :的4个 各分配到两边 一样重的拿下 07/03 12:47
3F：→ wree45 :第三次类推 07/03 12:48
4F：→ wree45 :不对不是天秤! 07/03 12:48
5F：→ wree45 :以上 别理我... 07/03 12:49
6F：推 ioriblood :目前只算出七个~~八个还在努力= = 07/04 10:11
7F：→ ownlai :我的想法跟你前面完全一样 然後最後一步就卡住 07/04 13:01
8F：→ ownlai :而你最後一步我觉得是错的 那单颗重量并非绝对正确 07/04 13:02