臺灣博碩士論文加值系統

在資訊科學領域的演算法(Algorithm)，有著琳琅滿目的各種方法，較重要者如：分而治之法（Divide & Conquer）,回溯法（Backtracking）,分支切斷法（Branch & Bound）,動態規劃法（Dynamic Programming）,暴力法（Brute Force）,貪婪法（Greedy Method）…等等。由於演算的方法眾多，而且不同問題又常會有多種不同的解法，所以要如何應用這些方法來解決問題將會是一個課題。而自從1977年即開始連續舉辨程式設計大賽至今的美國電腦協會(ACM)，也在網路上設有線上即時評審程式(Online Judge)來歡迎世界各地程式愛好者解題，而且收集各大比賽相關資訊的題庫數量也接近700題。所以本論文希望針對解答題庫的過程中所得到的心得作歸類與整理！由於題庫中的題型眾多，為了讓有興趣的愛好者，可在短時間對整個題庫有大概的認識，所以希望在分類中除了針對解法作分類外，也對問題背景的趣味性、任務要求的相似性作分類。同時為了維持合理的適用性與正確性，所討論的問題將僅就已獲得ACM線上評審接受的問題作為研究的依據。整個過程中較重要的部分是在歸類後，將各分類中較具代表性的問題，作詳細的說明與分析。

There are many algorithmic approaches in computer science to solve a problem. To name a few: Divide & Conquer, Backtracking, Branch & Bound , Dynamic Programming,　Brute Force,　Greedy Method, and so on. In general, there is more than one way to solve the same problem, and a useful algorithmic approach usually can help us to solve a large number of problems.
From 1977, ACM continuously hold a world-programming contest. A web site in http://acm.fi.uva.es/problemset/ can find hundreds of problems. Every participant in program design can use E-mail to submit source code to online judge for correctness. This paper will classify problems from our experience in problem solving.
Since the pool of problems are huge, in order to quickly grasp the gist in solving those problems, we will classify the problems according to similar backgrounds, missions and solved method. For the reason of correctness, we only concludes problems submitted and accepted by ACM online judge.
The focus of this paper is to show and analyze the representative of the problems in similar category.

目錄
第一章 緒論……………………………………………………1
1.1 前言…………………………………………………1
1.2 研究動機……………………………………………1
1.3 研究方向與內容概觀………………………………3
第二章 背景相關知識 ……………………………………………4
2.1 ACM線上競賽的背景與現況…………………………4
2.1.1 線上評審所提供的各種基本資訊…………………4
2.1.2 目前資訊概況與未來遠景…………………………6
2.1.3 送審的方法…………………………………………6
2.1.4 送審前的注意事項…………………………………7
2.2 常用演算法比較說明…………………………………8
2.2.1 DP與D&C的異同，DP與Greedy的異同………………8
2.2.2 DP與Greedy的一般適用場合………………………9
2.2.3其他搜尋法與常用基本技術與函數…………………9
第三章 ACM題庫分類………………………………………11
3.1 我們的分類原則與得到的十五個大類別…11
3.2 分類的特點與深入討論的四個大類別……13
第四章 排列(Permutation)組合與進位類問題的探討……15
4.1本類問題概說…………………………………15
4.2 各種好用的解法：字典序、非字典序、亂數序…15
4.3本文將”非字典序數法”改良為”字典序數法"…17
4.4 P153字元變換位置問題(Permalex)-先深(DFS)觀點…19
4.5 P417文字索引代號(Word Index)-先寬(BFS)觀點………20
4.6 P146識別碼問題(ID Codes)-發現找下一個排列………23
4.7 排列(Permutation)類問題小結…………………………28
第五章 動態規劃(DP)類問題的探討……………………………29
5.1本類問題概說………………………………………………29
5.2 P108最大連續四邊區域和(Maximum Sum)…………30
5.3 P116旅行推銷員問題(Unidirectional TSP)…………35
5.4 P164字串電腦(String Computer)- Edit Problem…39
5.5 P111打歷史成績(History Grading )- LCS Problem…43
5.6 P531 妥協方案(Compromise ) - LCS Problem print…49
5.7 P497戰略防衛行動(S.D.I.) - LIS Problem…………50
5.8 動態規劃(DP)類問題小結………………………………56
第六章 圖形(Graph)類問題的探討……………………………………57
6.1本類問題概說……………………………………………57
6.2 P571倒水問題(Jugs)-BFS……………………………58
6.3 P291一筆劃問題 (The House Of Santa Claus)-DFS…62
6.4 P103套盒子問題(Stacking Boxes)-Topologic Sort…64
6.5 P334同步事件編號(Identifying C.E.)-Transitive
Closure…68
6.6 P157尋找最佳路線(Route Finding)-Shortest Path…72
6.7 P558蟲洞(Wormholes)-Find Neg. Cycle………………77
6.8 P563犯罪浪潮(Crime Wave)-Max Flow…………………78
6.9 P273 傑克吸管(Jack Straws)-Path Compress……89
6.10圖形(Graph)類問題小結………………………………94
第七章 數學類之數論問題的探討……………………………………97
7.1本類問題概說……………………………………………97
7.2 P135沒任何四方形(No Rectangles)-Latin Square or
Projective Geometry……………………97
7.3 P138街道上的門牌號碼(Street Numbers)-Continued
Fraction Exp. or Pell’s Equ. ………107
7.4數論(Number Theory)類問題小結………………111
第八章 結論與展望………………………………………………114
參考文獻 …………………………………………………………116
附錄一：ACM題庫分類的分類題號………………………………119
附錄二：中文短稿…………………………………………………131
附錄三：英文短稿…………………………………………………139

參考文獻
主要演算法相關書籍：
[Chow 1997]Randy Chow ,Theodore Johnson, “Distributed Operating Systems & Algorithms,” Addison Wesley, 1997.
[Cormen 1996 ]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, “Introduction to Algorithms,” 1996.
[Horowitz 1996]Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran “Computer Algorithms C++,” 1996.
[Horowitz(DS)] Ellis Horowitz, Sartaj Sahni, Susan Anderson-freed “Data Structures in C,” 1993.
[Manber 1989]UDI MANBER “Introduction To Algorithms,” Addison Wesley, 1989.
[Sedgewick 1988]Robert Sedgewick “Algorithms,” Addison Wesley, 1988.
[Barssard 1988]Gilles Barssard, Paul Bartley, “Algorithmics Theory & Practice,” Prentice Hall, 1988.
[冼鏡光1996]冼鏡光, “C名題精選百則,” 儒林圖書公司,1996三版.
[張子浩1991]張子浩、徐立, “離散數學,” 文笙書局1991.
[張自南1997]張自南 “數值最適化方法,” 全華科技圖書”, 1997,pp504 .
[張遠南1996]張遠南,”使人聰明的智力遊戲”,九章出版社,1996,p59-62.
[劉函初1991]劉函初, “離散與組合數學,” 華滎書局, 1991, pp167-171.
[盧開澄1993]盧開澄,”組合數學,” 格致圖書, 1993,pp17-20.
[郭台生1996]郭台生,”演算法與資料結構,” 儒林圖書公司,1996.
其他：
[Bellman 1957]Richard Bellman, “Dynamic Programming,” Princeton University Press, 1957.
[Bellman 1962]Bellman, “Applied Dynamic Programming,” Princeton University Press, 1962.
[Birk 1989] Y. Birk and J. B. Lotspiech, “On Finding Non-intersecting Straight-Line Connections of Grid Points to the Boundary,” IBM Research Report RJ 7217(67984), Dec, 1989.
[Birk 1992] {同上Journal of Algorithm, 13, 636-656(1992) }
[Gersting] Judith L. Gersting “Mathematical structures for computer science,” Freeman, pp115-118.
[Gupta 1994]Rajiv Gupta, Scott A. Smolka, Shaji Bhaskar, “On Randomization in Sequential and Distributed Algorithms,” ACM Computing Surveys, Vol.26, No.1, March 1994,pp7-59.
[Ebert 1988]J.Ebert, Computing Eulerian Trails, Information Processing Letters, Vol.28(1988), pp93-97.
[Kanarek 1998] A. Czumaj, P. Kanarek, M. Kutylowski, K. Lorys, “Algorithmicam,” Vol. 21, No. 1,pages 2-20,May 1998.
[Lloyd 1983] Errol L. Lloyd “An O(nLogm)Algorithm for the Josephus Problem,” Journal of algorithms 4. 1983.
[Maekawa 1985]Mamoru Maekawa “A Square Root N Algorithm for Mutual Exclusion in Decentralized Systems,” ACM TOCS, Volume 3, Number 2, May 1985, pp145-159.
[Stevenhagen 1992] Peter Stevenhagen “On The Solvability of the Negative Pell Equation,” Mathematical preprint series, 1992, report 92-16.
[Stevenhagen 1993] Peter Stevenhagen “A Density Conjecture for the Negative Pell Equation,” Mathematical preprint series, 1993, report 93-08.
[http-1] “Information on Permutations,” http://www.theory.csc. uvic.ca/~con/cos.html
[http-135.1] Terry Ritter, “Latin Squares: A Literature Survey,” http:// www.io.com/~ritter/RES/LATSQ.HTM
[http-135.2] Newsgroups: sci.math http://www.math.niu.edu/~rusin/known-math/98/graeco_latin
[http-135.3] Terry Ritter, “Balanced Block Mixers,” http://www.io.com/~ritter/PATS/MIXPATC.HTM
[http-135.4]Orthogonal Latin Squares. http://www.cut-the-knot.com/arithmetic/latin3html
[http-135.5]Orthogonal Latin Squares. http://www-math.cudenver.edu/ ~wcherowi/courses/m6406/csln3.html
[http-135.6]Latin Square http://www.cut-the-knot.com/arithmetic/latin.html
[http-135.7] Finite geometries. http://www-math.cudenver.edu/ ~wcherowi/courses/m6406/cslnc.html
[http-135.9]” The History of the Problem ,” http://www.cecm.sfu.ca/organics/papers/lam/paper/html/node2-an.
[http-135.10] ”Projective Geometry” http://mathworld.wolfram.com/ProjectiveGeometry.html
[http-135.11] “sci.math FAQ:Projective Plane of Order 10,” http://www.faqs.org/faqs/sci-math-faq/proyectiveplane/
[http-135.12] Clement W. H. Lam “The Search for a Finite Projective Plane of Order 10,” http://www.cecm.sfu.ca/organics/papers/lam/index.hmtl, 1991.
[http-135.13] “Bruck-Ryser-Chowla Theorem,”http:// mathworld.wolfram.com/Bruck-Ryser-ChowlaTheorem.html
[http-138.1] Simon Plouffe, “Continued fraction algorithm”, http://www.lacim.uqam.ca/pi/cf.html.
[http-138.2] Computing the generating function of a series given its first few terms, by François Bergeron and Simon Plouffe, Experimental Mathematics, Vol. 1 #4, 1992.
[http-138.3] “Pell Equation” http://mathworld.wolfram.com/PellEquation.html
[http-138.4]”Pell’s Equation” http://glorian.math.virginia.edu/dnt/pell4.html
[http-138.5] “Pell’s Equation”, http://www-groups.dcs.st-and.ac.uk/~history/Diagrams/PellEquation.gif
[http-138.6]Newsgroups: sci.math, ”Pell Equation ,” http://www.math.niu.edu/~rusin/papers/known-math/98/sq_tri
[http-138.7]Methods to solve Diophantine Equ. http://members.tripod.com/~alpertron/METHODS.HTM