作者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/m.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