小殘的程式光廊

簡介最大子序列 (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 的基本概念是，將數列分成兩塊，各自回報 ...

拍攝時間：2012 年 4 月 7 日 隔天要去陽明山爬山，今天將要在台北親戚家住一晚，這天下午先來到士林官邸逛逛。 地址：台北市福林路 60 號 電話：0228836340 從捷運士林站二號出口走一段路，過一兩個路口就到了，相當方便。沒來過這裡，聽名稱一直以為是棟房子而已，沒想到是個花園。 今天這裡就是很多的花，一朵盛開的花 除了花之外還有一些園藝造景 季節似乎已經過去，花少了很多 不知道是甚麼花，一串一串的開 粉紅色的玫瑰花 水池造景 夏天到了，落花不是無情物，化作春泥更護花 抓住春天的尾巴 這時候人已經少了很多，稍早時後四處都是陸客 走到這裡的時候正巧噴水池開始噴起來 路旁的樹木樹皮很特別 在教堂對面的中式庭院 螃蟹造景，還是隻煮熟的螃蟹 新蘭亭 這時候這裡正在展覽蘭花 有各式各樣的蘭花 這也是蘭花 這作品似乎較作聖誕樹，有像嗎 園藝展蘭館，結果在裡面沒拍到甚麼 走到了另一邊，有一顆奇特的楓樹，樹幹完全被別的植物包覆住，秋天來的時候也許會更漂亮 這裡還有生態區 很多種類的水生植物 繞了一圈看到官邸了，不過時間太晚已經關閉，無法進入 而且進去還要額外的門票，所以隔著柵欄拍幾 ...

簡介二元搜索法 (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 ...

拍攝時間：2012 年 4 月 4 日 淡水紅毛城今天來到了淡水，一大早店家都還沒開，街上也都沒有人，不過今天不是來這逛街的，目標是紅毛城。 地址：新北市淡水區中正路28巷1號 電話：02-2623-1001 有人在這裡進行帆船衝浪，今天風很大，船的速度也相當的快速，看到他們快速的來回兩岸 之前通常都走到星巴克就回頭了，不過原來繼續走還可以到別的地方，經過了這條林蔭小徑，樹低垂到快要進水裡，很特別的景色 走了一段路之後，走出到大馬路的對面就看到紅毛城 之前要門票，現在已經不用門票了 雖然叫做紅毛城，不過比較像是官邸之類的建築 進入第一棟建築，裡面有牢房，關著不知名的人物 中庭有位高大的外國人 威廉王子號，大航海時代的船艦 客廳的擺設保有歐式的風格 就像電影的場景一般 書房 高級的餐廳，不過不能點菜 那個時代的家具看起來還真是高級 這是…下午茶？ 在附近吃完飯後，又朝著一滴水紀念館前進，途中經過這裡順手拍了一張，不過後來沒有進去 一滴水紀念館 地址：淡水區中正路1段6巷30號 電話：(02)2626-3350 實際上一滴水紀念館是在和平公園裡面 和平公園紀念碑 公園中的造景 ...

資訊 路徑：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 ...