| 伪币鉴定问题的一个改进算法 |
| |
| 引用本文： | 杨启帆.伪币鉴定问题的一个改进算法[J].浙江大学学报(自然科学版 ),1997,31(4):512-517. |
| |
| 作者姓名： | 杨启帆 |
| |
| 作者单位： | 浙江大学数学系 |
| |
| 摘 要： | 本文研究如下的伪币鉴定问题：设有ｎ枚硬币，其中隐藏着若干枚伪币．真币具有相同重量，伪币也具有相同重量，但真币与伪币重量不同．问题要求利用一台没有法码的天平，在最少或尽可能少次数的测试后将真伪币一一区分出来．Ｘ．Ｄ．Ｈｕ和Ｆ．Ｋ．Ｈｗａｎｇ［１］［２］等人研究了这一问题，提出了一些两分算法．本文基于一种新的逐次成倍扩展搜索技巧，构造了一个改进算法．根据测试次数分析，即使在最不顺利的情况下，我们的算法也能使用更少的测试次数，从而大大节省了测试的时间与经费．
|
| 关 键 词： | 伪币鉴定问题 两分算法 逐次成倍扩展搜索 |
An improved algorithm for counterfeit coin problem |
| |
| Yang Qifan.An improved algorithm for counterfeit coin problem[J].Journal of Zhejiang University(Engineering Science),1997,31(4):512-517. |
| |
| Authors: | Yang Qifan |
| |
| Abstract: | This paper is concerned with the problem of detecting d defective coins mixed with n-d standard weight coins. Every defective coin is lighter(of heavier) than the standard one. The goal is to sort them according to werght with a minimum number of weighings on a balance scale. X.D.Hu and F.K.Hwang gave an algorithm for solving this problem. In this paper,we present an improved algorithm and show that our algorithm takes less weighings in worst cases. |
| |
| Keywords: | counterfeit coin problem binary algorithm doubling search steps |
| 本文献已被 CNKI 维普 等数据库收录！ |
