Re: [問題] 有關演算法的問題

[smallworld (路人系草包)]

記得這題是出自摳門的演算法導論

以前讀的時候碰到這題也是想不出

剛剛稍有斬獲 請大家看看這樣行不行


已知 好的大於一半

我的做法是

1. 任取一晶片插入A 其他一一與在A上的晶片測試 如果不是兩者都說GOOD

就把B換掉 拿新的測 總之就是測到都出GOOD為止

2. 出現兩者皆說GOOD 就把兩片拿起來放一起 反覆1 最後晶片會兩兩成對

此時成對的對不管好壞 屬性都相同

3. 一對中 兩者擇一 與其他對擇一的晶片 進行1.步驟 把答案相同者 再放一起

反覆到最後剩兩堆 由已知 多的那堆是好的 少的那堆是壞的


共做O(logN)次

※ 引述《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      至少一個是壞的
: 現在有個問題
: 找出一個方法可以測試出好的晶片 並且說明測試的次數

--
拙僧の肉棒を試させろ

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.165.4.40
→ neverfly:光是第一步就不只logN了
→ neverfly:第二步的時間還要乘上第一步的時間
→ neverfly:怎麼可能O(log N)做的掉
→ smallworld:打錯NlogN
→ neverfly:看起來也不像N log N，比這大多了