#89 淺談 Dynamic Programing (1)

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 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上，我們會為這個 number 定義起始點，也就是說第 1 項和第 2 項的值是早被確定的，往後的項次皆由這兩項為基礎而算出來，所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ，那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時，就按以上的方法一直算到第 n 項就能得到答案. 接著，數學公式 F(n) = F(n-1) + F(n-2) 寫出來了，那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式．這一個程式碼沒有使用額外的記憶體空間，所以 space complexity 是 O(1)，但仔細看一下 time complexity，卻發現超乎想像的大，因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是，當程式在 F(5) 那一個層次要往下呼叫時，程式會呼叫自己兩次，並傳送 4 和 3 為輸入參數，當第一個 recursive call 再進去時，又會再呼叫自己，並傳入 3 和 2 為輸入參數，以此類推．所以你可以看的出來，有許多重覆的計算在這 recursive 的過程中一直發生．以上圖來說，F(3) 發生了 2 次，F(2) 發生了 3 次．當 n 是一個大的數字時，你就可以發現比 n 越小的數字，重覆計算的次數越多，並且是以指數趨勢來增加．上述的程式碼雖然很簡單，但是 time complexity 卻是很可怕的．上述的程式碼是由上而下計算下來的，假設我們繼續用由上而下的計算方式，改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算．如上圖，如果 F(3) 只真正地被計算了一次，而 F(2) 只真正地被計算了一次，那麼就不會有重覆計算的事情了．為了達成這目標，最簡單的方法便是把計算後的結果儲存下來，等到要計算一樣的內容時，去 "查表" 即可．也就是說第一次 F(3) 計算的結果儲存下來，當程式遇到第二次的 F(3) 時，直接去查詢，若有答案，直接將答案拿來使用，這樣就不用計算了．同時，為了確保不會造成過多的 time complexity，我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小，如 O(1)．這種 "查表" 的精神也是 dynamic programming 所代表的策略．

若將上述的程式碼加入 "查表" 的功能，它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣，但都是用了一個 array 來記錄每一個項次計算的答案，因此 time complexity 省下來了，而且 space complexity 也增加了，但這樣的空間增加似乎是值得的．當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小，不過這並不是這篇文章的重點．透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼．許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的，例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來．

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神，這是相當簡單的例子，下篇文章我們用較難的例子來說明 dynamic programming 的用法.

閱讀全文

#88 資訊工程系的大學先修考試 APCS

在美國加拿大的大學入學測試中心成立了一種測驗，名為 Advanced Placement，裡面分成多個不同的專業考試，主要用來測驗高中生在該專業領域的 "程度" 如何．這些專業領域如生物，歷史，物理，語言，統計等等，其中電腦科學也是其中一個專業領域．簡單地說，就是要測驗那些資優班的高中學生，當他們申請大學時，可以附上 Advanced Placement 的成績用來代表他們有多少的能力在這些專業領域裡．詳情可參考 https://en.wikipedia.org/wiki/Advanced_Placement

在數年前，台灣教育部也發動了一樣的計畫，其中電腦科學的專業是由台師大資工系來執行，詳情可參考 https://apcs.csie.ntnu.edu.tw/

到今年 2020 為止，大部份在台灣有比較好的資工系學校都會參考這個成績，並且設下了門檻，例如台大資工要求觀念題和實作題都要達到 4 級分以上．這個考試結果一共分為五級，依照學生答案的內容來分級．若要達成 4 級分的話，基本上要熟練一個程式語言，如 C++，並且會用基本的資料結構，如 Array, List 等，除此之外，還要知道如何寫 recursive code 來解決問題，例如 binary search 等．對於正在讀文章的你，可能已經工作多年，這些並不是什麼難事，但對一個高中生，除了要面對高中的課程，還要花時間學習這些 "課外讀物"，這的確不是件容易的事. 在師大的 APCS 網站裡，提供了歷史考題．我會在這網站裡貼出參考答案. 如果你是打算以後念資工系的高中生，或是你們家有這樣的高中生，歡迎你分享給他們.

程式實作題: 三角形辦別

日期: 2016/10/29

參考答案

程式實作題: 矩陣轉換

日期: 2016/3/5

參考答案

以上的答案是 C++ 搭配 STL，答案並不是我寫的，是我一位小徒弟寫的答案，他在二個月前剛升上高一，以他目前的能力要應付台灣 APCS 題目算輕鬆．我這位小徒弟是個小學霸，以後再來介紹我是如何訓練他電腦科學的知識.

以上兩題對於已經在工作的你來說應該都是很簡單的題目，只是一些基本的數學應用題．台灣 APCS 的歷史題目還有好多題，未來文章會介紹.

閱讀全文

#87 Binary Search Tree 簡介

在 "資料結構" 系列文章裡寫過了 Binary search ，也寫過了 Tree．Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找．Tree 提供我們一個資料儲存 (放置) 的結構，當這兩個碰在一起時，產生了一個相當有用的資料結構.

Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老，它出現在 1960 年代，在那個電腦硬體仍不太發達的年代，這個超級有用的資料結構就被發明出來了．誠如之前談的 binary search 內容，當你要進行 binary search 時，有一個很重要的前提就是被尋找的資料需要以某種排序好的順序存在，不論是從小排到大，從大排到小，或是從中排到小，再排中排到大，只要是資料依照某種屬性而排序好，就可以進行 binary search. 它的尋找資料的時間複雜度也在前面文章提過了，是 O (log N) 的複雜度，因為每一次尋找都可以捨棄掉一半非尋找目標的資料，這對尋找是個很大的幫助．然後，別忘了剛剛說的前題，資料必需是以某種方式排序好的．若你要在一堆沒有排序好的資料，把它排序，再執行 binary search 來找資料的話，這顯然有點過頭了，因為光是較快的排序都要花費 O(nlogn) 時間．因此在使用 binary search 之前，資料已是排序好的方式存在則能馬上使用 binary search，

當要讓資料以某種排序的方式建立起來時，可想而知，在建立的過程中可能要花費較多的時間，畢竟這不是隨便把資料加上去就好，而是要找到一個適當的位置才能加上去，以維持排序的狀態．你可以想像一個 integer single link list ，當你要加資料進去時，你得找到適當的位置並執行 insert 的動作，如下圖所示:

因此，只要我們能找一個適合的資料結構將資料依排序的目標建立起來，binary search 就可以派上用場. 在 Tree 的應用裡面，有個基本的結構叫 binary tree，也就是每個樹節點除了資料本身的空間外，還有另外兩個空間，一個是指向左邊節點的空間，另一個是指向右邊節點的空間. Binary tree 本身並不涉及任何資料排序的概念，但若我們為它加上一個限制，資料大的往右邊節點方向去建立，而資料小的往左邊節點方向建立，那麼這個 binary tree 便存在了排序的特性，如下圖所示，在任一個樹節點上，若左邊存在一個節點，則左邊節點的值將比較小，同理，右邊節點的值將比較大.

當 binary tree 加上了 "順序" 的特性時，這時就稱它為 binary search tree. 當尋找資料的動作發生時，從 root 開始出發，假設我們在上圖的 binary tree 上找 44，我們會在 root node 往右邊走，因為 44 > 11．以此類推，只要經過兩個樹楖點，我們便能找到 44. 如前面所說，這個動作的時間複雜度是 O(logn). 在大部份的應用裡，這個速度已經夠快了．

此時，你可能會發現在 binary search tree 要找資料時, root 的值是很重要的，因為你可能會看到如下圖的情況,

如上圖，倘若我們選到了一個不適合的值來當 root 時，此時 binary search tree 就長 "歪" 了．所謂的歪並不是壞掉的意思，而是大量傾向某一邊造成不平衡的情況．所謂的不平衡的意思就是某一樹節點左邊的 subtree 和右邊的 subtree 在高度上有大的落差．這會造成搜尋成本的不平均．比如，若你要找 44，它剛好是 root，所以一下子就找到了，若你要找 7，中間要經過 44 -> 33 -> 11 -> 6 ，最後到 7，若是你要找 11，中間經過 44 -> 33 就到 11. 所以，每個節點被找到的成本存在的大差異，因為我們稱之為不平衡的樹．這是我們希望能避免的情況，畢竟你希望的是每一個資料在被尋找時，每個資料被找到的時間成本和平均成本是很接近的，這樣才是公平．倘若資料本身需要不公平的情況，那就另當別論了.

Binary search tree 幫助我們將資料能用某一種順序的方式儲存起來，並且在尋找時也能達成 binary search 的效果．有些程式語言的程式庫裡都會提到這一個好用的資料結構，例如 C++ 的 map 就是典型的 binary search tree 實作. 如果你常用的程式語言裡沒有提供 binary search tree 的實作，我強烈建議你應該要在網路上找找是否有其他人做好成熟度夠高的實作，因為 binary search tree 的應用實在很多而且很好用. 當然 binary search tree 並無法為你自動達成 "平衡"，所以才會有其他的資料結構產生用來解決這個平衡的事情，如 AVL tree, red back tree, B tree 等等. AVL tree, red black tree, B tree 也算是蠻有用的資料結構，不光是學術價值，其工業應用價值也是頗高，以後會寫文章來介紹它們.

閱讀全文

#86 貪心方法是最佳解 ?

最佳解? 這種解答是許多問題所追尋的目標．例如，在一個城市裡找到出發點和目的地的最短距離．直覺來看，若你沒有把所有可能的路徑列出來，你怎麼知道那一個才是最短的．再舉例一個例子，在一個 int array 裡面，找出最大值的元素位置．若你沒把所有的元素都拜訪一遍，你怎知道那一個才是最大的．這兩個例子雖然都是在找 "最佳解"，但是解法的思考卻不太一樣．第二個例子的思考是 "一條路"，而第一個例子是 "多條絡"．在 "一條路" 的情況下，對下一個步驟來說沒什麼好選擇的，只能一直往前走．然而，"多條路"的情況下，在什麼路口選擇什麼路，這對答案或執行過程會有很大的影響． 

前面已有兩篇文章簡單地介紹了貪心方法．這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試．假設郵局提供的郵票面值如下:

$10, $5, $2, $1, $0.5, $0.2, $0.1 

現在你要寄一封信，它所需的郵資是16.1 元，請問最少要用幾張郵票 ? 這是一個最佳解的問題，目的是要找最少的郵票數量. 使用貪心方法來解這問題，它所需的程式碼如下:

以上的程式範例就是一個貪心方法．從最大的面值一直嘗試到最小的面值，一直湊到超過所需要賺買的郵票面值. 得到的答案是 $10, $5, $1, $0.1，需要四張郵票，面值是 10, 5, 1, 0.1 剛好能湊到 16.1，並且也這麼湊巧，四張郵票剛好是最佳解.

如果把郵票的面值改變，新的郵票面值有 

$5, $3.7, $3.1, $2.9, $2.3, $2, $1.7, $1.3, $1, $0.5, $0.2, $0.1

當我們再用同樣的程式去執行時，得到的答案會是 $5, $5, $5, $1, $0.1 ，需要 5 張郵票．但你認真排列之後，你會發現有一個更好的答案，那就是 $5, $3.7, $.3.7, $3.7，只需要 4 張郵票即可．此時便可發現貪心方法並無法保證我們一定能夠得到最佳解．如果得到最佳解，只能說題目本身的特性剛好能讓貪心方法得到最佳解而己．

從第一個問題來看，最佳解的答案有幾個特性

1. 答案最多一個 $0.1，因為若有兩個以上的 $0.1，便可以用 $0.2 來替代．

2. 答案最多兩個 $0.2，因為若有三個以上的 $0.2，便可以用一個 $0.5 和一個 $0.1 來替代.

3. 答案不會存在兩個 $0.2 和一個 $0.1，因為可以用一個 $0.5 替代.

還有一些其他的特性可以類推而得．同時，第二個問題可以用同樣的方式來找出最佳解的特性．第二個問題的其中一個特性就是，不該出現兩個 $5, 一個 $1 和一個 $0.1，因為可以用三個 $3.7 來替代，所以我們用貪心方法所得到的答案便不會是最佳解．

閱讀全文

#85 如何聘用適合的軟體工程師

如果你是一個團隊的領導者，尋找適合的軟體工程師一定是你份內工作裡不會缺少的一項任務．我這邊採用 "適合的軟體工程師" 而不是用 "優秀的軟體工程師"，其主要原因在於每個團隊的任務與能力不同，所以無所謂的優不優秀，只要是適合的人，對你團隊來說都是優秀的．

人們常說 "物以類聚"，這句話適用在許多人類的活動裡，對於建構一個軟體開發團隊而言，其實也是適用的．真正優秀的工程師對於技術含量低的工作通常不見得感興趣，相同地，能力不好的工程師也無法在技術含量高的團隊裡存活下來．這些原因可能來是一個現實的條件 - 薪資．

一般而言，薪資高的工作對於工程師的品質也會要求較高，相同地公司付出的薪水也會比較多．這是一個很簡單的經濟學原理 Supply-Demand 的觀念．一個健全的社會裡都是有這樣的現象．因此，身為團隊領導者的你首先必須思考一件事情，你需要什麼程度的軟體工程師．在你設定下了一個範圍之後，接下來的問題便是該如何衡量一個軟體工程師是否適合．

以下是我的做法，已經行之有年了，這些做法並不是我發明的，只能說是被 "同化" 後的結果.

1. 設定基本功夫的內容

既然是從事軟體開發的工作，你得先確保來面試的人具備基礎的資料結構與演算法的頭腦. 若是你資工相關科系畢業的，你應該能明確深刻的體驗到軟體工程師的工作就是將專案中的問題轉換成程式可以操作的模型，然後在電腦的架構下，不斷地在這些可操作的模型上做 "資料處理" 的動作，最後將結果產生出來．在這過程中，了解資料結構是一件非常重要的基礎．你可以從前面的文章裡了解到一個軟體工程師對資料結構的熟悉度將決定了程式的好壞 (Time complexity and Space complexity)，最終將會影響到整個專案的品質．

如果你團隊的工作是一般簡單的資料處理網站，使用者在表單上輸入資料，然後在其他表單上輸出資料．類似這樣的工作，你至少得確認你的軟體工程師懂得 Array, List, Stack, Queue, Hash table 這些基本的資料結構以及相關的應用．如果你團隊是製造一個資料庫引擎，那麼 Tree/Graph 的操作與相關應用將會是你團隊裡所需要的最基本的功夫．

透過考試來了解面試者的情況是最快速的方法之一．但我通常不建議拿一般市面上的考題．我建議的方式是準備一個在你過去的專案經驗裡值得拿出來當考試的題目．這是一個真實世界的問題，所以題目內容是容易能面試者明白為什麼是這種考題，同時也能讓面試者體會到未來有機會進來工作時，面對的情況這類似是這樣．通常準備一個簡單的和一個難的題目．

2. 設定操作工具的熟練度內容

世界上有許多程式語言以及相關許多不同的產品與工具．如果你需要的是一個可以盡快上戰場協助團隊的軟體工程師，那麼你便需要確保來面試的人員具備相關工具的知識與熟練度．例如，團隊的工作裡需要大量用到 Visual Studio/Microsoft SQL server 來進行專案開發，則你必須確認面試的人們對這些工具是熟悉的．最簡單的方法就是上機考．透過上機考的過程，你便可以清楚知道面試者對一個工具操作的熟悉度是在什麼程度．

3. 設定其他所需知識的領域

若專案是用關聯式資料庫做為 repository 時，你必須確定面試者具備 ER Model 的知識以及相關的知識，如 Index 的設計等. 若專案是用物件導向的方法來開發時，你必須確定面試者明白什麼是 class, object, 以及其他物件導向的原則與應用．同樣地，透過考試是最能直接明白面試者的情況．我在這邊也是給相同的建議，那就是考試的內容最好是團隊過去所面臨過的情況，分別找出簡單與難的問題來做為面試題目．

4. 設定人格特質

每個團隊都有一種 "文化"，這種文化的事情實在困難說清楚，而這種文化確會大大地影響整個團隊的產出和品質．身為團隊領導者的你必須了解到團隊的文化是什麼，然後將這些文化融入在團隊的運作過程中．比如，沒有經過 review 的 code 不能 check-in source control, 沒有加上 unit test 的 function 不能 check-in source control．類似這樣的事情讓面試者了解到團隊運作是有規則地運行．因此，態度散漫或不夠嚴謹的人自然無法能適應這種文化．

分享一個以前的經驗，我多年前參加一個公司內部的面試，面試的過程中，那位老闆不斷地提出許多問題來轟炸我的思緒，除了看我的反應以外，也看我能不能耐住性子來穩健地解決問題．他們團隊的工作是一個線上問題支援的網站服務，所以工程師們必須 on-call 並且有抗壓的能力.

一個適合的軟體工程師除了要寫出符合團隊期待的程式碼品質以外，還要執行團隊所規定用來幫助便於軟體管理的事情．要盡量讓一切的團隊活動都是在可受控的範圍內，這是團隊領導者非常需要的．

最後，找工作是緣份，找到適合的軟體工程師也是一種緣份．千萬別為了補滿工程師的人數而濫芋充數，因為最後倒霉的將是整個團隊，這是團隊領導者最需要注意的事情之一.

閱讀全文