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

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

劉耀才(Liu Yao Tsai)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2004年)

摘要

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

關鍵字

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

並列摘要

The counterfeit coin problem is a well-known problem. There are some people who have tried to make the problem more challenging by adding some constraints for the problem. There are 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-cointerfeit coins problem with unknown weight、the 3-cointerfeit coins problem with known weight、the 3-cointerfeit coins problem with unknown weight、the 4-cointerfeit coins problem with known weight、the 4-cointerfeit coins problem with unknown weight. We also tackle the k-counterfeit coins problem with unknown weight by improving the algorithm proposed by Li-Jhong Li, in which he only dealed with the k-counterfeit coins problem with known weight, .
In addition, we provide the analyses of the algorithms for these counterfeit coins problems. According to the analyses, we will know the theoretical lower bound of the numbers of weightings to identify the counterfeit coins in a mass of coins. Thus, we will know which strategy of the problem might be further improved.

並列關鍵字

lower bound analysis ； the counterfeit coins problem ； trisection method

參考文獻

【10】李立中，多枚偽幣問題之演算法設計與分析，國立台灣大學資訊教育學研究所碩士論文，2000。

【1】A. Born, C. A. J. Hurkens, G. J. Woeginger, How to detect a counterfeit coin: Adaptive versus non-adaptive solutions, Elsevier Information Processing Letters, Vol.86, pp.137-141, 2003.

【2】A. D. Bonis, L. G., U. V. , Optimal detection of a countfeit coin with multi-arms balances, Elsevier Discrete Applied Mathmatics, Vol.61, pp.121-131, 1995.

【4】L. Halbeisen, N. Hungerbuhler, The general counterfeit coin problem, Elsevier Discrete Mathmatics, Vol.147, pp.139-150, 1995.

【5】P. J. Wan, D. Z. Du, A -competitive algorithm for counterfeit coin problem, Elsevier Discrete Mathematics, Vol.163, pp.173-200, 1997.