作者xam (听说)
站内Programming
标题Re: [问题] 有关演算法的问题
时间Thu Apr 3 20:24:56 2008
※ 引述《dancs96 (山岚)》之铭言：
: 有N个检查晶片不确定好坏
: 但知道一定有一半以上是好的
: 在测试方式是 一个测试平台可以放两个晶片 A B
: A会检查B 而B会检查A
: 如果晶片是好的
: 当它在测试平台上检查的时候就会说 另一个是"good" 或是"bad"
: 而这个结果是完全可信的
: 但是如果是坏的 则结果是不可信的
: 也就是说 测试结果可用下表表示
A B 可能结果
_________________________________________________
1. B good A good 两个都是好的或是两个都是坏的
2. B good A bad 至少一个是坏的
3. B bad A good 至少一个是坏的
4. B bad A bad 至少一个是坏的
: 现在有个问题
: 找出一个方法可以测试出好的晶片 并且说明测试的次数
总共有 N chips
先取任一个晶片 X
用 X 和其他 N-1 个晶片作测试, 依据结果分组, 可以得到四组晶片
{X1}, {X2}, {X3}, {X4} ps. n({X1})+n({X2})+n({X3})+n({X4}) = N-1
假设 X 是好的, 则 {X1} 可以相信都是好的;
假设 X 是坏的, 则 {X1} 可以相信都是坏的(X是坏的，你还说好，真的脑袋坏掉);
又保证晶片至少一半是好的, 所以:
If n({X1})+1 >= N/2 then
X+{X1} are good, {X2}+{X3}+{X4} are bad
end
else
X+{X1} are bad
把 X+{X1} 放一边, 再从剩下 {X2}+{X3}+{X4} 任取一个
重复前面的演算法
测试次数:
第一次 N-1 => N'
第二次 N'-n({X1}) => N'' n({X1})>=0
N''-
一直重复下去
就算前面每次都拿到坏的, 顶多跑 N/2 遍,
所以测试次数是 (N-1)+(N-2)+(N-3)+..... +([N/2])
这是我想到的, 不知道有没有漏了什麽
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.168.4.59
※ 编辑: xam 来自: 118.168.4.59 (04/03 20:33)
1F：→ xam:丢掉{X1}的时候, {X3} 好像也可以丢耶... 118.168.4.59 04/03 20:40