Name
Abstract | ||
|---|---|---|
We consider the classical problem of searching for a heavier coin in a set of n coins, n - 1 of which have the same weight. The weighing device is b-balance which is the generalization of two-arms balance. The minimum numbers of weighings are determined exactly for worst-case sequential algorithm, average-case sequential algorithm, worst-case predetermined algorithm, average-case predetermined algorithm.We also investigate the above search model with additional constraint: each weighing is only allowed to use the coins that are still in doubt. We present a worst-case optimal sequential algorithm and an average-case optimal sequential algorithm requiring the minimum numbers of weighings. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2006.03.010 | Discrete Applied Mathematics |
Keywords | Field | DocType |
two-arms balance,search model,b -balance,search,average-case,minimum number,counterfeit coin,classical problem,worst-case optimal sequential algorithm,worst-case sequential algorithm,average-case sequential algorithm,additional constraint,worst-case,n coin,heavier coin | Algorithm,Counterfeit,Sequential algorithm,Group testing,Mathematics | Journal |
Volume | Issue | ISSN |
154 | 14 | Discrete Applied Mathematics |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wen An Liu | 1 | 65 | 12.61 |
| Huan Huan Cui | 2 | 0 | 0.34 |
| Bing Qing Ma | 3 | 0 | 0.34 |