两伪币的搜索问题

作者：武晓辉; 李胜家

来源：运筹学学报, 2016, 20(04): 102-108.

DOI：10.15960/j.cnki.issn.1007-6093.2016.04.012

• 组合搜索
• 组测试
• 称重问题
• 两伪币

考虑两伪币的搜索问题:给定外观相同的n个硬币,其中有两个比较重的伪币,通过等臂天平在尽可能少的称量次数下去找出两个伪币.L~((2))(n)为最坏情况下找到两伪币的最小称量步数.对于任意的n≥2,满足log3(2n)]≤L~((2))(n)≤[log3(2n)]+1.猜想信息理论下界均可达.通过一个新的方法扩大了满足信息理论下界的n的取值范围.

• 单位
  山西大学