« 前一篇:一句话
后一篇:章太炎:《国学演讲录》 »

据说是GOOGLE笔试题 @ 11/24/2005

唧歪类
芯片测试:有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);
    }
}
发布于 11/24/2005 11:44:22 | 评论:10
csh @ 11/24/2005 13:51:54
kaka,

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

吴雨 @ 11/24/2005 13:59:04
你那要比较多少次啊??
csh @ 11/24/2005 14:04:01
while那里写的有点问题
不过比的次数不超过4k-1
csh @ 11/24/2005 14:09:27
反正2个2个一组,如果测试完的结果都是对的就留下其中一个,否则都扔掉,把所有的组都测试完了剩下的在2个2个一组...,这样
mountebank @ 2/28/2006 15:37:18
将一次比较结果看作一个得分,判断为好得1分,为坏得-1
一个好芯片总是得正分
一个坏芯片总是的负分

这样最少用 1999 * 2 次

最多可能要用 1999 + 1998 + 。。。。 + 999次吧(没有细算)
tmy @ 9/30/2006 17:44:37
    楼主的有漏洞吧 .
    上楼的可行,相当于投票选举主席.比如1001块好,999块差(这是最坏情况);用其余1999块来表决1块,如果被表决的是好的,则值最小为1,如果被表决的是坏的,则值最大为-1.这样用1999次可100%断定一块芯片好坏,最少就是用1999次.
如果选出好的可结束,否则仍在剩下的没被100%确定块中选一个作被选举对象,其余的1999(仍包括被判为坏的)块来选举,直到选出好的为止.假设有n 个坏的,则最多进行1999*n次(n 轮仍没选出,则因为判定了n 个是坏的,剩下的则全是好的了).  为加速循环,可用被选举的与已经判定为坏的作比较,若结果为好,则立即可断定被选举者是坏的了,因为好芯片不可能把坏芯片断定为好芯片.
tmy @ 9/30/2006 17:54:07
因为n 事先也不知道,n 最大为999,上限为1999*999次
tmy @ 9/30/2006 18:13:59
呵呵,仔细想了,若被选取者没选上,可开除其选举权,mountbank的最多是正确的
cfh @ 10/11/2006 15:40:51
1.我们先初始化两个块堆,初始的测试堆一,以及后来用来存放移出去的块的堆二。从堆一中选出一块芯片用作比较块。
2.用被选中芯片A与该堆中其它块之一B相比较,(1)如果A已经和堆一中所有的块作了比较,则A就是一块好的芯片;(2)如果比较结果是坏的,则继续将块A与其它块相比较;(3)如果结果是好的,再用被判定为好的块B与A块相比较,如果结果为A是好的,则将块B移到堆二中,继续用A块与其它块相比较,如果结果为A是坏的,则将块A移到堆二中,并选取B块为新的比较块。转到2。

其最佳情况是芯片中好的个数减一再乘以2再加上坏的个数。
在最坏情况下,其比较次数比较难于计算。
cfh @ 10/11/2006 15:47:38
我前面说的算法存在一个问题是,可能判断的好的芯片实际上是错的,我再研究一下看能不能在此基础上再改进一下。呵呵

看帖要回帖...

categories
archives
links
statistics
  • 网志数:1168
  • 评论数:2011