کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421496 | 684855 | 2010 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Searching for a counterfeit coin with b-balance
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 14, 1 September 2006, Pages 2010–2023
Journal: Discrete Applied Mathematics - Volume 154, Issue 14, 1 September 2006, Pages 2010–2023
نویسندگان
Wen An Liu, Huan Huan Cui, Bing Qing Ma,