程式技術

簡介費波那西數列 (Fibonacci)，又稱費氏數列、黃金分割數列等很多譯名，由西方的數學家費波那西使用兔子問題來描述這個數列，以下引用 Wiki： 第一個月初有一對剛誕生的兔子 第二個月之後(第三個月初)牠們可以生育 每月每對可生育的兔子會誕生下一對新兔子 兔子永不死去 使用數學式來表達的話如下： 123F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) 列出前20個數值 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 演算法數學法解法有很多種，可以直接套數學公式，推導過程可參考 Wiki，公式如下： 以程式設計的角度來看，一般使用迭代法、Divide and Conquery 和動態規劃 (Dynamic Programming) 的方式來解。 迭代法由於每次新的問題的答案來自於前兩個問題，所以每次運 ...

簡介Dynamic Programming 中文譯作動態規劃，動態規劃類似 Divide and Conquer，一個問題的答案來相依於子問題，常用來解決最佳解的問題。與 Divide and Conquer 不同的地方在於，動態規劃多使用了 memoization 的機制，將處理過的子問題答案記錄下來，避免重複計算，因此在子問題重疊的時候應該使用動態規劃；Divide and Conquer 通常使用遞迴 (Top-Down) 來處理，有時轉成迴圈 (Bottom-up) 來解並不容易，故使用動態規劃則可以解決重覆計算並保留遞迴思考的優點。 同樣拿費波那西數列 (Fibonacci) 為例子 使用 Divide and Conquer 的寫法如下： 12345678function Fibonacci(n) if n == 0 return 0 if n == 1 return 1 end if return Fibonacci(n - 1) + Fibonacci(n - 2)end function 如同之前在 Divide and conquer 一文中所說，會重覆計算黃 ...

說明本文針對一些 JavaScript 效能相關的文章之理論進行實際的測試與驗證，結果有些符合預期，有些則意料之外。測試環境瀏覽器如下： Chrome：18.0.1025.168 m Firefox：12.0 Safari：5.1.5(7534.55.3) Opera：11.62 IE8、IE7 為使用 IE9 切換模式 變數存取JavaScript 變數存取具有以下特性： 使用變數時會透過作用域鏈 (Scope Chain) 自動判斷其所屬範圍，會從目前區域變數查找，逐漸往外圍查找。對變數存取屬性 (點符號.) 會進行查找而消耗時間。 根據以上原則，我們可以推論出一些增加效能的可能方法並實際測試： 使用區域變數，減少變數查找次數，包含作用域鏈與存取屬性，盡可能的使用區域變數。 Chrome Firefox Safari Opera IE9 IE8 IE7 存取區域變數 14.9 15.4 62.8 58.3 30 25 30 存取全域變數 13.8 17 73.9 74.1 43.7 11165.7 11208.6 存取變數屬性 15.3 12.9 80 ...

簡介Iterative Method 中文翻譯作迭代法或疊代法，而在數學領域和電腦程式領域的定義有些不同，數學領域的迭代法指的是無法使用公式一次求解，而須反覆運算求出近似解；而在電腦程式雖然亦有反覆運算的含義，但一般指的是迴圈解。 迭代法透過設定一個初始值開始反覆運算，最後求出答案，是算是一種 Bottom-Up 的模式，通常會和遞迴作比較，實作方式簡易區分如下： 迭代：使用迴圈實作。 遞迴：函式推疊呼叫。 基本上相同的演算法如果能夠直接使用迴圈，因為不透過函式堆疊，效能會比較好。相對於迭代，遞迴就算是一種 Top-Down 的模式。以階乘為範例： 遞迴123456function Factorial(n) if n == 1 return 1 end if return n * Factorial(n - 1)end function 遞迴的思考模式，求 n 階的時候當作 n - 1 階已知，相乘即是答案，n - 1 的如何求在 n 階的時候無須理會，就像上級要交由下屬去處理的 Top-Down 模式。 迭代1234567function Factorial(n) sum = ...

資訊 路徑：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 解壓縮後 ...