多枚偽幣問題之演算法設計與分析

Abstract

偽幣問題由來已久，有許多人不斷的增加不同的條件，使得這個問題變得更具挑戰性也更加困難，也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的偽幣問題。而我們在本論文中便針對2枚偽幣，但是不知道偽幣輕重的問題，以及3枚以上知道輕重的偽幣問題提出了演算法。並且分析出這些演算法保證能秤量出一堆硬幣中特定個數的偽幣，其所需要的最大稱量次數。而在最後則針對1枚偽幣知道輕重、1枚偽幣不知輕重、2枚偽幣知道輕重、2枚偽幣不知輕重、3枚以上知道輕重等問題，提出了分析，說明哪些問題所被提出的演算法已經達到理論值下限，哪些問題所被提出的演算法則還有努力的空間。

The counterfeit coin problem is a well-known problem. There are some people who have tried to make the problem more challenging by adding more constraints on the problem. There are also a lot of people presenting different algorithms for variants of the problem. In this paper, we will propose some algorithms and strategies to solve some sort of the counterfeit coin problems, including the 2-counterfeit coins problem with unknown weight, and the k-counterfeit coins with known weight, where k  3. In addition, we will provide the analysis of the algorithms for these counterfeit coins problems. According to the analysis, we will know the theoretical lower bound of the numbers of the weighting when we are looking for the counterfeit coins in a mass of coins. Thus, we will know which strategy of the problem might be further improved.