请教：有难度的算法笔试题。

/*

个人觉得第三题是个概率题，得到的结果是否满足要求要看具体对芯片要求怎样。



现假设按照一般的小概率事件评判标准来：即小概率事件发生的概率<=0.3%。我们在实际生活中一般认为小概率事件是不可能发生的，即如果这个芯片出错的概率<=0.3%(当然可以按照具体要求调节该参数），那么我们就认为这是好芯片了。

再假设，坏的芯片测试其他芯片结果正确的概率为0.5，那么如果用坏的芯片A连续测试芯片B，10次结果都一样的概率为0.5的9次方，即0.20%，已经是小概率事件了。我们可以认为这种情况不可能发生，即A其实是好芯片（至少是满足约束条件的）。

基于上面的讨论，现给出算法如下：

*/

/**************************

1.从芯片堆中任取两块芯片，标记为A,B

2.用A测试B，如果发现B是好的，转步骤3，否则转步骤4

3.用A测试B，如果发现B是好的，判断：：（如果测试次数少于9次，循环步骤3，否则转步骤5），否则转步骤6

4.用A测试B，如果发现B是坏的，判断：：（如果测试次数少于9次，循环步骤4，否则转步骤5），否则转步骤6

5.A满足约束条件，可以当好芯片使。算法结束。

6.A满足坏芯片条件。（没找到好的不要紧，坏的也有用）转步骤7。

7.把B放回芯片堆，从该堆中999个芯片中任取一个出来，反复测试A，如果<=9次测试中发现存在一次测A的结果A是好芯片，那么这块芯片就可以认为是坏的，舍弃之，继续从998个芯片中任取一个出来，重复7，直到有一块芯片测试A时连续9次结果A是坏芯片，这块芯片就是要找的好芯片了。

**************************/

/*

粗略分析一下该算法的复杂度、可行性：

1、因为好芯片比坏芯片多，最坏情况下，501好芯片499坏芯片。那么随机抽样拿到坏芯片的概率约0.5，连续9次拿到坏芯片概率<0.3%,属于小概率事件。假设步骤1--6发现第一块A是坏芯片，则用了9次测试，再假设步骤7发生了小概率事件，即连续找到9个坏芯片，那么又用了最多9×9次测试，最后找到好芯片，又用了9次测试，所以总计9×11=99次测试。



2、现在撇开概率，看看其他情况：

   2.1 步骤5的所谓好芯片有一定概率是伪劣产品。虽然概率很低，但在仪器要求很高的地方，1/1000000的出错率都不能有！那么，极端情况测试总数将是（log0.5（p））×N,p是产品出错率，log0.5（p）对应上述情况中的参数9，具体可能是个较大的数如20，而N运气差的人可能会遇到两三百，从而比较次数从不到100升至成千上万。

   2.2 由步骤6确定的坏芯片是100%坏的，因此步骤7筛掉的坏芯片当然也是100%坏的，这倒是可以用来将成千上万的坏芯片挑出来处理掉。



*/



//有什么不当之处，欢迎大家提出指正！