伪币鉴定问题的一个改进算法

本文研究如下的伪币鉴定问题：设有ｎ枚硬币，其中隐藏着若干枚伪币．真币具有相同重量，伪币也具有相同重量，但真币与伪币重量不同．问题要求利用一台没有法码的天平，在最少或尽可能少次数的测试后将真伪币一一区分出来．Ｘ．Ｄ．Ｈｕ和Ｆ．Ｋ．Ｈｗａｎｇ［１］［２］等人研究了这一问题，提出了一些两分算法．本文基于一种新的逐次成倍扩展搜索技巧，构造了一个改进算法．根据测试次数分析，即使在最不顺利的情况下，我们的算法也能使用更少的测试次数，从而大大节省了测试的时间与经费．