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

The Design and Analysis of Algorithm for the Counterfeit Coins Problem

李立中(Li-Chung Lee)

指導教授 ： 林順喜

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2001年)

摘要

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

關鍵字

演算法 ； 偽幣問題 ； 三分法 ； 三元決策樹 ； 二值排序 ； 錯誤偵測 ； 錯誤更正

並列摘要

無資料

並列關鍵字

algorithm ； the counterfeit coins problem ； trisection ； ternary decision tree ； 2-value sorting ； error detection ； error correction

參考文獻

【2】 V. Auletta, A. Negro, G. Parlati, Solution of Ulam's problem on binary search with four lies,http://citeseer.nj.nec.com/auletta93solution.html, 1993.

【3】 A. D. Bonis, L. Gargano, U. Vaccaro, Group testing with unreliable tests. Information Science, Vol. 96, No.1& 2, pp 1-14, 1997.

【4】 A. D. Bonis, L. Gargano, Optimal detection of a counterfeit coin with multi-arms balances. Research and Computer Science, Vol. 61, pp.121-131, 1995.

【5】 J. L. Bernier et al, Solving Mastermind using gas and simulated annealing: a case of dynamic constraint optimization. Proceedings PPSN, Parallel Problem Solving from Nature IV. Computer Science 1141, pp. 554-563, 1996.

【6】 Z. Chen et al, Finding a hidden code by asking questions, COCOON’96, Computing and Combinatorics, pp. 50-55, 1996.