(3.237.20.246) 您好!臺灣時間:2021/04/14 10:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:劉耀才
研究生(外文):Liu Yao Tsai
論文名稱:偽幣問題之改良演算法設計與分析
論文名稱(外文):The Designs and Analyses of Improved Algorithms for the Counterfeit Coins Problem
指導教授:林順喜林順喜引用關係
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:150
中文關鍵詞:下限分析偽幣問題三分法
外文關鍵詞:lower bound analysisthe counterfeit coins problemtrisection method
相關次數:
  • 被引用被引用:0
  • 點閱點閱:468
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
偽幣問題由來已久,有許多人不斷的增加不同的條件,使得這個問題變得更具挑戰性也更加困難,也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的偽幣問題。在本論文中,我們對兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題提出了改良的演算法,以及改進了李立中的三枚以上偽幣知其輕重演算法,使之成為三枚以上偽幣不知其輕重的演算法。在最後我們也對一枚偽幣知其輕重、一枚偽幣不知其輕重、兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題,提出了分析,說明各個演算法相對於理論下限還有多少可以努力的空間。
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
第二章 研究背景及目的 3
第一節 研究背景 3
第二節 一般化問題的相關研究 4
第三節 一枚偽幣問題的相關研究 4
第四節 兩枚偽幣問題的相關研究 6
第五節 三枚以上偽幣問題的相關研究 7
第三章 我們提出的新方法與改良的方法 8
第一節 兩枚偽幣未知輕重的演算法 10
第二節 三枚偽幣已知輕重的演算法 33
第三節 三枚偽幣未知輕重的演算法 43
第四節 四枚偽幣已知輕重的演算法 63
第五節 四枚偽幣未知輕重的演算法 81
第六節 三枚以上偽幣未知輕重的一般化演算法 123
第四章 秤量次數的理論下限分析 131
第一節 找出一枚已知輕重偽幣的秤量次數理論值 131
第二節 找出一枚未知輕重偽幣的秤量次數理論值 131
第三節 找出兩枚已知輕重偽幣的秤量次數理論值 132
第四節 找出兩枚未知輕重偽幣的秤量次數理論值 133
第五節 找出三枚已知輕重偽幣的秤量次數理論值 135
第六節 找出三枚未知輕重偽幣的秤量次數理論值 137
第七節 找出四枚已知輕重偽幣的秤量次數理論值 139
第八節 找出四枚未知輕重偽幣的秤量次數理論值 141
第九節 找出三枚以上未知輕重偽幣的一般化分析 143
第五章 結論 144
參考文獻 145
【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。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔