Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421496 | Discrete Applied Mathematics | 2010 | 14 Pages |
Abstract
We consider the classical problem of searching for a heavier coin in a set of n coins, n-1n-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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wen An Liu, Huan Huan Cui, Bing Qing Ma,