※ 引述《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)