应用数学
應用數學
응용수학
MATHEMATICA APPLICATA
2005年
3期
345-351
,共7页
伪硬币%最优分组测试过程%信息论界%分组测试%标准硬币
偽硬幣%最優分組測試過程%信息論界%分組測試%標準硬幣
위경폐%최우분조측시과정%신식론계%분조측시%표준경폐
Defective coin%Optimal group testing procedure%Information-theoretic bound%Group testing%Standard coin
下面的问题被称为n个外观不可区分硬币的分组测试问题,每个硬币可以是伪硬币或是标准硬币.本文所涉及的问题是:已知一个由n个硬币组成的集合中有两个伪(较重的)硬币,用一台天平以最小的称重次数,从这n个硬币组成的集合中探测出两个伪(较重的)硬币.我们构造了找出两个伪(较重的)硬币的两个算法,并且这两个算法是最优的.
下麵的問題被稱為n箇外觀不可區分硬幣的分組測試問題,每箇硬幣可以是偽硬幣或是標準硬幣.本文所涉及的問題是:已知一箇由n箇硬幣組成的集閤中有兩箇偽(較重的)硬幣,用一檯天平以最小的稱重次數,從這n箇硬幣組成的集閤中探測齣兩箇偽(較重的)硬幣.我們構造瞭找齣兩箇偽(較重的)硬幣的兩箇算法,併且這兩箇算法是最優的.
하면적문제피칭위n개외관불가구분경폐적분조측시문제,매개경폐가이시위경폐혹시표준경폐.본문소섭급적문제시:이지일개유n개경폐조성적집합중유량개위(교중적)경폐,용일태천평이최소적칭중차수,종저n개경폐조성적집합중탐측출량개위(교중적)경폐.아문구조료조출량개위(교중적)경폐적량개산법,병차저량개산법시최우적.
The following problem is known as group testing problem for n coins of the same appearance. Each coin can be defective or standard. We consider the problem of ascertaining the minimum number of weighing which suffice to determine the two defective (heavier) coins in a set of n coins given a balance scale and the information that there are exactly two heavier coins present. The two algorithm are constructed to find out the two heavier coins, and the two corresponding algorithm are optimal.