,(这里所需化验次数是指在最坏情况下化验次数,如果碰巧,可能首先化验的10个人全是病人,10次化验就够了,下面讨论的化验次数均指在最坏情况下的化验次数)。为了减少化验次数,人们采用分组化验的办法,即把几个人的血样混在一起,先化验一次,若化验合格,则这几个人全部正常,若混合血样不合格,说明这几个人中有病人,再对它们重新化验(逐个化验或再分组化验)。试给出一种分组化验的方法使其化验次数尽可能地小,不超过1000次。解:解我们给出如下的方法:从1000人中任取64人,把他们的血样混合化验。一般地,n个人中有k个病人,令s使2s≤n/k<2s+1,则从n个人中任取25个人一组,当n=1000,k=10时,25=64若这64人混合血样合格(化验是阴性),则这64个人正常,可排除,无需再化验,再从剩下未化验的人中任取64个人,混合血样化验。若这64人混合血样不合格(化验呈阳性),说明这64人中有病人。把这64个人,分为两组,每组32人。任取一组的混合血化验,即可确定有病人的一组。(即只需化验-次,若化验的这组血样成阴性,则病人在另--组。若化验的这组血样成阳性,这组有病人,但此时,另-组也可能有病人)。作为最坏的可能情形,我们无法保证另-组的32人中没有病人,故选定有病。人的一组后,把另一组人退回到未化验的人群中去。把有病人的这组32人,再分为两组,每组16人,重复上述过程。即化验--次,确定有病人的一组,把另一组退回到未化验的人群中。依次下去,直到找到一个病人为止。至此一-共化验了7次。再从未化验的人中任取64人重复上述过程。总之,对每次64人混合血化验成阳性的,通过7次化验可找到1个病人,由于共有10个病人,因此,这样的情形,化验次数不超过7X10=70次。对每次64人混合血化验成阴性的,由于1000=15X64+40,化验次数不超过15次。故总的化验次数不超过70+15=85次。
全文预览
