Dynamic programming 是大學部演算法課程裡相當重要的一個主題，也是典型用空間換取時間的策略．但奇怪的是，這個策略一點也不 dynamic ，一點也不 programming．老實說，我不知道為何這個策略叫 dynamic prograaming，我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子．Fibonacci number 是以數學多項式來表達的數字集合，以數學式來表達就可以寫成如下:F(n) = F(n-1) + F(n-2) 也就是說求第 10 項 (n=10) 的答案時，你必須要先算出來第 9 項和第 8 項. 如果要求第 1...
#88 資訊工程系的大學先修考試 APCS
在美國加拿大的大學入學測試中心成立了一種測驗，名為 Advanced Placement，裡面分成多個不同的專業考試，主要用來測驗高中生在該專業領域的 "程度" 如何．這些專業領域如生物，歷史，物理，語言，統計等等，其中電腦科學也是其中一個專業領域．簡單地說，就是要測驗那些資優班的高中學生，當他們申請大學時，可以附上 Advanced Placement 的成績用來代表他們有多少的能力在這些專業領域裡．詳情可參考 https://en.wikipedia.org/wiki/Advanced_Placement在數年前，台灣教育部也發動了一樣的計畫，其中電腦科學的專業是由台師大資工系來執行，詳情可參考 https://apcs.csie.ntnu.edu.tw/到今年...
#87 Binary Search Tree 簡介
在 "資料結構" 系列文章裡寫過了 Binary search ，也寫過了 Tree．Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找．Tree 提供我們一個資料儲存 (放置) 的結構，當這兩個碰在一起時，產生了一個相當有用的資料結構.
Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老，它出現在 1960 年代，在那個電腦硬體仍不太發達的年代，這個超級有用的資料結構就被發明出來了．誠如之前談的 binary search 內容，當你要進行...
#86 貪心方法是最佳解 ?
最佳解? 這種解答是許多問題所追尋的目標．例如，在一個城市裡找到出發點和目的地的最短距離．直覺來看，若你沒有把所有可能的路徑列出來，你怎麼知道那一個才是最短的．再舉例一個例子，在一個 int array 裡面，找出最大值的元素位置．若你沒把所有的元素都拜訪一遍，你怎知道那一個才是最大的．這兩個例子雖然都是在找 "最佳解"，但是解法的思考卻不太一樣．第二個例子的思考是 "一條路"，而第一個例子是 "多條絡"．在 "一條路" 的情況下，對下一個步驟來說沒什麼好選擇的，只能一直往前走．然而，"多條路"的情況下，在什麼路口選擇什麼路，這對答案或執行過程會有很大的影響． 前面已有兩篇文章簡單地介紹了貪心方法．這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試．假設郵局提供的郵票面值如下:$10,...
#85 如何聘用適合的軟體工程師
如果你是一個團隊的領導者，尋找適合的軟體工程師一定是你份內工作裡不會缺少的一項任務．我這邊採用 "適合的軟體工程師" 而不是用 "優秀的軟體工程師"，其主要原因在於每個團隊的任務與能力不同，所以無所謂的優不優秀，只要是適合的人，對你團隊來說都是優秀的．人們常說 "物以類聚"，這句話適用在許多人類的活動裡，對於建構一個軟體開發團隊而言，其實也是適用的．真正優秀的工程師對於技術含量低的工作通常不見得感興趣，相同地，能力不好的工程師也無法在技術含量高的團隊裡存活下來．這些原因可能來是一個現實的條件 - 薪資．一般而言，薪資高的工作對於工程師的品質也會要求較高，相同地公司付出的薪水也會比較多．這是一個很簡單的經濟學原理 Supply-Demand 的觀念．一個健全的社會裡都是有這樣的現象．因此，身為團隊領導者的你首先必須思考一件事情，你需要什麼程度的軟體工程師．在你設定下了一個範圍之後，接下來的問題便是該如何衡量一個軟體工程師是否適合．以下是我的做法，已經行之有年了，這些做法並不是我發明的，只能說是被...