据说是GOOGLE笔试题 / 秋梦无痕

据说是GOOGLE笔试题

芯片测试：有2k块芯片，已知好芯片比坏芯片多。请设计算法从其中找出一片好芯片，说明你所用的比较次数上限。

其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏。坏芯片和其它芯片比较时，会随机的给出好或是坏。

我的算法：（非标准答案，欢迎探讨）

取一个芯片：
1、用该芯片比较另一个芯片；
2、如果比较结果是坏的，就认为被比较芯片是坏的，放一边，用最后比较芯片比较另一个芯片，返回2；如果比较结果是好的，下一步；
3、用最后被比较芯片比较第一块芯片；
4、如果比较结果是坏的，就认为第一个芯片是坏的，所有被认为是好芯片的就都是坏的，放一边，返回1；如果比较是好的，而且还有芯片可测，用最后被比较芯片比较另一个芯片，返回2，如果没有芯片可比较，下一步。
5、认为第一个芯片是好的(他测出来的也都是好的)。

假设坏芯片为n个，则：
最好情况：需要测 n + 2 * (1999 - n)次。
最坏情况：一共需要 n + 2 * 1999次。

应csh要求，写成伪码：

list<chip*> total, bad, good;
chip* ca, cb, cc;
read_all(&total);
ca = total.removeHead();
good.appendTail(ca);
while(!total.isEmpty()) {
cb = good.getTail();
cc = total.removeHead();
if(cb->Check(cc)) {
if(cc->Check(ca)) {
good.appendTail(cc);
} else {
//如果需要全部的好芯片
//total.append(bad);
//bad.clear();
bad.append(good);
good.clear();
good.appendTail(cc);
ca = cc;
}
} else {
bad.appendTail(cc);
}
}

kaka,


m = 2*k;
i = floor(m/2);
[b]collection[/b] = the 2k chips;
while(i>3){
[i]fetch two chips from the [b]collection[/b][/i];
[i]use the two check each other[/i];
[i]if the results are both 'good',keep one of the two,or else drop the two[/i];
[i][b]collection[/b] = the rest chips[/i]
i = number of [b]collection[/b];
}
if (i=3){
...
}else{
...
}

你那要比较多少次啊？？

while那里写的有点问题
不过比的次数不超过4k-1

反正2个2个一组，如果测试完的结果都是对的就留下其中一个，否则都扔掉，把所有的组都测试完了剩下的在2个2个一组...，这样

将一次比较结果看作一个得分，判断为好得1分，为坏得-1
一个好芯片总是得正分
一个坏芯片总是的负分

这样最少用 1999 * 2 次

最多可能要用 1999 + 1998 + 。。。。 + 999次吧（没有细算）

楼主的有漏洞吧 .
上楼的可行,相当于投票选举主席.比如1001块好,999块差(这是最坏情况);用其余1999块来表决1块,如果被表决的是好的,则值最小为1,如果被表决的是坏的,则值最大为-1.这样用1999次可100%断定一块芯片好坏,最少就是用1999次.
如果选出好的可结束,否则仍在剩下的没被100%确定块中选一个作被选举对象,其余的1999(仍包括被判为坏的)块来选举,直到选出好的为止.假设有n 个坏的,则最多进行1999*n次(n 轮仍没选出,则因为判定了n 个是坏的,剩下的则全是好的了). 为加速循环,可用被选举的与已经判定为坏的作比较,若结果为好,则立即可断定被选举者是坏的了,因为好芯片不可能把坏芯片断定为好芯片.

因为n 事先也不知道,n 最大为999,上限为1999*999次

呵呵,仔细想了,若被选取者没选上,可开除其选举权,mountbank的最多是正确的

1.我们先初始化两个块堆，初始的测试堆一，以及后来用来存放移出去的块的堆二。从堆一中选出一块芯片用作比较块。
2.用被选中芯片A与该堆中其它块之一B相比较，(1)如果A已经和堆一中所有的块作了比较，则A就是一块好的芯片；(2)如果比较结果是坏的，则继续将块A与其它块相比较；(3)如果结果是好的，再用被判定为好的块B与A块相比较，如果结果为A是好的，则将块B移到堆二中，继续用A块与其它块相比较，如果结果为A是坏的，则将块A移到堆二中，并选取B块为新的比较块。转到2。

其最佳情况是芯片中好的个数减一再乘以2再加上坏的个数。
在最坏情况下，其比较次数比较难于计算。

我前面说的算法存在一个问题是，可能判断的好的芯片实际上是错的，我再研究一下看能不能在此基础上再改进一下。呵呵

评论已关闭