数学
很经典的芯片测试题,当智力测试做一做吧.芯片测试:有2k块芯片,已知好芯片比坏芯片多.请设计算法从其中找出一片 好芯片,说明你所用的比较次数上限.其中:好芯片和其它芯片比较时,能正确给出另一块芯片是好还是坏. 坏芯片和其它芯片比较时,会随机的给出好或是坏.善良的本人已经找来答案了:两块芯片比较,结果可能是(好好),(好坏),(坏坏).如果结果是(好好),则可能是两块好芯片,也可能是两块坏芯片.如果结果是(好坏)或者(坏坏),则两块芯片中至少有一块是坏的.1. 将2k块芯片分成k组,每组两个比较.如果结果是

2019-04-19

很经典的芯片测试题,当智力测试做一做吧.
芯片测试:有2k块芯片,已知好芯片比坏芯片多.请设计算法从其中找出一片
好芯片,说明你所用的比较次数上限.
其中:好芯片和其它芯片比较时,能正确给出另一块芯片是好还是坏.
坏芯片和其它芯片比较时,会随机的给出好或是坏.
善良的本人已经找来答案了:
两块芯片比较,结果可能是(好好),(好坏),(坏坏).如果结果是(好好),则可能是两块好芯片,也可能是两块坏芯片.如果结果是(好坏)或者(坏坏),则两块芯片中至少有一块是坏的.
1. 将2k块芯片分成k组,每组两个比较.如果结果是(好坏)或者(坏坏),则把两块芯片都去掉;如果结果是(好好),则任选其中一块去掉.可以保证剩下好芯片比坏芯片多.
2. 如果剩下1个或2个,则可以判断这些是好芯片.
3. 如果剩下偶数个,则回到第1步.
4. 如果剩下奇数个,则任取一个和其它所有芯片比较,如果有一半将此芯片判为好芯片,则说明此芯片为好芯片,测试结束;否则,说明此芯片为坏芯片,去掉此芯片(当然还可以去掉将此芯片判为好芯片的芯片)后总芯片数为偶数,回到第1步.
考虑最坏的情况:
第1次,进行k次比较,可以使芯片数减半;
第2次,k为奇数,则需要进行k-1次比较,使芯片数减为k-1.
第3次,通过(k-1)/ 2次比较可以使芯片数减为 (k-1)/2.
第4次,(k-1)/2为奇数,需要(k-1)/2 - 1次比较
第5次,需要 ((k-1)/2 - 1)/2次比较
..
所以最多4k次比较.
下面,求解释.有哪位能帮俺解释清楚?以上解答是正确的吗?几乎步步欠推导啊!
优质解答
感觉答案没问题呀 LZ哪里不清楚?
解释下答案第一步 所做之后为什么好芯片依旧比坏芯片多吧:
假设有m个好芯片 n个坏芯片 (m>n)
两两比较只有三种情况 好好比较 好坏比较 坏坏比较
假设有a个好芯片与a个坏芯片进行的好坏比较 那么剩下的芯片都是好好 或 坏坏比较:
好坏比较的结果不是 好坏 就是 坏坏 肯定这2a个芯片都被弃掉了
好好比较的芯片弃掉了一半 则好芯片剩余个数:m'=(m-a)/2
坏坏比较的芯片至少弃掉一半(根据规则 2个芯片比较要么弃掉1个 要么弃掉2个)
所以坏芯片剩余个数:n'
感觉答案没问题呀 LZ哪里不清楚?
解释下答案第一步 所做之后为什么好芯片依旧比坏芯片多吧:
假设有m个好芯片 n个坏芯片 (m>n)
两两比较只有三种情况 好好比较 好坏比较 坏坏比较
假设有a个好芯片与a个坏芯片进行的好坏比较 那么剩下的芯片都是好好 或 坏坏比较:
好坏比较的结果不是 好坏 就是 坏坏 肯定这2a个芯片都被弃掉了
好好比较的芯片弃掉了一半 则好芯片剩余个数:m'=(m-a)/2
坏坏比较的芯片至少弃掉一半(根据规则 2个芯片比较要么弃掉1个 要么弃掉2个)
所以坏芯片剩余个数:n'
相关问答