作者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