Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106310
Title: 偽幣問題之改良演算法設計與分析
The Designs and Analyses of Improved Algorithms for the Counterfeit Coins Problem
Authors: 林順喜
劉耀才
Liu Yao Tsai
Keywords: 下限分析
偽幣問題
三分法
lower bound analysis
the counterfeit coins problem
trisection method
Issue Date: 2005
Abstract: 偽幣問題由來已久,有許多人不斷的增加不同的條件,使得這個問題變得更具挑戰性也更加困難,也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的偽幣問題。在本論文中,我們對兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題提出了改良的演算法,以及改進了李立中的三枚以上偽幣知其輕重演算法,使之成為三枚以上偽幣不知其輕重的演算法。在最後我們也對一枚偽幣知其輕重、一枚偽幣不知其輕重、兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題,提出了分析,說明各個演算法相對於理論下限還有多少可以努力的空間。
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.
URI: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=%22http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22G0069147006%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106310
Other Identifiers: G0069147006
Appears in Collections:學位論文

Files in This Item:
File Description SizeFormat 
700601.pdf83.53 kBAdobe PDFView/Open
700602.pdf125.66 kBAdobe PDFView/Open
700603.pdf474.36 kBAdobe PDFView/Open
700604.pdf3.72 MBAdobe PDFView/Open
700605.pdf59.98 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.