(34.204.201.220) 您好!臺灣時間:2021/04/19 18:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳京達
論文名稱:三個變數之硬幣問題之研究
論文名稱(外文):Research on the Coin Problem for Three Variables
指導教授:林順喜林順喜引用關係
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:82
中文關鍵詞:硬幣問題找錢問題換硬幣問題Frobenius數
外文關鍵詞:Coin ProblemMoney-Changing ProblemCoin Exchange ProblemFrobenius Number
相關次數:
  • 被引用被引用:1
  • 點閱點閱:273
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
硬幣問題又叫找錢問題或換硬幣問題,也有人叫它做兌換郵票問題,是一個十分著名的問題。
由於現在於兩個變數的情況下已有公式解,而在四個變數以上已知無closed-form solution,故本論文在三個變數的情況下做討論。此部分的問題現在尚未有通解,但已知在某些情況下有解或是上限值。所以本論文的研究目標是以不同於現有數學討論的方式,運用電腦的幫助,由大量的數據之中,整理出新的規則,希望能由新規則及舊規則推廣得到更完整的公式,以解決此問題。
我們在此問題之的某些特例之上提出一種快速的解法,我們發現了一種填表法,剛好可利用它來看出Frobenius number的規律性,因此可在最小數為2、3、4、5或6時解出所有此問題之解,且只需簡單之計算。我們發現且證明了在最小數為這些特定數時擁有某些特定之規則可快速解此問題。
Coin Problem is known as Money-Changing Problem, Coin Exchange Problem, or Stamp Exchange Problem. It is a very famous problem.
Now it already has solution for two variables. It has been proven that there is no closed-form solution for more than three variables. But it is already known that there are upper bounds in some situations.
In this thesis, we focus on solving the coin problem for three variables. We discover a table-filling approach which can be used to deduce the regularities of Frobenius numbers. From it, we derive a fast way to find answers in some special cases, i.e. the smallest vaule among the three variables is either 2, 3, 4, 5 or 6. It can find answers directly from the formulas which are very easy to be calculated.
第一章 緒論 1
第一節 前言 1
第二節 文獻探討 2
第三節 三個變數之Coin Problem之介紹及定義 4
第四節 論文架構 4
第二章 g(3,b,c)時的規則 6
第一節 g(3,b,c)時的問題定義 7
第二節 g(3,b,c)時的規則解說 7
第三節 g(3,b,c)時的規則證明 9
第四節 本章之結論 11
第三章 g(4,b,c)時的規則 12
第一節 g(4,b,c)時的問題定義 12
第二節 g(4,b,c)時的規則解說 12
第三節 g(4,b,c)時的規則證明 18
第四節 本章之結論 27
第四章 g(5,b,c)時的規則 28
第一節 g(5,b,c)時的問題定義 28
第二節 g(5,b,c)時的規則解說 28
第三節 g(5,b,c)時的規則證明 36
第四節 本章之結論 46
第五章 g(6,b,c)時的規則 47
第一節 g(6,b,c)時的問題定義 47
第二節 g(6,b,c)時的規則解說 47
第三節 g(6,b,c)時的規則證明 59
第四節 本章之結論 77
第六章 結論及未來方向 78
參考文獻 81
[1] F. Aguiló, A. Miralles, “On the Frobenius’ problem of three numbers,” Discrete Mathematics &Theoretical Computer Science, Vol.AE, 2005, pp.317-322.
[2] M. Beck, D. Einstein, S. Zacks, “Some experimental results on the Frobenius problem,” Experimental Mathematics, Vol.12, 2003, pp.263-269.
[3] D. Beihoffer, J. Hendry, A. Nijenhuis, S. Wagon, “Faster Algorithms for Forbenius Numbers,” The Electronic Journal of Combinatorics, Vol.12, 2005, R27.
[4] T. C. Brown, P. J. Shiue, “A remark related to the Frobenius problem,” Fibonacci Quarterly, Vol.31, 1993, pp.31-36.
[5] S. Böcker, Z. Lipták, “The money changing problem revisited: computing the Frobenius number in time O(ka1),” Computing and Combinatorics Conference, Kunming, China, 2005.
[6] J. Dixmier, “Proof of a conjecture by Erd¨os and Graham concerning the problem of Frobenius,” Journal of Number Theory, Vol.34, 1990, pp.198-209.
[7] R. J. Levit, “A minimum solution for a diophantine equation,” American Mathematical Monthly, Vol.63, 1956, pp.646-651.
[9] J. L. R. Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications, Oxford Univerity Press, 2005.
[10] J. J. Sylvester, “Mathematical questions with their solutions,” The Educational Times, Vol.41, 1884, pp.21.
[11] A. Tripathi, S. Vijay, “On a generalization of coin exchange problem for three variables,” Journal of Integer Sequences, Vol.9, 2006, Article 06.4.6.
[12] A. Tripathi, “The coin exchange problem for arithmetic progressions,” American Mathematical Monthly, Vol.101, 1994, pp.779-781.
[13] Y. Vitek, “Bounds for a linear Diophantine problem of Frobenius,” Jurnal of London Mathematical Society, Vol.10, 1975, pp.79-85.
[14] E. W. Weisstein, “Coin problem,” From MathWorld—A Wolfram Web Resource, http://mathworld.wolfram.com/CoinProblem.html.
[15] E. W. Weisstein, “McNuggetNumber,” From MathWorld—A Wolfram Web Resource, http://mathworld.wolfram.com/McNuggetNumber.html.
[16] E. W. Weisstein, “FrobeniusNumber,” From MathWorld—A Wolfram Web Resource, http://mathworld.wolfram.com/FrobeniusNumber.html.
[17] E. W. Weisstein, “Diophantine equation,” From MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/DiophantineEquation.html.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔