臺灣博碩士論文加值系統

偽幣問題由來已久，有許多人不斷的增加不同的條件，使得這個問題變得更具挑戰性也更加困難，也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的偽幣問題。而我們在本論文中便針對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.

目錄
附圖目錄 iii
附表目錄 iv
第一章 簡介 1
第二章 研究背景及目的 3
第一節 研究背景 3
第二節 一般化問題的相關研究 4
第三節 一枚偽幣問題的相關研究 6
第四節 2枚偽幣且知道輕重問題的相關研究 7
第五節 2枚以上偽幣問題的其它相關研究 11
第三章 我們提出的方法─交錯秤量法 12
第一節 二枚偽幣不知輕重的交錯秤量法 12
第二節 三枚以上知道輕重的偽幣問題之演算法 26
第四章 各演算法與理論最佳解分析 38
第一節 找出一枚已知輕重偽幣的秤量次數之理論值 38
第二節 找出一枚不知輕重偽幣的秤量次數之理論值 41
第三節 找出二枚已知輕重偽幣的秤量次數之理論值 43
第四節 找出二枚不知輕重偽幣的秤量次數之理論值 44
第五節 找出三枚以上不知輕重偽幣的秤量次數之理論值 45
第五章 結論 47
參考文獻 49
附圖目錄
圖2-1、Pyrich的演算法 8
圖3-1、交錯秤量法─以5枚硬幣為例 15
圖3-2、交錯秤量法各硬幣集合關係示意圖（假設n為12之倍數） 16
圖3-3、交錯秤量法流程圖 19
圖3-4、交錯秤量法─以11枚硬幣為例 25
圖3-5、找出3枚以上已知輕重偽幣之演算法Find 31
圖4-1、秤量偽幣的三元決策樹示意圖 40
附表目錄
表2-1、||A|| = ||B||的偽幣分布情形 ..9
表2-2、||A|| > ||B||的偽幣分布情形 ..9
表2-3、||A|| = ||B|情況下再秤量A和C的偽幣分布情形之一 10
表2-4、||A|| = ||B|情況下再秤量A和C的偽幣分布情形之二 10
表2-5、||A|| > ||B|情況下再秤量A和C的偽幣分布情形 10
表3-1、n枚硬幣在分堆時每一集合的大小 17
表3-2、||S1|| = ||S2||的偽幣可能分布情況 27
表3-3、||S1|| > ||S2||的偽幣可能分布情況 27
表3-4、||S1|| < ||S2||的偽幣可能分布情況 28
表3-5、||S1|| = ||S2||的偽幣可能分布情況 29
表3-6、||S1|| < ||S2||的偽幣可能分布情況 29
表3-7、||S1|| > ||S2||的偽幣可能分布情況 29
表3-8、||s1~s9|| = || s10~s18||的偽幣分布情況 32
表3-9、s1~s9中7枚偽幣分布情形 33
表3-10、s1~s9中各種偽幣分布情形 33
表3-11、s1~s9中各種偽幣分布情形 34
表3-12、s1~s9中各種偽幣分布情形剩下的可能 34
表3-13、所有偽幣分布情形剩下的可能 34

參考文獻
【1】 V. Auletta, A. Negro, G. Parlati, Some results on searching with lies. Theoretical Computer Science, pp. 24-37, October 1992.
【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.
【7】 T. H. Cormen, C. L. Leiserson, R. L. Rivest, Introduction to Algorithms, The MIT press & McGraw-Hill, 1993.
【8】 C. Deppe, Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting-codes. Diskrete Strukturen in der Mathematik, Preprint 98-036, Bielefeld, 1998.
【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】 X. D. Hu, P. D. Chen, F. K. Hwang, A new competitive algorithm for the counterfeit coin problem. Preprint, 1992.
【11】 R. W. Irving, Towards an optimum Mastermind strategy. Journal of Recreational Mathematics, Vol. 11:2, pp. 81-87, 1978.
【12】 G.. Kabatianski, V. Lebedev, The Mastermind game and the rigidity of the Hamming space. Proceedings of the International Symposium on Information Theory. IEEE, pp. 375-375, 2000.
【13】 D. E. Knuth, The computer as Mastermind, Journal of Recreational Mathematics, Vol. 9:1, pp. 1-6, 1976.
【14】 K. I. Ko, S. C. Teng, On the number of queries necessary to identify a permutation. Journal of Algorithms, Vol. 7, pp. 449-462, 1886.
【15】 K. Koyama, T. W. Lai, An optimal Mastermind strategy. Journal of Recreational Mathematics, Vol. 25, pp. 251-256, 1993.
【16】 E. Neuwirth, Some strategies for Mastermind. Zeitschrift fur Operations Research, Vol. 26, pp. 257-278, 1982.
【17】 J. A. Pyrich, The counterfeit coin problem — times 2! http://www.97cc.com/~japyrich/projects/coins.shtml, 2001.
【18】 P. J. Wan, Q. Yang, D. Kelley, A 3/2log3-competitive algorithm for the counterfeit coin problem. Theoretical Computer Science Vol.181, pp. 347-356, 1997.
【19】 楊錦潭、鄭又齊、馬德強、王授民合著，演算法的天空，pp.247-273，松崗書局，1989年6月初版。
【20】 馬德強、陳國正發表，以歸納法處理偽幣問題，http://wwwedu.nknu.edu.tw/48552001/，2002。