#93 平衡樹系列 - AVL Tree

在前面的資料庫文章裡曾介紹過 B-tree，一種平衡的搜尋樹，利用樹狀的結構來達成快速尋找的目的，而且因為是平衡的，所以從 root 出發到每一個樹葉的尋找成本是一樣的，這也是必要的，畢竟資料庫引擎用公平的方式來對待所有的資料．然而，B-tree 的結構並非是 binary 的型式，因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態．在前幾篇的文章也談過了 binary search tree，若你看過的話，你會清楚地知道 binary search tree 和 binary tree 的不同．在 binary search tree 裡，因為在建立樹的過程中有一個很重要的特性，就是右邊子節點的值大於父節點，左邊子節點的值小於父節點，因此在建立樹或是尋找節點時，到達一個節點時，只需要選擇其中一邊，不是左邊就是右邊，所以也達到...

閱讀全文

#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子，我的小徒弟去報名他人生第一次的 APCS 考試，可以說是他學習電腦科學以來第一次的正式上機考試．一共有四題的程式設計題目，前面兩題算是簡單的，第三題算中等，第四題比第三題再進階一點點．這篇文章就來談談第三題的解題思考．完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ，首先，要解題之前，請先確定自已己經百分百了解題目．這一個題目的解決過程可以分成下列 2 個部份,1. 讀取輸入參數，因為輸入參數並非按照切割次序而輸入的，我們要進行切割時是按照次序來切割的．因此，我們必須對輸入參數做處理，以讓沒有次序的參數集合變成有次序的參數集合．2. 每一次切割時，都需要知道左右兩端的長度，這樣才能算出該次切割的費用，而知道左右兩端的長度，這需要一個快速的行為才能符合題目的要求．因為題目提到切割次數最多會到二十萬次，並且棍子的長度可以到...

閱讀全文

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料，目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下，因此，希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考. 一般來說，我會把履歷表的寫法分成兩種，一種是屬於年輕工程師的寫法，另一種是資深工程師的寫法，我將年資不到十年的人定義為年輕工程師，所以可能是在 32 - 36 歲之間，就看你在幾歲從學校畢業．在這年資以下的人，撰寫履歷表時應該要著重在技能的部份．也就是說，你得在履歷表上說明你用過了那些工具與方法來製造軟體系統，以及你運用了那些專業知識 (課本上學的) 在你的工作上．比如，某個年輕工程師從事電商系統前端功能的開發，屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西，是否用到其他的 framework，如...

閱讀全文

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多，這一篇文章來說明其中一種應用，Maximun subarray sum．這個問題是在一個整數的 array 裡找一個連續空間的元素，其元素的總和的值是最大的．如下圖: source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/從 index 2 到 index 6 之間的元素總和等於 7，這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難，因為用最直接的暴力法就可以解決了，其程式結構如下: ...

閱讀全文

#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...

閱讀全文

#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 的觀念．一個健全的社會裡都是有這樣的現象．因此，身為團隊領導者的你首先必須思考一件事情，你需要什麼程度的軟體工程師．在你設定下了一個範圍之後，接下來的問題便是該如何衡量一個軟體工程師是否適合．以下是我的做法，已經行之有年了，這些做法並不是我發明的，只能說是被...

閱讀全文

#84 程式設計的簡約格式 - 減少程式碼縮排

最近在 code review 的過程中，總是常常會看到一些令人驚喜的事情，其中一件事情和程式的寫法有關．有時候是邏輯可以在簡化，有時候是 coding style 上可以在簡化以便閱讀．首先來看 coding style 可以簡化的部份．在寫程式的過程中，有時會因為業務邏輯面的複雜而造成會寫出多個 nested if statements 的情況，如下面的例子 This file contains bidirectional Unicode text that may be interpreted or compiled differently...

閱讀全文

#83 最近搜尋清單資料結構

最近遇到一個特別的需求有關一種像 Queue 但又不是 Queue 的資料結構 需求如下: 1. 可以自訂清單數量大小 2. 內容一筆一筆的存放，但讀取時是後進先出 3. 如果存放時，該資料已存在，則讀取時它會先被讀取. 舉些實例來說明 以下為動作順序 Initialize as size of 5 Set 1 Set 2 Set 3 GetItems() ==> 資料是 3,2,1 Set 4 Set 5 GetItems() ==> 資料是 5,4,3,2,1 Set 6 Set 7 GetItems() ==> 資料是 7,6,5,4,3 Set 5 GetItems() ==> 資料是 5,7,6,4,3 Set 3 GetItems() ==>...

閱讀全文

#82 K個最近鄰居演算法 (k-nearest neighbor algorithm, KNN)

在大部份的科學領域裡都蠻注重分類 (Classification) 這件事．透過分類，它能幫助我們整理問題，也能整理答案，甚至在不同的問題集合裡找出通用的答案．在人工智慧的領域裡，有一門科目叫模式辨認 (pattern recognition)，它應用在影像辨識，人臉辨識，語言辨識等的範圍，其中需要一個重要的技能就是將所要辦認的物件做分類，然後在該分類裡找出合適的對應結果．在這過程中，k-nearest neighbor (KNN) 是一種相對古老且直覺的方法．方法簡單而且能有高準確率，並且不需要所謂的 “訓練”．在人工智慧的領域裡，簡單而言，做的事情就是收集資料，然後依這些資料整理出一個數學模型，未來有新資料出現時，就可以丟入這數學模型加以運算，得出來的結果就是此模型的預測結果．KNN...

閱讀全文

#81 出神入化的用介面 第四集 修改共用的介面 part.2

這一篇文章是上一集的延伸，再來說明新版本 interface 的後續實際使用的情況．先將此篇文章要解決問題再描述一次．想像一家公司出版了一套軟體，而這個產品裡包含了許多的元件檔案 (.dll)，而且每一個元件是由不同的團隊產生．每個元件可以有獨立的發行時間，也就是說當 A 團隊要釋出新功能的版本時，他們可以自行釋出．在客戶端裡，可以透過該軟體裡的更新程式來下載並且安裝 A 團隊所製做的新版本元件．由於各元件釋出的時間並非一致，因此元件之間的互動將變得有挑戰性． A 團隊裡的某些功能是透過 B 團隊的元件所完成的．例如，A 團隊提供的功能裡有一項是計算產品折扣，而這項功能的細節實作者其實是 B 團隊，因此 B 團隊會提供 interface component 給 A 團隊使用，如: ...

閱讀全文

#80 寫程式的參考準則 (coding guideline) - C# 篇

曾有一些朋友問我，在微軟公司裡是否有寫程式的準則 (coding guideline)．這件事因不同的團隊而異，大部份的團隊都會依循 MSDN 文件裡的建議，但並非每一個團隊都有文件記錄這些準則．以前我在 Windows 部門裡的某個團隊就正好有文件說明 C# coding guideline．除了 C# coding guideline 以外，還有其他的文件，例如 code review 文件, database 開發文件等等．在這篇文章中，我將從 C# coding guideline 開始寫起．這些 coding guideline 不是什麼秘密，很多都是來自 MSDN 的文件．若你的團隊也需要一份 C# coding guideline, 希望能派的上用場． 1. 在一份 C# 原始碼裡，別有...

閱讀全文

#79 貪心策略 - Greedy (2)

上一篇文章談了貪心策略的基本想法，但並沒有提到任何的程式碼來說明貪心策略是怎麼進行的．其實貪心策略並沒有一個很明顯程式碼撰寫方式，如果硬是要湊出一個程式碼外型的話，我覺得它的長相可能如下: while ( 依問題條件來決定是否要繼續下一步 ) { // 1. 依照問題，在這一個步驟裡取得最佳解 // 2. 根據步驟一得到的最佳解來決定程式的下一個狀態 // 3. 將程式目前的狀態移動到下一個狀態，下一個狀態將會更接近最終的答案 } 老鼠走迷宮是很典型資料結構 Stack 作業，它的內容是假設一個方形的土地，這土地用畫分成許多面積相等的小格子，就像棋盤那樣．每一個格子都是一種地形，如山，河，平地．老鼠只能走平地，不能爬山也不能過河．老鼠將從起點走到終點，起點是在這土地的左上角，而終點是在右下角．這個作業就是要讓老鼠能走出一條路從起點到終點．如果沒有路存在，則最後的答案是...

閱讀全文