Re: [討論] 有人說這是微軟面試題目

[pancake9237 (還記得我嗎)]

※ 引述《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://www.ptt.cc/bbs/logic/M.1498553224.A.32E.html
推 sendicmimic: 我認為分三堆去秤是一種文字漏洞，
→ sendicmimic: 因為分三堆要秤的過程比分兩堆去秤麻煩多了
→ sendicmimic: 那我就把他分成162堆去秤，一次就秤完，但實際呢?
→ sendicmimic: 當我沒說吧，我沒進入狀況，抱歉。
推 N100: 其實我也覺得，分三堆，應該算成『秤兩次』，而不是『秤一
→ N100: 次』
推 dalconan: 這邊的「秤」，指得一般是天秤，所以才說是秤一次吧
→ howard91: 題目所說的秤應該是指磅秤，你的方法的秤是天秤