資料結構 - 二元樹 (Binary Tree)
簡介二元樹 (Binary Tree) 是資料結構中樹狀結構的一種，也是常使用的一種資料結構，很多其他的樹種也是基於二元樹發展出來，所以是很重要的一種資料結構。 定義二元樹顧名思義是指每個節點都最多只能有兩個分支，所以會看起來這樣： 而比較嚴謹的定義如下： 每個節點最多有兩個子節點。 子節點有左右之分。 當然原來樹的定義也是要繼承下來。 在二元樹中也定義了一些專有名詞，解釋如下： 完滿二元樹 (Full Binary Tree)或翻譯滿二元樹，每個節點有 0 或 2 個子節點。也稱作嚴格二元樹 (Strictly Binary Tree)、正規二元樹 (Proper Binary Tree) 或 2-tree。範例如下： 大多數的中文資料對完滿二元樹的定義相當於英文的完美二元樹。 完全二元樹 (Complete Binary Tree)除了最後一階層之外的階層都必須填滿，而最後一階層的節點必須由左至右填入。範例如下： 完美二元樹 (Perfect Binary Tree)同時滿足完滿二元樹的條件，並且所有的葉節點都在同一個階層。範例如下： 在這個定義下可以得知，完美二元樹也必定是完 ...
網頁開發人員工具
開發人員工具之前的文章提到，早期開發 JavaScript 要進行 Debug 並不容易，不過現在的瀏覽器大多都已經有內建的開發人員工具，能夠讓我們方便的進行觀察 DOM 元素和 CSS 屬性等不同的功能。 這邊介紹一些常見的瀏覽器如何使用除錯模式來進行開發工作。 ChromeChrome 瀏覽器內建開發人員工具，可以從功能選單中開啟或者直接按熱鍵 F12 即可開啟，畫面如下： SafariSafari 瀏覽器雖然內建了開發人員工具，但預設是關閉的，所以要先進入選單的偏好設定，在進階的標籤下勾選 [在選單列中顯示 “開發人員” 選單]。 之後一樣可以從選單中開啟，或是按右鍵的檢視元件，或是直接按熱鍵 Ctrl + Alt + C 開啟，畫面如下： FirefoxFirefox 瀏覽器需要額外安裝 Firebug 的擴充套件，從選單的附加元件進入管理畫面，搜索 Firebug 後安裝即可使用。 除了可以從畫面社找到 Firebug 的圖示開啟之外，也可以直接使用熱鍵 F12 開啟，畫面如下： OperaOpera 有內建的開發人員工具，可以按右鍵選擇檢查元件開啟或是使用熱鍵 Ctrl + ...
資料結構 - 樹 (Tree)
簡介樹 (Tree) 是一種常見的資料結構，他是一種階層式 (Hierarchical) 的資料集合，我們就先來看看下面這棵樹： 我們觀察這棵樹之後可以發現他由某些東西組成，包含樹葉、樹枝和樹幹；同樣地，在程式世界裡有著類似的對應，樹的最開始會有一個根節點，就像樹的樹根一樣，所有的資料都是由這裡開始發展，接著會有一些其他的節點，有些節點可能在最末端，稱之為葉節點，就像樹的樹葉一樣，其他的節點則像樹的樹枝一樣。 不過在程式世界裡面，我們習慣把根節點放在最上面，而在我們生活中其實也很常使用，像是組織圖： 上圖的區長為根節點，最下面的各單位則為葉節點。 定義在數學的圖論和資料結構所提到的樹其實有些差異，在這裡先說明兩者的不同，數學中對樹的定義這裡簡化如下： 圖中任兩點存在一條路經相通，但不存在環 (Cycle)。 不過在資料結構裡面所說的樹，指的是數學裡的有根樹 (Rooted tree)，定義如下： 有一個特殊節點為根節點的樹。 在資料結構中的實作會有父節點和子節點的分別，所以可以進一步的定義： 樹存在一個為根節點，根節點沒有父節點 (不可以有迴圈)。 每個節點只有一個父節點 ( ...
JavaScript 教學 - 基本語法 (Syntax)
介紹 JavaScript 中的基本語法與使用方式，包含執行 JavaScript、在 HTML中 嵌入 JavaScript、註解與其他特性。 如何執行 JavaScriptJavaScript 最常使用在網頁上，所以基本上所有瀏覽器都可以用來執行 JavaScript 程式，我們簡單的建立一個網頁，例如 hello.html，如下： 12345678910111213<!DOCTYPE html><html> <head> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta charset="utf-8"> <title>Hello World!</title> <script> document.write('Hello world!'); </script> ...
演算法 - 選擇排序法 (Selection Sort)
簡介選擇排序法 (Selection Sort) 是排序演算法的一種，也是一種簡單容易理解的演算法，其概念是反覆從未排序的數列中取出最小的元素，加入到另一個的數列，結果即為已排序的數列。運算流程如下： 從未排序的數列中找到最小的元素。 將此元素取出並加入到已排序數列最後。 重複以上動作直到未排序數列全部處理完成。 流程示意圖： 然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地 (In-place) 的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。從未排序部分找到最小的元素，利用交換的方式將元素放置已排序部分的尾端。運算流程如下： 從未排序的數列中找到最小的元素。 將此元素與已排序部分的尾端元素進行交換。 重複以上動作直到未排序數列全部處理完成。 流程示意圖： 選擇排序法的比較複雜度固定是 O(n^2)，不過交換次數則是 O(n)，在最佳情況可以到 O(0)，比起氣泡排序法的比較次數少很多，所以效能上會比較好。 分析 最佳時間複雜度：O(n^2) 平均時間複雜度：O(n^2) 最差時間複雜度：O(n^2) 空間複雜度：O(1) Stab ...
TopCoder Inv 2001 Semi A+B - ChessCover
資訊 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ ChessCover 分數：1000 題目說明在西洋棋中要避免你的 King 被攻擊，現在撰寫一套程式，系統輸入棋盤目前狀態，程式要從棋盤上找出安全的位置並回傳有多少個。棋盤上會出現以下五種棋子： Queen：可以攻擊八方位直線。 Rook：可以攻擊上下左右直線。 Bishop：可以攻擊斜角四方位直線。 Knight：可以攻擊 L 位置 (類似象棋馬的日字形)。 Pawn：可以攻擊斜角四方位一格。 如下圖所示： 12345678 Queen Rook Bishop Knight PawnX + + X + + X + + + X + + + X + + + + + X + + + + + + + + + + + + + ++ X + X + X + + + + X + + + + X + + + X + + + X + X + + + + + + + + ++ + X X X + + + ...
演算法 - 插入排序法 (Insertion Sort)
簡介插入排序法 (Insertion Sort) 是排序演算法的一種，他是一種簡單容易理解的排序演算法，其概念是利用另一個數列來存放已排序部分，逐一取出未排序數列中元素，從已排序數列由後往前找到適當的位置插入。運算流程如下： 從未排序數列取出一元素。 由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。 重複以上動作直到未排序數列全部處理完成。 流程示意圖： 然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地 (In-place) 的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。在與已排序的部分比較時，利用指派 (Assign) 的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。運算流程如下： 將未排序的部分最左邊元素儲存到暫存變數。 由後往前和已排序部分元素比較，若比自己大則將該元素往右邊位移。 重複2的動作直到遇到不大於自己的元素，將暫存變數寫入在該元素之後；若都沒有則寫入在最前面。 重複以上動作直到未排序部分全部處理完成。 流程示意圖： 分析 最佳 ...
演算法 - 氣泡排序法 (Bubble Sort)
簡介氣泡排序法 (Bubble Sort) 是最容易理解和實作的一種排序演算法，也翻譯作冒泡排序法。由於它很容易學習，所以也是許多演算法課程中第一個學習的排序演算法。 由於他的演算法過程會將最大的數值移動到陣列最後面，而較小的數值則逐漸的往陣列前端移動，就像有許多氣泡慢慢從底部浮出，因此稱為氣泡排序法。他的運作流程如下： 比較相鄰的兩個元素，若前面的元素較大就進行交換。 重複進行 1 的動作直到最後面，最後一個元素將會是最大值。 重複進行 1, 2 的動作，每次比較到上一輪的最後一個元素。 重複進行以上動作直到沒有元素需要比較。 流程示意圖： 實作上直接使用迴圈就可以很容易的完成。另外可以使用額外的旗標 (Flag) 來判斷這一輪是否有發生交換情形，若都沒有發生交換表示數列已經是排序好的，即可跳出迴圈，因此最佳時間複雜度是有可能達到 O(n)。 分析 最佳時間複雜度：O(n) 平均時間複雜度：O(n^2) 最差時間複雜度：O(n^2) 空間複雜度：O(1) Stable sort：是 虛擬碼一般版本1234567891011function sort(list) // 重複 N ...
排序演算法 (Sorting)
簡介排序 (Sorting) 演算法是常用到的一種演算法，顧名思義他是用來將資料依據特定的規則做排序後輸出；既然稱為排序就會有一個比較順序的依據，例如數字就比較數值大小、字串則依 ASCII 字母順序或者物件會有自定義的規則。一般沒有特別指定的話，輸出是以遞增排序為準。 穩定排序排序演算法分為穩定 (Stable) 和不穩定 (Unstable) 兩種，是指當資料中有相等數值的兩元素，經過排序之後是否能夠保持原有的相對位置，例如： 1(猴子, 智商60) (丁丁, 智商20) (拉拉, 智商20) (路人甲, 智商90) 將這些資料依據智商來排序，會發現智商 20 的有兩位，因此我們可能得到以下兩種情況 12(丁丁, 智商20) (拉拉, 智商20) (猴子, 智商60) (路人甲, 智商90)(拉拉, 智商20) (丁丁, 智商20) (猴子, 智商60) (路人甲, 智商90) 第一種情況丁丁和拉拉與原始的相對位置一致 (丁丁在前)，能夠總是維持相對位置的排序法我們稱之為穩定排序，反之則稱為不穩定排序，不能確保相對位置與原來一樣 (但是也有可能一樣)。 如果是純數字的排序基本上是 ...
TopCoder Inv 2001 Semi A+B - Tothello
資訊 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ Tothello 分數：500 題目程式介面12345Class Name: TothelloMethod Name: bestMoveParameters: String[], String[], StringReturns: intMethod signature (be sure your method is public): int bestMove(String[] redPieces, String[] blackPieces, String whoseTurn); 說明Tothello 是一個 Othello 遊戲的修改版，Othello 是一種兩人玩的遊戲，一方使用紅色的棋子，一方使用黑色的棋子，輪流在一個 8x8 大小的棋盤上下棋。當一方下棋之後，如果有將對方的棋子兩端包夾起來，對方的棋子就會變成自己的棋子；而若有棋子變成自己的棋子後，又產生其他的包夾，則又可以變成自己的棋子，直到沒有任何包夾。另外自己的回合的時候，也可以選擇 Pass 不下棋。 現在請實作一個程 ...
