Re: [問題] 有關演算法的問題
※ 引述《LPH66 (IWH68S0XZ8M89)》之銘言：
: ※ 引述《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
: 那麼多的那組就都是好的 少的那組就都是壞的
可是問題是 A 壞 未必一定會回報錯的答案呀.
原文只是說: 不可信 而已
可能它是壞的, 但仍然回報正確答案.
所以我覺得無解... 一個壞了的東西仍然可以
回報正確答案... 除非問題改為:
但是如果是壞的 則結果是錯誤的
那才有得玩吧
alien
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.155.236.82
→
04/03 19:00, , 1F
04/03 19:00, 1F
→
04/03 19:01, , 2F
04/03 19:01, 2F
→
04/03 19:49, , 3F
04/03 19:49, 3F
討論串 (同標題文章)