Re: [問題] 有關演算法的問題
※ 引述《dancs96 (山嵐)》之銘言:
: 有N個檢查晶片不確定好壞
: 但知道一定有一半以上是好的
: 在測試方式是 一個測試平台可以放兩個晶片 A B
: A會檢查B 而B會檢查A
: 如果晶片是好的
: 當它在測試平台上檢查的時候就會說 另一個是"good" 或是"bad"
: 而這個結果是完全可信的
: 但是如果是壞的 則結果是不可信的
: 也就是說 測試結果可用下表表示
: A B 可能結果
: _________________________________________________
: B good A good 兩個都是好的或是兩個都是壞的
: B good A bad 至少一個是壞的
: B bad A good 至少一個是壞的
: B bad A bad 至少一個是壞的
: 現在有個問題
: 找出一個方法可以測試出好的晶片 並且說明測試的次數
換個方式想
若A好B好 => A回報B good; B回報A good
A好B壞 => A回報B bad; B回報A bad
A壞B好 => A回報B bad; B回報A bad
A壞B壞 => A回報B good; B回報A good
所以其實只有兩種回答
依照這兩種回答把這N個分成兩組
其中同組的人都說對方是good 不同組的人都說對方是bad
那麼多的那組就都是好的 少的那組就都是壞的
--
總覺得這篇在Programming版是走錯了...
這比較像是在Math版的東西 XD
--
有人喜歡邊玩遊戲邊上逼;
也有人喜歡邊聽歌邊打字。
但是,我有個請求,
選字的時候請專心好嗎?
-- 改編自「古 火田 任三郎」之開場白
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
→
04/03 18:17, , 1F
04/03 18:17, 1F
討論串 (同標題文章)