作者adrianshum (Alien)
看板Programming
标题Re: [问题] 有关演算法的问题
时间Thu Apr 3 18:51:41 2008
※ 引述《LPH66 (IWH68S0XZ8M89)》之铭言：
: ※ 引述《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 至少一个是坏的
: : 现在有个问题
: : 找出一个方法可以测试出好的晶片 并且说明测试的次数
: 换个方式想
: 若A好B好 => A回报B good; B回报A good
: A好B坏 => A回报B bad; B回报A bad
: A坏B好 => A回报B bad; B回报A bad
: A坏B坏 => A回报B good; B回报A good
: 所以其实只有两种回答
: 依照这两种回答把这N个分成两组
: 其中同组的人都说对方是good 不同组的人都说对方是bad
: 那麽多的那组就都是好的 少的那组就都是坏的
可是问题是 A 坏 未必一定会回报错的答案呀.
原文只是说: 不可信 而已
可能它是坏的, 但仍然回报正确答案.
所以我觉得无解... 一个坏了的东西仍然可以
回报正确答案... 除非问题改为:
但是如果是坏的 则结果是错误的
那才有得玩吧
alien
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 202.155.236.82
1F：→ LPH66:也是啦 不过如你说的这样解释就无解了 140.112.30.84 04/03 19:00
2F：→ LPH66:所以我才先用这个解释解题 140.112.30.84 04/03 19:01
3F：→ xam:要不可信才会变成问题啊 118.168.4.59 04/03 19:49