作者smallworld (路人系草包)
看板Programming
标题Re: [问题] 有关演算法的问题
时间Thu Apr 3 22:11:39 2008
记得这题是出自抠门的演算法导论
以前读的时候碰到这题也是想不出
刚刚稍有斩获 请大家看看这样行不行
已知 好的大於一半
我的做法是
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
1F：→ neverfly:光是第一步就不只logN了 163.22.21.113 04/07 18:27
2F：→ neverfly:第二步的时间还要乘上第一步的时间 163.22.21.113 04/07 18:27
3F：→ neverfly:怎麽可能O(log N)做的掉 163.22.21.113 04/07 18:28
4F：→ smallworld:打错NlogN 123.193.83.210 04/11 22:43
5F：→ neverfly:看起来也不像N log N，比这大多了 125.231.4.198 04/15 15:03