僞幣問題之改良演算法設計與分析

The Designs and Analyses of Improved Algorithms for the Counterfeit Coins Problem

劉耀才(Yao-Tsai Liu) ； 林順喜(Shun-Shii Lin)

《電腦學刊》 17卷4期 (2007/01) Pp. 113-140

摘要

僞幣問題由來已久，有許多研究者考慮不同的條件，使得這個問題變得更具挑戰性也更加困難，也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的僞幣問題。在本論文中，我們對兩枚僞幣不知其輕重、三枚僞幣知其輕重、三枚僞幣不知其輕重、四枚僞幣知其輕重、四枚僞幣不知其輕重等問題提出了改良的演算法，以及改進了李立中的三枚以上僞幣知其輕重演算法，使之成爲三枚以上僞幣不知其輕重的演算法。在最後我們也對一枚僞幣知其輕重、一枚僞幣不知其輕重、兩枚僞幣不知其輕重、三枚僞幣知其輕重、三枚僞幣不知其輕重、四枚僞幣知其輕重、四枚僞幣不知其輕重等問題，提出了分析，說明各個演算法相對於理論下限還有多少可以努力的空間。

關鍵字

下限分析 ； 僞幣問題 ； 三分法

並列摘要

The counterfeit coin problem is a well-known problem. Many researchers have tried to make the problem more challenging by considering some constraints for the problem. There were also a lot of researchers presenting different algorithms for variants of the problem. In this paper, we propose some improved algorithms and strategies to solve some kinds of the counterfeit coin problems, including the 2-counterfeit coins problem with unknown weights, the 3-counterfeit coins problem with known weights, the 3-counterfeit coins problem with unknown weights, the 4-counterfeit coins problem with known weights, the 4-counterfeit coins problem with unknown weights. We also tackle the k-counterfeit coins problem with unknown weights by improving the algorithm proposed by Li-Jhong Li, in which he only dealt with the k-counterfeit coins problem with known weights. In addition, we provide the analyses of the algorithms for these counterfeit coins problems. According to the analyses, we know the theoretical lower bound of the numbers of weightings to identify the counterfeit coins in a mass of coins. Thus, we can know which strategy of the problem might be further improved.

並列關鍵字

Lower bound analysis ； The counterfeit coins problem ； Trisection method