Please use this identifier to cite or link to this item:
The Designs and Analyses of Improved Algorithms for the Counterfeit Coins Problem
Liu Yao Tsai
lower bound analysis
the counterfeit coins problem
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.
|Appears in Collections:||學位論文|
Files in This Item:
|700601.pdf||83.53 kB||Adobe PDF||View/Open|
|700602.pdf||125.66 kB||Adobe PDF||View/Open|
|700603.pdf||474.36 kB||Adobe PDF||View/Open|
|700604.pdf||3.72 MB||Adobe PDF||View/Open|
|700605.pdf||59.98 kB||Adobe PDF||View/Open|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.