摘要
研究以b个天平为试验装置,如何用最少的试验次数从n个硬币中识别出所含的唯一轻币的并行搜索模型.这是对试验装置为一个天平的推广.论文构造出具有最少试验次数的最坏情况序列算法以及最坏情况预确定算法.此外研究了两个相关的模型,得到了精确的最少试验次数.
The following parallel search model is studied: How to identify the only one light coin from a set of n coins by using the minimal number of tests when the test devices are b balances. This model is the generalization of one balance. We establish the worst-case sequential and predetermined algorithms with the minimal number of tests. Meanwhile, two relative models are also studied, the exact results on the minimal number of tests are determined for both models.
出处
《河南师范大学学报(自然科学版)》
CAS
CSCD
北大核心
2006年第3期211-214,共4页
Journal of Henan Normal University(Natural Science Edition)
基金
国家自然科学基金(1057104570571024)
关键词
搜索
b个天平
最坏情况
序列算法
预确定算法
search
b balances
worst-case
sequential algorithm
predetermined algorithm