Re: [請益] 某公司面試題目@@
※ 引述《PaulOnei11 (PTT改革派創始人)》之銘言：
: ※ 引述《papau (千ちゃん大好き )》之銘言：
: : 1.有8本書，其中一本較重，你只有天枰一個工具，請問你要秤幾次?
: : 怎麼秤才能找出較重的那本書?
: 用二分法
: 假設較重的那本書為A
: 先將8本書各以4本為一組分別放在天枰兩端去秤
: 而這兩組較重的那四本其中一本即為A
: 再用較重的這四本分成兩本為一組分別放在天枰兩端去秤
: 而這兩組較重的那兩本其中一本即為A
: 最後只要再來比秤這兩本哪一本較重
: 較重的那本即為A
: 因此總共是秤了三次
: 較簡單的算式就是8=2^3，所以是三次
如果 1~8 本書，除了一本比較重，其他重量相同的話
則前面已經提過，不斷分三份的方法是最少次數的
in this case 只需要測量兩次
123 456 78 <= 分成三份
1)
123 ___ 456 2)
|
若 123 比較重，則秤 1 與 2，平衡則是 3 比較重
若 456 比較重，則秤 4 與 5，平衡則是 6 比較重
若 123 與 456 平衡，秤 7 與 8 則可得知答案
如果 1~8 本書重量均不一定相同，需測量出最重的
則是像冠軍賽一樣，1 vs 2 比較輕的淘汰 .. vs 3 比較輕的淘汰 .. vs 4 ......
等於七次
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.14.246
※ 編輯: ttcat0902 來自: 220.135.14.246 (08/19 03:04)
推
09/06 17:49, , 1F
09/06 17:49, 1F
討論串 (同標題文章)