簡易檢索 / 詳目顯示
| 研究生： |
劉耀才 Liu Yao Tsai |
|---|---|
| 論文名稱： |
偽幣問題之改良演算法設計與分析 The Designs and Analyses of Improved Algorithms for the Counterfeit Coins Problem |
| 指導教授： | 林順喜 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2005 |
| 畢業學年度： | 93 |
| 語文別： | 中文 |
| 論文頁數： | 150 |
| 中文關鍵詞： | 下限分析 、偽幣問題 、三分法 |
| 英文關鍵詞： | lower bound analysis, the counterfeit coins problem, trisection method |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：252 下載：53 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
偽幣問題由來已久，有許多人不斷的增加不同的條件，使得這個問題變得更具挑戰性也更加困難，也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的偽幣問題。在本論文中，我們對兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題提出了改良的演算法，以及改進了李立中的三枚以上偽幣知其輕重演算法，使之成為三枚以上偽幣不知其輕重的演算法。在最後我們也對一枚偽幣知其輕重、一枚偽幣不知其輕重、兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題，提出了分析，說明各個演算法相對於理論下限還有多少可以努力的空間。
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.
【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.
【3】J. A. Pyrich, The counterfeit coin problem , http://www.97cc.com/~japyrich/ projects/coins.shtml, 2001.
【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.
【6】P. J. Wan, Q. Yang, D. Kelley, A -competitive algorithm for the counterfeit coin problem, Theoretical Computer Science, Vol.181, pp.347-356, 1997.
【7】W. A. Liu, Z. K. Nie, Optimal detection of two counterfeit coins with two-arms balance, Elsevier Discrete Applied Mathmatics, Vol.137, pp.267-291, 2004.
【8】W. Guzicki, Ulam's Searching Game with Two Lies, Journal of Combinatorial Theory, Ser A, Vol.54, pp.1-19, 1990.
【9】X. D. Hu, P. D. Chen, F. K. Hwang, A new competitive algorithm for the counterfeit coin problem, Information Processing Letters, Vol.51, pp.213-218, 1994.
【10】李立中，多枚偽幣問題之演算法設計與分析，國立台灣大學資訊教育學研究所碩士論文，2000。
【11】陳善泰，演繹競局及相關問題最佳化演算法之研究，國立台灣大學資訊教育學研究所博士論文，2004。
【12】楊錦潭、鄭又齊、馬德強、王授民合著，演算法的天空，pp.247-272，松崗書局，1989年6月初版。
【13】馬德強、陳國正，以歸納法處理偽幣問題，http://wwwedu.nknu.edu.tw/ 48552001/，2002。