作者pancake9237 (还记得我吗)
看板logic
标题Re: [讨论] 有人说这是微软面试题目
时间Tue Jun 27 16:47:01 2017
※ 引述《lovechin (大叔)》之铭言：
: 如题
: http://i.imgur.com/4Ro15EY.jpg
: 请问大家怎麽解这个题目？
: 正常算法用因式分解去算为「五次」
: 但是题目感觉像是在问
: 「什麽方法可以在最短时间内找到」
: 所以是问最少次数？
: 有人用二分法 求得最少2次 最多7次
: 讨论一下，以题目的文字叙述来看
: 两种答案都算对？
: 在此不考虑一个一个量，
: 因为题目已经有说了不能一个
: 首次发文有违反版规请告知修改
这题其实不难 , 因为有告诉你只有一个是9g , 其余是10g
就把所有的金币分三堆 : A B C
第一次秤随便拿两堆来秤一定可以拿到某一堆是掺有9g的金币
(假设A<B, 则A堆里有9g金币
B<A, 则B堆里有9g金币
A=B, 则C堆里有9g金币)
第二次秤一样再分三堆, 依此类推
所以162=2*3*3*3*3 , 因此需要5次
总结 2~3枚金币需要秤1次
4~9枚金币需要秤2次
10~27枚金币需要秤3次
28~81枚金币需要秤4次
82~243枚金币需要秤5次
依此类推....
题外话:这种题目的变化题是 不知金币的重量是重还是轻,
要找出那个差异的金币并知道是轻还是重
提供给大家参考!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.177.70.163
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/logic/M.1498553224.A.32E.html
1F：推 sendicmimic: 我认为分三堆去秤是一种文字漏洞， 08/11 13:17
2F：→ sendicmimic: 因为分三堆要秤的过程比分两堆去秤麻烦多了 08/11 13:17
3F：→ sendicmimic: 那我就把他分成162堆去秤，一次就秤完，但实际呢? 08/11 13:19
4F：→ sendicmimic: 当我没说吧，我没进入状况，抱歉。 08/11 13:26
5F：推 N100: 其实我也觉得，分三堆，应该算成『秤两次』，而不是『秤一 03/14 06:42
6F：→ N100: 次』 03/14 06:42
7F：推 dalconan: 这边的「秤」，指得一般是天秤，所以才说是秤一次吧 03/21 20:18
8F：→ howard91: 题目所说的秤应该是指磅秤，你的方法的秤是天秤 05/29 19:02