Re: [問卦] 解一題數學....在線等...已回收
※ 引述《Phoenix723 (操場旁的含羞草)》之銘言：
: 我的尼哥甲老板剛剛問了一題數學
: 一座孤島上有12個人
: 只有11個人體重一樣
: 只有一個翹翹板可以使用
: 但是只能測試3次就要把體重不同的人找出來
: 獎品是畢昂絲的演唱會門票
: 很想贏
: 在線等
演算法考慮最壞情況下 第一次絕對是44 因為可能的答案總共有24種
每一次測量結果不管為 (左重,左輕,平)
都要盡可能平均才測得出來
譬如說第一次66的話 假設左邊較重 就有12種可能情形
但剩下兩次測量只能有9種測量結果 不足以對應出12種這麼多
歸納以上思維後 假設12人編號為1234 5678 abcd
直接說結論 最佳解應為
1234 - 5678
125a - 34bc
136b - 47cd
為什麼是最佳解 因為它不用管之前的測試結果 三次可以一起測
NOTE. 譬如說若結果為(左重,左重,左重) 則答案為1號較重
若(右重,右重,右重) 則1號較輕 其他情況可以自行細想
群試(Pooling test/design)問題起源自血液篩檢
情境：時值二次大戰 想在眾多役男中找出梅毒帶原者
你不可能慢慢等每次的報告結果 一定是希望抽血後分送不同的中心化驗
而早期篩檢費用昂貴 也就有了測驗次數的限制
現代問題還會加入篩檢結果出錯的機率 讓理論越趨貼近實際情形
延伸問題:
1. 若題目改為13個人 則無法在三次測出 (即使可能答案有26種 < 27)
2. 若題目改為14個人但其中一人確定正常 則可以在三次測出
有興趣的話可以把它想到透徹
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.13.253.145
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1543686623.A.C5D.html
推
12/02 01:52,
7年前
, 1F
12/02 01:52, 1F
推
12/02 01:52,
7年前
, 2F
12/02 01:52, 2F
推
12/02 02:00,
7年前
, 3F
12/02 02:00, 3F
→
12/02 02:05,
7年前
, 4F
12/02 02:05, 4F
→
12/02 02:06,
7年前
, 5F
12/02 02:06, 5F
→
12/02 02:20,
7年前
, 6F
12/02 02:20, 6F
→
12/02 02:20,
7年前
, 7F
12/02 02:20, 7F
→
12/02 02:21,
7年前
, 8F
12/02 02:21, 8F
→
12/02 02:21,
7年前
, 9F
12/02 02:21, 9F
→
12/02 02:24,
7年前
, 10F
12/02 02:24, 10F
→
12/02 02:25,
7年前
, 11F
12/02 02:25, 11F
→
12/02 02:31,
7年前
, 12F
12/02 02:31, 12F
→
12/02 02:32,
7年前
, 13F
12/02 02:32, 13F
→
12/02 02:35,
7年前
, 14F
12/02 02:35, 14F
推
12/03 16:51,
7年前
, 15F
12/03 16:51, 15F
討論串 (同標題文章)
完整討論串 (本文為第 14 之 21 篇)：
