menu

秋梦无痕

一场秋雨无梦痕,春夜清风冻煞人。冬来冷水寒似铁,夏至京北蟑满城。

Avatar

据说是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再加上坏的个数。
在最坏情况下,其比较次数比较难于计算。

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

评论已关闭