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 至少一個是壞的
: 現在有個問題
: 找出一個方法可以測試出好的晶片 並且說明測試的次數
有點舊的話題
這兩天突然想到一個方法, 不知會不會比較有效率一點?
重點在於 好的 比 壞的 多
隨便從晶片裡抽一個出來, 和剩下的逐一比對.
只要有其中一個報告 bad, 則這對拿起來放在一邊.
然後在晶片堆拿下一個, 繼續做.
直到有一顆晶片, 和其他剩下的所有晶片檢查結果都是
good. 這時, 剩下的所有晶片都是都是好的.
再用這些好的晶片來檢查之前放在一邊的那堆就好了.
這方法一定要肯定好的比壞的多才能成立
alien
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.78.81.71
→
04/16 00:44, , 1F
04/16 00:44, 1F
討論串 (同標題文章)