硬币问题的一种新的通用算法的研究  

A new universal algorithm for coins problem

作　　者：代亮[1] 谢晓尧[2] 张仁津[1] 杨惠仁[3] 

机构地区：[1]贵州师范大学数学与计算机学院,贵阳550001 [2]贵州师范大学重点实验室,贵阳550001 [3]贵州商业高等专科学校,贵阳550001

出　　处：《制造业自动化》2012年第13期28-31,共4页Manufacturing Automation

基　　金：国家自然基金(41161065)

摘　　要：在图像压缩、模式识别、筛选等工业应用中提出了搜索坏硬币的最优化问题,即用尽可能少的测试次数检测出坏硬币并确定轻重。对这一问题,可采用AO*算法、遗传算法等国际通用算法求解,但这些算法的时间复杂度和空间复杂度过大。因此提出了一种新的解决此类问题的通用算法,并用C++将其实现和测试。测试结果表明:算法的时间、空间和成功率均达到了理论极限。

关 键 词：n-硬币问题 决策树 分组测试 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]