程式技術

資訊 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ MatchMaker 分數：250 題目程式介面123456Class Name: MatchMakerMethod Name: getBestMatchesParamaters: String[], String, intReturns: String[]Method signature:String[] getBestMatches(String[] members, String currentUser, int sf); 說明線上交友網站需要透過程式來自動找出條件匹配的對象，會員會先輸入一些資料做為依據，當會員要求配對時，程式會回傳一個符合的對象清單，對象的符合項目必須大於等於設定的相似度 (similarity factor)。現在程式會先輸入會員資料、目前會員和相似度，會員資料如下格式： 1{名稱} {性別} {對象性別} {資料1} {資料2} ... 例如 1BETTY ...

簡介最大子序列 (Maximum Subarray 或稱作 Maximum Subsequence) 為在一個具有正負數陣列當中，找出一段連續的元素總和最大，這個問題又分為一定要取值或可不取。實作方法有很多種，這裡說明四種實作方法，分別為暴力法、改良式暴力法、Divide and Conquer 和 Kadane’s 演算法 (Dynamic Programming)，其中 Kadane’s 實作取值和可不取值兩種版本，其他為一定要取值版本。 演算法暴力法最簡單直覺的想就是將所有可能的開始和結束範圍都算過一遍即可，[0] ~ [0]、[0] ~ [1] … [0] ~ [N] … [N] ~ [N] 的總和找出最大。 改良式暴力法然而在上面暴力法計算，[0] ~ [N] 的總和時，其實過程中 [0] ~ [0]、[0] ~ [1] … [0] ~ [N] 的總和也已經同時計算了，所以只需計算 [0] ~ [N]、[1] ~ [N] … [N] ~ [N] 即可。 Divide and Conquer如下圖所示，Divide and Conquer 的基本概念是，將數列分成兩塊，各自回報 ...

簡介二元搜索法 (Binary Search) 又稱折半搜索，搜索演算法的一種，可使用 Divide and Conquer 或直接使用迴圈 (迭代) 來實作，搜索的目標資料必須是已經排序過的 (以小到大排序為例)。其概念是每次挑選中間位置的資料來比對，若該資料小於目標值，則縮小範圍為左半部，反之亦然；因此使用這個方法每次比對後都可以濾掉一半的資料，以增快搜索速度。過程依以下步驟進行： 取出搜索範圍中點的元素。 與搜索目標比較，若相等則回傳位址。若小於則將左邊邊界改為中點右側，若大於則將右邊邊界改為中點左側。 左邊邊界不超過右邊邊界(還有資料)則重複以上動作，若已無資料則回傳-1(找不到)。 流程範例如圖所示，例如搜索值為4的元素： 分析 最佳時間複雜度：O(1) 平均時間複雜度：O(log n) 最差時間複雜度：O(log n) 空間複雜度：O(1) 虛擬碼迭代12345678910111213141516function search(list, target) var left = 0, right = list.length - 1 while left <= ri ...

資訊 路徑：Tournament \ 1-16 \ 1 - Inv 2001 R1 \ Prerequisites 分數：1000 題目程式介面12345Class Name: PrerequisitesMathod Name: orderClassesParameters: String[]Returns: String[]Method signature: string[] orderClasses(string[] classSchedule) 說明學生在大學修課時，會遇到複雜的先修課問題，也就是某些課會有要求需先修完另外某些課後才能修，所以我們來寫一支幫助排定修課續順的程式。程式會輸入字串陣列，每一筆資料表示課程與此課程的先修課，格式大致如下： 1{系所代碼}{課號}: {先修課} {先修課} 例如 1CSE111: CSE110 MATH101 請依據以下規則排出修課的順序： 課程的先修課必須全部修過後才能修。 同時有多個課程可以修時，先修課號數字小的。 承上，如果數字相同時，則先修系所 ...

簡介快速排序法是排序演算法的一種，使用 Divide and Conquer 的演算法來實作。其概念是從數列中挑選一個基準點，大於基準的放一邊，小於的放一邊，如此循環最後可完成排序。過程依照以下步驟進行(遞增為例)： 數列中選擇一元素作為基準點 (pivot)。 小於此元素的移至基準的左邊，大於此元素的移至右邊，相等的任意放。 基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。 流程範例如圖所示： 實作的方式除了一般使用額外的暫存數列之外，也有使用較少額外空間的 原地 (In-place) 方式，In-place 的方式主要概念是將基準點暫時移到最右邊，小於基準的移至數列一端並記錄遞增索引，最後將基準點換回索引位置，過程依照以下步驟進行 (遞增為例)： 數列中選擇一元素作為基準點 (pivot)，並與最右邊的元素交換位置。 建立一索引指向最左邊元素。 小於基準的元素與索引位置的元素交換位置，每次交換後遞增索引。 完成後將基準點與索引位置的元素交換位置。 基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。 流程範例如圖所示： 基準點 ...

問題在 Windows 環境上使用 mysql2 的gem，啟動網站時出現以下錯誤 1C:/RailsInstaller/Ruby1.9.3/lib/ruby/gems/1.9.1/gems/mysql2-0.3.11/lib/mysql2.rb:9:in `require': Incorrect MySQL client library version! This gem was compiled for 6.0.0 but the client library is 5.0.51a. (RuntimeError) 原因如錯誤訊息所說，mysql2 使用的 client 是 mysql-connector-c-6 的版本，而電腦上安裝的版本不符 解決方案下載所需的client版本 http://dev.mysql.com/downloads/connector/c/ 選擇 mysql-connector-c-noinstall-6.x.x-win32.zip 的版本，例如 1mysql-connector-c-noinstall-6.0.2-win32.zip 解壓縮後 ...

資訊 路徑：Tournament \ 1-16 \ 1 - Inv 2001 R1 \ SquareDigits 分數：500 題目程式介面1234Class Name: SquareDigitsMethod Name: smallestResultParameters: intReturns: int 說明輸入一數字 n，找到 T(x) 包含 n 的最小 x。 定義S(x)：表示 x 的數字逐字幕次和，例如 S(3) = 3 * 3 = 9 和 S(230) = 2 * 2 + 3 * 3 + 0 * 0 = 13。T(x)：表示重複執行 S(x) 直到出現重複結果，例如 T(37)，S(37) = 58S(58) = 89S(89) = 145S(145) = 42S(42) = 20S(20) = 4S(4) = 16S(16) = 37S(37) <- 重複T(37) = { 58, 89, 145, 42, 20, 4, 16, 37 } ...

簡介TopCoder 是一個提供線上程式競賽的網站，類似 ACM 的競賽，提供演算法題目的比賽和練習之外，還有其他的軟體設計的項目，如果獲得前幾名的話還可以拿到獎金。 可以到官網點擊右上 [SIGN UP] 註冊，之後可以在這邊參加各種類型的競賽。 其中的演算法類型提供了線上編寫程式送出的功能，可以從畫面左上角的 O(n) 的圖示進入，其他圖示表示不同類型的競賽 點擊 O(n) 之後，他會開啟 Java 程式，登入後可以選擇進入練功房寫以前競賽的題目來練習，或者是參加目前進行中的競賽。 進入練功房之後，可以開啟題目來練習，一個競賽有三道題目，依據難度分別是 250、500 和 1000 分的題目。 開啟之後會進入撰寫程式畫面，TopCoder 目前支援 Java、C++、C# 和 VB 四種語言。程式寫到一半要離開的話，可以使用 Save，若寫完則可以 Compile，若要自己輸入資料測試則使用 Test，確認一切正確之後則可以 Submit 出去，題目越快完成交出去分數會越高，從題目被開啟後就開始計時，另外重新 Submit 的話還會額外的扣分，無論如何，完成至少可得到 30% 的分 ...

簡介合併排序法 (或稱歸併排序法)，是排序演算法的一種，使用 Divide and Conquer 的演算法來實作。排序時需要額外的空間來處理，過程依照以下步驟進行： 將陣列分割直到只有一個元素。 開始兩兩合併，每次合併同時進行排序，合併出排序過的陣列。 重複2的動作直到全部合併完成。 流程範例如圖所示： 實作又可分為 Top-down 和 Bottom-up，依據原始的步驟會先將陣量分割直到剩一個元素 (Top-down)，然而也可以一開始就直接切割成單一元素開始合併 (Bottom-up)。 分析 最佳時間複雜度：O(nlog n) 平均時間複雜度：O(nlog n) 最差時間複雜度：O(nlog n) 空間複雜度：O(n) Stable sort：是 虛擬碼以下以較高階的想法寫出虛擬碼，實作上效能要好必須還要進一步修改： Top-down12345678910111213141516171819202122function sort(list) if list.length == 1 return list end if left = 取出從 list[0] 到 list ...

簡介也翻譯作漢諾塔，這是根據一個傳說演變而成的題目，題目的規則如下： 有三根竿子，例如編號為 A、B 和 C，竿子上面可串中空圓盤。 於 A 竿子放入 N 個盤子開始，盤子由下至上變小。 一次只能移動一個盤子。 大盤子不能再小盤子上面。 目標將全部盤子移動到 C 竿子。 現在我們嘗試上面的問題撰寫成程式解決，依據上面的說明，寫出程式印出移動的步驟。 演算法此題目一般可使用 Divide and Conquer 來解，當有 N 個盤子的時候很難思考，我們假設只有兩個盤子的時候，就很好思考，只需要： 將上面的盤子移到暫時擺放的竿子。 將下面的盤子移到目標竿子。 將原來上面的盤子移到目標竿子。 而當盤子 N 個的時候，其實也是依照同樣的邏輯進行即可，但上面 N - 1 個盤子要如何移到暫時擺放的竿子，這時候我們用遞迴的方式交給下一次呼叫自己去處理。 虛擬碼123456789function move(disks, from, to) if disks == 1 自訂的移動動作 else move(disks - 1, from, 另一竿子) move(1, from, ...