【介紹】Code::Blocks

　　為了能撰寫 C/C++ 的程式，你可能需要在自己的電腦中建置一套 IDE（Integrated Development Environment，整合開發環境），卻又不想用需要付費、又只能在 Windows 上執行的 Visual Studio（雖然 VS 也有提供免費的 Express Edition）。

　　或許會有人推薦你使用 Dev-C++ 這套 open source 的免費軟體。不過根據我自己使用過的經驗，Dev-C++ 時常在執行到一半的時候當掉。而且其最新版本 4.9.9.2 是在 2005 年 2 月發佈的，顯然已經好幾年都沒有在繼續更新。

　　在這裡，我要為各位介紹另一款同樣免費又穩定的 IDE - Code::Blocks。


　　Code::Blocks 是一個 open source 的 IDE。由於其是由 wxWidgets 寫成，因此也具備了跨多種平台（Windows、Mac OS X、Linux 等）的能力。

　　Code::Blocks 也支援多種編譯器（compiler），如常見的 GCC / MinGW、Microsoft 的 Visual C++、Intel 的 ICC 等。除此之外，Code::Blocks 還支援匯入 Dev-C++ 與 Visual C++ 專案的能力，可謂功能相當豐富。


　　在這裡簡單示範一下如何在 Windows （XP Pro SP3）下安裝 Code::Blocks。

　　首先，先進到下載頁，找到 Windows 用的 binary 版本。當前的最新版本為 10.05，提供了 "codeblocks-10.05-setup.exe" 與 "codeblocks-10.05mingw-setup.exe" 兩個安裝檔，分別為單純的 Code::Blocks 與包含 MinGW 的版本。

　　在這裡，我選擇的是不包含 MinGW 的版本。


　　下載完成、執行安裝檔後，會出現選擇安裝元件的畫面。基本上，遵照預設值，直接按 "Next" 即可。


　　接著選擇安裝的目錄。


　　接著就可以等待安裝完成了。



　　在 Code::Blocks 安裝完成之後，我們還需要安裝 MinGW 作為其使用的編譯環境。（假如在第一步下載的就是包含 MinGW，這一步可以跳過。當然，你也可以選擇 MinGW 以外的編譯環境，如 ICC。）

　　MinGW 的安裝方式請參見這篇。


　　第一次開啟 Code::Blocks 時，它會請你選擇一個預設的編譯器。後面有寫 "Detected" 的，代表 Code::Blocks 在你電腦偵測到的已安裝的編譯器。

　　這裡我們選擇 "GNU GCC Compiler"。


　　安裝到這邊，就可以開始使用 Code::Block 了！



　　想利用 Code::Block 新增一個 C/C++ 的檔案，請點選選單的 File > New > File...。


　　接著選擇 "C/C++ source"。


　　然後選擇 "C" 或 "C++"。


　　並設定檔案建立的路徑。


　　撰寫完程式，再按下工具列的 "Run" 就可以編譯執行了。

Reference:

• Code::Blocks
• Code::Blocks - Wikipedia
• Writing C++ Application Without Visual C++

展開全文文章收合

【雜記】漫談樹狀結構

　　在之前寫的「樹（tree）」這篇文章中，有網友提到：希望能夠瞭解 tree 能夠在應用上什麼問題上面。不過，由於我本身對樹的瞭解也很粗淺，所以這篇就野人獻曝一下，隨意講講一些我知道的東西。學得不甚透徹，可能會有些不完整或是錯誤的地方，就請各位別見怪囉 :P


　　先前曾經提到：在樹狀結構中，節點（node）的分支度（degree）代表其子節點（child）數量。若是有一種樹狀結構至多只會有 n 個子節點，即樹中的任何節點分支度均小於或等於 n，則我們會將這種樹稱為一棵「n 元樹｣。

　　其中，大概就屬二元樹（binary tree）的應用最為廣泛。如上所述，其節點至多只會有兩個子節點。通常我們會直接將之稱為左子（left child）與右子（right child）。下圖是一棵二元樹：




　　在談應用之前，讓我們先來看看一個樹狀結構常見的操作：尋訪（traversal），也就是依照某種順序訪問樹中的所有節點。一般來說，常見的尋訪方式包含深度優先尋訪（depth-first traversal）與廣度優先尋訪（breadth-first traversal）。

　　以上面的樹狀圖來說明，深度優先尋訪會先從根節點 F 開始，走訪 F 的第一個子節點 B，再接著走訪 B 的第一個子節點 A。由於 A 不具有子節點，所以我們退回上一層，再接著走訪 B 的第二個子節點 D。完整的尋訪順序為：F B A D C E G I H。

　　而廣度優先尋訪相對於深度優先尋訪的不斷深入，是以層級順序（level-order）來進行尋訪。所以同樣由根節點 F 開始，走訪 F 的第一個子節點 B，再接著走訪 F 的第二個子節點 G。由於 F 只有兩個子節點，所以我們接著尋訪下一層 B 的子節點 A 與 D，然後是 G 的子節點 I。完整的尋訪順序為：F B G A D I C E H。


　　其中，二元樹又具有三種特殊的尋訪方式：前序（pre-order）、中序（in-order）、與後序（post-order）。若是把尋訪根節點、尋訪左子樹、尋訪右子樹分別記做 D、L、R，則前序的尋訪順序為 D L R、中序的尋訪順序為 L D R、後序的尋訪順序為 L R D。

　　以同樣的圖舉例的話，前序的尋訪順序為：F B A D C E G I H、中序的尋訪順序為：A B C D E F G H I、後序的尋訪順序為：A C E D B H I G F。（正確來說，二元樹只比一般的樹多了中序與後序兩種尋訪方式，因為前序尋訪與深度優先尋訪的順序其實是相同的。）


　　說完了尋訪，不過跟應用有什麼關聯呢？其中一個常見的用途是排序（sorting）。

　　我們可以定義一個特殊的二元樹：樹狀結構中，其左子樹所有節點所存的值必定小於根節點的值，且其右子樹所有節點所存的值必定大於等於根節點的值。如下圖：



　　有沒有發現，當我們用中序來尋訪這棵二元樹，我們便可以得到一個升序（ascending order）的數列。


　　若是根據定義，給出一個新增節點的操作：

Function insertNode(TreeNode root, Type value)
    If root.value > value then
        If root.hasLeftChild Then
            insertNode(root.leftChild, value)
        Else
            root.leftChild = CreateNode(value)
    Else
        If root.hasRightChild Then
            insertNode(root.rightChild, value)
        Else
            root.rightChild = CreateNode(value)
End

　　利用這個新增節點的操作，我們便可以將一堆資料建立成一棵符合定義的二元樹。於是，我們便可以利用這個操作，在加上中序尋訪來得到一串排序過的資料。


　　事實上，這種特殊的二元樹，被稱為二元搜尋樹（binary search tree）。其義如其名，這種二元樹也可以用以進行「已排序資料」的搜尋（search）。

　　根據定義我們可以得知：若是欲尋找的值小於二元搜尋樹的根節點，則其右子樹必定不可能出現欲尋找的值；同樣的，若是欲尋找的值大於二元搜尋樹的根節點，則其左子樹必定不可能出現欲尋找的值。而這種方式其實就跟二分搜尋法（binary search）的原理有異曲同工之妙。

　　我們可以定義搜尋的操作如下：

Function search(TreeNode root, Type value)
    If root.value = value then
        print "Found"
    Else If root.value > value then
        If root.hasLeftChild Then
            search(root.leftChild, value)
        Else
            print "Not Found"
    Else
        If root.hasRightChild Then
            search(root.rightChild, value)
        Else
            print "Not Found"
End

　　而這種利用二元搜尋樹的搜尋方式，其複雜度為 O(h)。其中 h 為樹的高度（height）。而若每棵子樹的左右子樹節點數量都相同（或差一），則 h 即等同於 lg n，也就是說搜尋的複雜度為 O(lg n)，與二分搜尋法相當。


　　由以上這些例子，可以知道「樹」不僅可以用來處理常見的排序與搜尋問題，還是種挺有效率的方式呢。

References：

• Tree (data structure) - Wikipedia
• Binary tree - Wikipedia
• Tree traversal - Wikipedia
• Binary search tree - Wikipedia
• Tree - 演算法筆記
• 由樹的前序、中序、後序走法來談資料結構 - MMDays
• 二元樹在排序的應用 - MMDays
• 二元樹排序對搜尋的影響 - MMDays

展開全文文章收合

【轉貼】Visualization of Quick sort

　　偶然在網路上看到的影片：用動畫展示氣泡排序法（Bubble Sort）跟快速排序法（Quicksort）的運作原理，並比較兩者的效率（進行比較的次數）。整支影片看起來還滿可愛的。



Visualization of Quick sort 展開全文文章收合

【雜記】FLOLAC '10

　　2010 Formosan Summer School on Logic, Language, and Computation（FLOLAC ’10），是辦在台大進修推廣部的暑期碩士學分班。雖然是碩士學分班，但由於剛好符合相關學系大二以上的報名資格，又在半自願被網友 yen3 「騙來」的狀態下還是報名了XD。




　　對於一個語言，我們可以從兩個觀點來看它：一個是語法（syntax），即語言本身的規則（rule）與形式（form）；另一個則是語意（semantics），為語言本身所表達的意義（meaning）。

　　寫出可以執行的程式也許不難，要寫出正確的程式卻不簡單。當我們得到一段程式，我們該如何分析、驗證這個程式的結果，以確保其確實符合我們的預期？更甚者，我們該如何在撰寫程式的同時，也確保我們建構出來的程式一定是正確的？

　　對於程式語法上的錯誤（syntax error）可以經由編譯器（compiler）或直譯器（interpreter）來幫我們檢查出來。但是，語意上的錯誤（logic error 或稱 semantic error）卻難以經由其他工具來協助我們察覺。

　　一般我們也許習慣利用測試資料來確認程式的正確性：只要程式能通過所有的測試資料（即輸出結果符合預期），我們就可以「假設」程式是正確的了。不過，要產出全面性的測試資料本身有其難度，再加上此種方式必須仰賴於程式的實作（implement），作為驗證並不是一種非常好的方式。

　　而 FLOLAC '10 這一系列的課程，主要的內容就是教導如何以邏輯推理為基礎，從語意的角度將程式形式化（formalize）並進行分析。以及用以輔助的 Frama-C 分析工具的使用。



　　不過 FLOLAC ’10 的時程有兩天跟期末考撞期，所以一開始就請了兩天假。直到第三天的 Logic 跟 Op 課都已經是第二堂課，FP 課甚至已經結束了。要在沒聽過第一堂課的情況下銜接上內容，一開始還真是一個頭兩個大。還好後來漸漸跟上了，總算有種進入狀況的感覺。

　　歷經了兩週八點準時起床出門上課，直到下午五點下課，比暑假前還規律的暑假生活，水深火熱的 FLOLAC '10 終於順利結束了。雖然課程有點辛苦，不過接觸了不少人、也接觸了不少新東西，感覺收獲也相當多。

　　遇見了 yen3、GSR、dryman，還有其他周圍的人、努力想搞懂 Frama-C 到底在做什麼、跟 dryman 一起到麥當勞邊念書邊聊天、期末考前在 Google Wave 上熱烈的討論。對於整個 FLOLAC 的課程，我想我還滿樂在其中的。


　　雖然不知道自己能學到多少，又能應用多少。不過也許就像 yen3 所說：「能體會，就能產生質變」。或許在之後就會發現，現在學過的這些，其實都有潛移默化的作用也說不定。 展開全文文章收合

【演算】插入排序法 - Insertion Sort

　　插入排序法（insertion sort）與選擇排序法（selection sort）類似，同為較簡易、直觀的排序演算法（sorting algorithm）。其原理都是將資料分為「已排序」與「未排序」兩個部份。再將未排序資料中的第一筆資料插入到已排序資料的適當位置。



與選擇排序法相同，一般我們習慣將「已排序」的資料擺在資料序列的前端，並將「未排序」的資料擺在資料序列的後端。

若是我們需要將資料由小排到大。則我們會依序取出每個「未排序」的資料，然後由「已排序」資料的最後一筆開始，往前依序尋找第一個比這筆「未排序」資料還小的元素，並將其後的所有資料往後移一格，再將這筆「未排序」資料「插入」在這個「空出來的位子」。



其虛擬碼如下：

Function insertionSort(Type data[1..n])
    Index i, j;
    Type value;
    For i from 2 to n do
        value = data[i];

        j = i - 1;
        While j >= 1 and data[j] > value do
            data[j + 1] = data[j];
            j = j - 1;

        data[j + 1] = value;
End

讓我們看看實際操作的例子。若是我們需要將以下資料由小排到大：

83 31 96 17 42 14 54

則每一次迴圈的執行結果如下：

83 31 96 17 42 14 54

31 83 96 17 42 14 54

31 83 96 17 42 14 54

17 31 83 96 42 14 54

17 31 42 83 96 14 54

14 17 31 42 83 96 54

14 17 31 42 54 83 96

同樣的，我們必須要分析這種演算法的執行效率如何。

在資料都已排序的最佳情況下，資料大小為 n 的敘述執行次數如下：

Function insertionSort(Type data[1..n])
    Index i, j;                                     // 1
    Type value;                                     // 1
    For i from 2 to n do                            // n - 1
        value = data[i];                            // n - 1

        j = i - 1;                                  // n - 1
        While j >= 1 and data[j] > value do         // n - 1
            data[j + 1] = data[j];                  // 0
            j = j - 1;                              // 0

        data[j + 1] = value;                        // n - 1
End

敘述的執行次數總和：B(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + (n - 1) + (n - 1) = 5n - 3 ∈ Ο(n)。複雜度為線性時間。



但是在資料完全反序的最差情況（註1）：

Function insertionSort(Type data[1..n])
    Index i, j;                                     // 1
    Type value;                                     // 1
    For i from 2 to n do                            // n - 1
        value = data[i];                            // n - 1

        j = i - 1;                                  // n - 1
        While j >= 1 and data[j] > value do         // n(n - 1) / 2
            data[j + 1] = data[j];                  // n(n - 1) / 2
            j = j - 1;                              // n(n - 1) / 2

        data[j + 1] = value;                        // n - 1
End

敘述的執行次數總和：W(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + (n - 1) = (3n² + 3n - 4) / 2 ∈ Ο(n²)，複雜度為平方時間。

平均來說，這種演算法的執行效率並不算高，因此也比較不適合用以處理數量較多的資料。

註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。

展開全文文章收合

【演算】合併排序法 - Mergesort

　　合併排序法（mergesort）是一個典型利用分治法（divide and conquer，D&C）解決問題的例子。其原理為不斷地將資料分成兩等分，直到每份的資料量小到一個程度後，各自排序後再一一合併起來。



　　假設現在有 n 筆資料需要進行排序。

　　則我們首先會將這 n 筆資料分成兩等分（大小皆為 n/2）；接著，再將這兩堆大小為 n/2 的資料各自分為兩等分（大小皆為 n/4）；同樣的，我們再將這四堆大小為 n/4 的資料各自分為兩等分（大小皆為 n/8）。

　　如此進行下去，直到每堆的資料量足夠小（例如：每堆只剩 1 筆資料）之後，我們就分別將每堆資料進行排序，再將這些資料堆兩兩一對進行合併，直到排序完成為止。





　　其虛擬碼大致如下：

Function mergeSort(Type data[1..n])
    If n <= 1 then return

    Index x, y, i, j
    x = n / 2
    y = n - x

    Type left[1..x], right[1..y]
    For i from 1 to x do
        left[i] = data[i]
    For i from 1 to y do
        right[i] = data[x + i]

    mergeSort(left)
    mergeSort(right)
    merge(data, left, right)
End

Function merge(Type data[1..n], Type left[1..x], Type right[1..y])
    Index i, j, k
    i = j = k = 1

    While i <= x and j <= y do
        If left[i] < right[j] then
            data[k] = left[i]
            i = i + 1
        Else
            data[k] = right[j]
            j = j + 1
        k = k + 1

    While i <= x do
        data[k] = left[i]
        i = i + 1
        k = k + 1

    While j <= y do
        data[k] = right[j]
        j = j + 1
        k = k + 1
End

　　讓我們舉個實際的例子說明：現在我們有八筆資料需要排序（由小而大）：

(84、13、73、26、32、19、91、38)

　　且只要每堆的資料量大於 1 時，就需要再將資料進行分割。

　　首先，我們先將資料分成兩等分：

(84、13、73、26)　(32、19、91、38)

　　此時每堆的資料量為 4 (8 / 2) > 1。因此，我們還需要將每堆資料再各自分成兩等分：

(84、13)　(73、26)　(32、19)　(91、38)

　　此時每堆的資料量為 2 (4 / 2) > 1。再一次，我們將每堆資料各自分成兩等分：

(13)　(84)　(26)　(73)　(19)　(32)　(38)　(91)

　　此時每堆的資料量為 1 (2 / 2) = 1 ，符合停止切割的條件。所以接下來，我們要將資料兩兩合併。在合併的同時，同時確保資料排序：

(13、84)　(26、73)　(19、32)　(38、91)

　　同樣的，我們將資料兩兩合併：

(13、26、73、84)　(19、32、38、91)

　　同樣的，我們將資料兩兩合併：

(13、19、26、32、38、73、84、91)

　　最後，我們從時間效率上來討論合併排序法。設 merge sort 的時間複雜度函數為 T(n)。

　　我們可以知道，在每一次呼叫 mergeSort() 函式時，我們都需要分別將前半段與後半段的資料複製給 left 跟 right，所以複製資料的時間花費為 c₁n。

　　然後，我們需要遞迴呼叫兩次資料大小為 n/2 的 mergeSort()，時間花費為 2T(n / 2)。最後再加上呼叫 merge() 函式所需的時間花費 c₂n。所以我們可以得到：T(n) = 2T(n / 2) + cn (n > 1)，且 T(1) = 1。



　　若是將式子展開：T(n) = 2T(n / 2) + cn = 4T(n / 4) + 2c(n / 2) + cn = 8T(n / 8) + 4c(n / 4) + 2c(n / 2) + cn = ... = cn + cn + cn + ... + cn = cn(lg n + 1) ∈ O(n lg n)（註1）。

　　由此可見，合併排序的的時間效率是相當不錯的。



　　另外，因為有網友詢問非遞迴的合併排序法，因此試著寫了以下這個虛擬碼：

Function mergeSort(Type data[1..n])
    If n <= 1 then return

    Index i, j, k
    For i from 2 to (n / 2) do
        For j from 0 to (n - 1) step (2 * i) do
            Index x, y
            x = min(i, n - j)
            y = min(i, max(0, n - i - j))

            Type left[1..x], right[1..y]
            For k from 1 to x do
                left[k] = data[j + k]
            For k from 1 to y do
                right[k] = data[i + j + k]

            Index p, q, r
            p = q = 1
            r = j
            While p <= x and q <= y do
                If left[p] < right[q] then
                    data[r] = left[p]
                    p = p + 1
                Else
                    data[r] = right[q]
                    q = q + 1
                r = r + 1

            While p <= x do
                data[r] = left[p]
                p = p + 1
                r = r + 1

            While q <= y do
                data[r] = right[q]
                q = q + 1
                r = r + 1
End

　　寫起來感覺不太直觀，如果有錯誤歡迎糾正我：）


註1. 其實可以直接利用支配定理（Master theorem）來求出複雜度 T(n)。 展開全文文章收合

【演算】選擇排序法 - Selection Sort

　　選擇排序法（selection sort）為一種較直觀的排序演算法（sorting algorithm）。其將資料分為「已排序」與「未排序」兩部份，並從「未排序」的資料中找出最大（最小）值，放入「已排序」資料的最後端。如是進行，直到排序結束（未排序資料為空）為止。



　　一般來說，我們的作法是：將「已排序」的資料擺在資料序列的前端，並將「未排序」的資料擺在資料序列的後端。

　　假設我們需要將 n 筆資料由大排到小。在起初，這 n 筆資料都是「未排序」的。於是，我們從這 n 筆資料取出其中的最大值，並將之放在「已排序」資料的最後端。換言之，就是將之與第一筆資料進行交換。

　　接著，我們再從剩下的 n - 1 筆資料取出最大值，同樣放入「已排序」資料的最後端（與第二筆資料進行交換）；再從剩下的 n - 2 筆資料取出最大值，放入「已排序」資料的最後端（與第三筆資料進行交換）。

　　以此類推，直到沒有任何「未排序」的資料為止。



　　選擇排序法的虛擬碼大致如下：

Function selectionSort(Type data[1..n])
    Index i, j, max
    For i from 1 to n do
        max = i
        For j from i + 1 to n do
            If data[j] > data[max] then
                max = j

        Exchange data[i] and data[max]
End

　　舉例來說，若我們需要將以下資料由大排到小：

19 58 33 41 28 14 53 84

　　則以此演算法運作的過程如下：

84 58 33 41 28 14 53 19

84 58 33 41 28 14 53 19

84 58 53 41 28 14 33 19

84 58 53 41 28 14 33 19

84 58 53 41 33 14 28 19

84 58 53 41 33 28 14 19

84 58 53 41 33 28 19 14

84 58 53 41 33 28 19 14

　　若是我們分析在最差情況下（所有資料的順序剛好完全相反），使用選擇排序法將 n 筆資料排序的敘述執行次數（註1）：

Function selectionSort(Type data[1..n])
    Index i, j, max                                 // 1
    For i from 1 to n do                            // n
        max = i                                     // n
        For j from i + 1 to n do                    // n(n - 1) / 2
            If data[j] > data[max] then             // n(n - 1) / 2
                max = j                             // n(n - 1) / 2

        Exchange data[i] and data[max]              // n
End

　　經由以上，我們可以得到最差情況下，敘訴的執行次數總和：W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + n = (3n² + 3n - 2) / 2 ∈ Ο(n²)。

　　由此可知，選擇排序法的時間複雜度與之前介紹過的氣泡排序法（bubble sort）相當，同樣為效率不大優良的排序演算法。

註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。

展開全文文章收合