Re: [討論] 有人說這是微軟面試題目
: 請問大家怎麼解這個題目？
: 正常算法用因式分解去算為「五次」
: 但是題目感覺像是在問
: 「什麼方法可以在最短時間內找到」
: 所以是問最少次數？
: 有人用二分法 求得最少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
推
08/11 13:17, , 1F
08/11 13:17, 1F
→
08/11 13:17, , 2F
08/11 13:17, 2F
→
08/11 13:19, , 3F
08/11 13:19, 3F
→
08/11 13:26, , 4F
08/11 13:26, 4F
推
03/14 06:42, , 5F
03/14 06:42, 5F
→
03/14 06:42, , 6F
03/14 06:42, 6F
推
03/21 20:18, , 7F
03/21 20:18, 7F
→
05/29 19:02, , 8F
05/29 19:02, 8F
討論串 (同標題文章)
