【介紹】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 加總化簡而來。

【目錄】Verilog

Verilog 相關一覽


筆記

‧Introduction to Verilog
‧Quartus II Installation
‧Verilog Module
‧Create a Verilog Project

【筆記】Create a Verilog Project

　　安裝好 Verilog 的撰寫環境－－Quartus II 之後，我們還需要建置好一個專案（project）才能正式開始。所以，這裡簡單的描述一下建立專案，以及編譯 Verilog 原始碼的流程。



　　首先，點選選單的 File/New Project Wizard。就會跳出一個專案的建置精靈：



　　在「What is the working directory for this project?」中輸入你專案的擺放路徑，並在「What is the name of this project?」中輸入專案的名稱（註1）。

　　若是專案路徑的資料夾不存在，會跳出訊息問你是否要建立它：



　　確定要建立，就選擇「是」。



　　按下 Next 之後，我們可以加入一些現有的檔案到專案裡頭：



　　你可以利用 File name 後方的「...」按鈕開啟檔案對話方塊，選擇要加入的檔案，再按下 Add 按鈕加入專案。也可以直接按下 Add All 將目錄下的檔案都加到專案中。

　　不過，這裡我們還沒有任何現存的檔案可以加入，所以直接按下 Finish 完成專案建置（註2）。



　　建立好專案之後，我們還需要建立一個 Verilog 的原始碼檔案。按下選單的 File/New，就會出現對話框詢問你新增的檔案類型：



　　由於我們要是 Verilog 的原始碼檔案，所以選擇「Verilog HDL File」。

　　新增完成之後，就可以直接開始撰寫程式碼（下圖中的程式碼為先前 Verilog Module 解釋的 AndGate Module）：



　　接下來將檔案存檔：



　　請記得，Quartus II 的主要模組一定要跟檔案名稱相同。



　　接下來，就可以按下選單的 Precessing/Start Compilation 開始編譯的動作。假如跳出「Full Compilation was successful」的對話框，就代表編譯成功了（註3）：

註1. 建議將專案放在獨立的地方，並為專案取個有意義的名稱，方便以後重複使用專案。
註2. 實際上後面還有一些設定燒錄晶片跟相關工具的部份，不過這裡我們目前都用不到。
註3. 這裡會看到其實編譯過程中會有些警告訊息。雖然這裡我們並不在意它，不過你也可以去看看這些警告訊息，查查到底為什麼。

【筆記】Verilog Module

　　在之前的簡介中提到，Verilog 以模組（module）作為描述的基本單位。模組如同程式語言中的函式（function），可以將一部份的程式碼封裝起來，並提供對外溝通的介面（interface）。如此一來，我們便可以重複利用這些定義好的模組，以構成較大、較複雜的系統。



　　我們可以將模組看成兩個部份：連接埠（port）的宣告，以及模組的主體（body）。

　　其中，連接埠類似於程式語言中函式的參數（parameter），提供了對外溝通的介面。包含了輸入埠（input）、輸出埠（output）、或是兼具輸出入的雙向埠（inout）。簡單來說的話，其實可以把連接埠想成一顆 IC 上面的接腳（pin）。

　　而模組主體則類似於程式語言中的函式主體，表達了模組的結構，或是模組的功能與行為。



　　以下是一個 Verilog 的模組，代表一個 and 邏輯閘：

module AndGate(out, a, b);
    input   a, b;
    output  out;

    and(out, a, b);
endmodule

　　接著，讓我們一步一步理解這個簡易的模組。

module AndGate(out, a, b);

　　這裡的「module」為 Verilog 語法的關鍵字，代表一個模組宣告的開頭；「AndGate」為這個模組的名稱（註1）；而括號中的 out、a、跟 b，則是這個模組的連接埠（註2）。

　　不過，在這裡並沒有指明連接埠的類型（input、output、或是 inout）。所以我們將在下面兩行宣告它們：

    input   a, b;
    output  out;

　　我們宣告 a 跟 b 為 AndGate 的輸入埠，且 out 為 AndGate 的輸出埠。



　　而模組主體的部份，我們只做了一個簡單的動作：

    and(out, a, b);

　　「and」為 Verilog 提供的內建邏輯閘。這裡的動作是將輸入埠 a 跟 b 進行 and 運算，並以輸出埠 out 作為運算後的結果（註3）。



　　最後，我們以「endmodule」關鍵字結束模組的宣告：

endmodule

　　這個模組的示意圖大致如下：

註1. 你可以根據模組的功能，自行取一個有意義的名稱。
註2. 一般來說，我們習慣將 output 寫在前面、將 input 寫在後面。
註3. 或許想成「將 a 跟 b 接到 and gate 的 input 接腳，並將 out 接到 and gate 的 output 接腳」會比較好理解。

【筆記】Quartus II Installation

　　在實際開始撰寫 Verilog 之前，我們需要先安裝好撰寫執行 Verilog 程式的環境工具。而這裡我們採用的工具，是 Altera 公司的 Quartus II 這套軟體。

　　Quartus II 是一套用以撰寫 Verilog、VHDL、AHDL 等 HDL 的開發工具，除了可以進行程式的編輯與編譯之外，也可以用以產生邏輯圖、狀態圖、波形圖等等，在功能上算是相當齊全。



　　現行的 Quartus II 有兩個不同的版本：Web Edition 與 Subscription Edition。

　　其中 Subscription Edition 有提供 30 天的試用期。超過試用期之後，是需要經過授權才可以繼續使用的。而 Web Edition 則是免費的版本，可以直接下載來使用。

　　這裡我們要使用的是 Web Edition。



　　要取得 Quartus II Web Edition，需要先連到其下載頁面：



　　然後，選擇下載「Quartus® II Web Edition Software v9.1 Service Pack 1」（請依照當前最新版本自行尋找）。



　　接著會進到 Account Sign-In 的畫面。假設各位都沒有 Altera 的帳號，可以選擇「Get One-Time Access」並在下面的文字框輸入你的 E-mail，就能夠不經由註冊的步驟繼續下載。

　　當然，若是你真的想註冊一個帳號，選擇「Create Your myAltera Account」並完成註冊步驟也是可以的。



　　最後，拉到頁面下方，點選「Click to Download Your File Now」，就可以進行下載，並開始安裝（因為安裝過程只需要選擇安裝路徑，這裡就不花版面贅述了）。

　　由於檔案大小高達 1.5GB，下載跟安裝的動作比較耗時，所以可能需要耐心等待一下子。



　　安裝完成之後，就可以開始使用 Quartus II 這套功能強大的工具囉：

【筆記】Introduction to Verilog

　　因為系上這學期有一門要寫 Verilog 的必修課，所以想說乾脆直接在 blog 上做個筆記整理內容，並供一起上課的同學們作為參考。不過，其中的許多內容都不是我非常瞭解的，假如有任何錯誤或問題，都歡迎各位提出來。



　　說到 Verilog 就不能不先提到 HDL（Hardware Description Language，硬體描述語言）。

　　所謂 HDL，即是利用一般高階語言的程式撰寫法，以達成數位電路功能或結構的設計、驗證與模擬。利用 HDL，我們便可以不必透過傳統的手繪方式設計電路，再在麵包板上接出電路來進行驗證與模擬。而 Verilog 則是主流的兩種 HDL 之一（註1）。

　　Verilog 在設計時採用了近似於 C 語言的語法，以類似於函式（function）的模組（module）作為描述的基本單位。對於熟悉 C 語言的程式設計師來說，Verilog 還算是相當容易學習。



　　在實際的設計上，Verilog 則提供了四種層級的描述方式，供設計者在不同層次的觀點上設計電路。分別為：開關層級（Switch Level）、邏輯閘層級（Gate Level）、資料流層級（Dataflow Level）與行為層級（Behavioral Level）。

　　開關層級是 Verilog 所提供的最低層級。在這個層級上，設計者需要瞭解電路的開關－－電晶體（transistor）的元件特性，並以此進行電路的設計。

　　在邏輯閘層級中，設計者的觀點從一個個的電晶體，轉到較高層的邏輯閘（logic gate）。以此觀點，設計者可以直接利用如 and、or、not、xor 等邏輯閘，與將之連接的線路來進行設計。

　　在資料流層級中，我們關注的則是資料如何經由硬體元件進行處理、儲存、與流向；而在最高層級的行為層級上，設計者只需要知道模組與函式間的功能，而不去考慮硬體實作的細節。

註1. 另一種常用的硬體描述語言是 VHDL（Very-High-Speed Integrated Circuit Hardware Description Language）。

【演算】氣泡排序法 - Bubble Sort

　　氣泡排序法（bubble sort）是排序演算法（sorting algorithm）中較簡易的一種。其運作的原理是藉由逐次比較相鄰的兩筆資料，並依照排序條件（由大至小或由小至大）交換資料直到排序完成為止。



　　假設現在我們需要將 n 筆資料 A₁、A₂、......、A_n 由小排到大。

　　一開始，我們需要先比較 A₁ 與 A₂ 兩筆資料的大小。若是 A₁ > A₂，則交換兩筆資料；接著比較 A₂ 與 A₃。若是 A₂ > A₃，則交換兩筆資料；以此類推，一直到比較完 A_{n - 1} 與 A_n 為止。



　　這樣就完了嗎？當然還沒。到目前為止，我們只確定 A_n 是 n 筆資料中最大的數字。

　　接下來，重複剛剛的動作：比較 A₁ 與 A₂、A₂ 與 A₃、A₃ 與 A₄、......，不同的是，這一次只需要比較到 A_{n - 2} 與 A_{n - 1} 即可。到目前為止，我們可以確定 A_{n - 1} 是 n 筆資料中次大的數字。

　　接著就繼續重複同樣的動作，便能確定每一輪比較中的最大資料，皆在這些資料的最後面。直到所有資料排序完成為止。



　　其原理的虛擬碼大致如下：

Function bubbleSort(Type data[1..n])
    Index i, j;
    For i from n to 2 do
        For j from 1 to i - 1 do
            If data[j] > data[j + 1] then
                Exchange data[j] and data[j + 1]
End

　　讓我們舉個實際的例子來說明。若是我們現在要將以下這些資料由大排到小：

1 43 6 79 50 2

　　則第一輪的比較與交換過程如下：

43 1 6 79 50 2

43 6 1 79 50 2

43 6 79 1 50 2

43 6 79 50 1 2

43 6 79 50 2 1

　　第二輪的比較與交換過程如下：

43 6 79 50 2 1

43 79 6 50 2 1

43 79 50 6 2 1

43 79 50 6 2 1

　　接下來以此類推。

　　由此可以看到，資料中較小的一筆會藉由交換慢慢「浮」到資料頂端，其「氣泡排序」之名也是因此而來。



　　若是我們分析在最差情況下（即所有資料的順序剛好完全相反，因為我們必須在每一輪迴圈，藉由不斷交換兩筆資料的動作，把最前頭的資料移到最後面），使用氣泡排序法將 n 筆資料排序的敘述執行次數（註1）：

Function bubbleSort(Type data[1..n])
    Index i, j;                                     // 1
    For i from n to 2 do                            // n - 1
        For j from 1 to i - 1 do                    // n(n - 1) / 2
            If data[j] > data[j + 1] then           // n(n - 1) / 2
                Exchange data[j] and data[j + 1]    // n(n - 1) / 2
End

　　可得出所有敘述的執行次數總和為：W(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 = (3n² - n) / 2 ∈ Ο(n²)，為一個平方時間（quadratic time）的演算法。



　　而在最好的情況下（即所有資料都為已排序狀態，因為不需要進行任何一次交換動作）：

Function bubbleSort(Type data[1..n])
    Index i, j;                                     // 1
    For i from n to 2 do                            // n - 1
        For j from 1 to i - 1 do                    // n(n - 1) / 2
            If data[j] > data[j + 1] then           // n(n - 1) / 2
                Exchange data[j] and data[j + 1]    // 0
End

　　所有敘述的執行次數總和為：B(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + 0 = n² ∈ Ο(n²)。複雜度依舊為平方時間。

　　對於一種排序演算法而言，這樣複雜度是相當沒有效率的。因此這個方法多半只是被拿來簡單的解釋排序概念，而不是拿來實際應用。

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

【演算】遞迴函式 - Recursive Function

　　所謂的遞迴（recursion），簡單來說就是「函式（function）不斷呼叫自身」的一種程式撰寫法。遞迴的意義，在於把一個問題切割成相同性質的較小問題來解決。而為了防止程式無窮盡的遞迴下去，我們還必須為所寫出來的遞迴函式設定一個終止條件（termination condition）。

　　遞迴的原理，是利用函式本身的堆疊（stack）性質－－後進先出（last in, first out，LIFO）來達成的。說得簡單一點，就是當某個函式呼叫另一個函式時，其會先執行完被呼叫的函式，才繼續執行自身的函式內容。



　　讓我們舉一個常見的例子來解釋：階乘（factorial）。

　　在數學上的定義中，對於一個非負整數 n，其階乘代表的是所有小於或等於 n 的正整數乘積，記作 n!。即 n! = 1 × 2 × 3 × ... × n。若我們規定 0! = 1，則可以將之改寫成：對於所有非負整數 n，(n + 1)! = (n + 1) × n!。

　　於是，我們便可以利用程式寫出計算階乘的遞迴函式。以下為其虛擬碼：

Function factorial(Integer n)
    If n = 0 then
        Return 1
    Else
        Return n × factorial(n - 1)
End

　　在這裡，我們相當於將原始的問題 n! 看作是 n × (n - 1)! 這個較小的問題。也就是得知 (n - 1)! 的值，就可以求得 n! 的解。同樣的，又可以將 (n - 1)! 看作是 (n - 1) × (n - 2)!、將 (n - 2)! 看作是 (n - 2) × (n - 3)!、......。

　　舉例來說，若是我們需要利用程式求出 6! 的值。則在我們呼叫 factorial(6) 時，為了得出結果，亦須求出 factorial(5) 的值。而為了得出 factorial(5) 的結果，我們亦須求出 factorial(4) 的值......。一直不斷遞迴下去，直到達到終止條件：n = 0 為止。

　　實際運作的結果，就如下圖所示意的（藍箭頭代表呼叫，紅箭頭代表回傳）：





　　除此之外，遞迴還可以解決相當多其他的問題。例如斐波那契數列（fibonacci sequence）、老鼠走迷宮（mouse in a maze）、以及河內塔（tower of hanoi）等等，這裡我就不加贅述了。



　　雖然利用程式的遞迴解法較為直觀，但是不斷堆疊函式的結果，極有可能浪費了過多的記憶體空間。其實，遞迴的程式多半都能藉由迴圈的方式替代，只是程式也可能會因此變得複雜難懂。至於實際上要使用何者，就看你怎麼選擇囉。

【演算】複雜度分析 - Complexity Analysis

　　在演算法簡介中，我們提到了「找電話」問題的兩個演算法：分別為「依序找」跟「按筆劃找」。我們可以知道，對於相同的問題，可能會同時存在許多不同的解法。然而在這種擁有多種可能解法的情況下，我們理應對這些演算法進行評估，並從中選擇一種最有效的方式。



　　從比較執行時間的層面來看，或許你會想到：直接利用計時器來比較不同演算法實現程式的執行時間。但是，這種方式的變因太多。實作演算法的程式語言、記憶體大小、不同的編譯（直譯）器、甚至是電腦中運行的程式，可能都會影響計時所得的結果。相對的，這種方式也就顯得不太準確。

　　除了實際去計時之外，我們也可以假設演算法中「每一步」的執行時間都相同。於是，我們也可以直接拿演算法所有「步驟」的執行次數總和來進行比較。



　　讓我們同樣以「依序找電話」演算法為例。

　　先考慮在最差情況（worst case）下（也就是欲尋找的電話號碼不在電話簿中，因為你必須搜遍整本電話簿），「依序找電話」虛擬碼每行敘述的執行次數如下（方便起見，我們以變數 n 代表電話簿的大小 phoneBook.size）：

Input name                                          // 1
While True do                                       // n
    If index > phoneBook.size then                  // n
        Output "phone number not found"             // 1
        Break loop                                  // 1

    If phoneBook.record[index].name = name then     // n
        Output phoneBook.record[index].phone        // 0
        Break loop                                  // 0

    index = index + 1                               // n

　　因此在最差情況下，每行敘述的執行次數總和：W(n) = 1 + n + n + 1 + 1 + n + 0 + 0 + n = 4n + 3。

　　由此可以發現，一個演算法的執行時間通常會隨著輸入資料的大小 n 的成長而成長（註1）。而這個與資料大小 n 相關的時間（或空間）函數，則稱為這個演算法的複雜度（complexity）。



　　不過，我們還可以用更簡明、更具數學意義的方式來表達它。

　　首先，我們可以知道當 n 是一個相當大的數字時，4n 是遠大於 3 的。換句話說，就是我們只需要保留函數的最高項，也就是這個例子中的 4n。而若是只想考慮其函數的成長趨勢，我們甚至可以連其係數一併省略，只注意 n 這個部份，代表這個演算法是一個線性時間（linear time）的演算法，記作 O(n)。



　　Ο（big-omicron，或是稱作 big-O）是一個漸進符號（asymptotic notation），代表了函數的漸進上限（asymptotic upper bound）。其定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ f(n) ≤ cg(n)，則 f(n) ∈ Ο(g(n))。

　　簡單來說，若是我們說一個演算法的複雜度函數 f(n) ∈ Ο(g(n))，就代表函數 f(n) 的成長趨勢與 g(n) 相似或是更慢的。



　　除了 big-omicron 之外，我們還可以使用 Ω（big-omega）、Θ（big-theta）、ο（little-omicron）與 ω（little-omega）來表達一個演算法的複雜度。

　　big-omega 代表了函數的漸進下限（asymptotic lower bound）。簡單來說，若是我們說一個演算法的複雜度函數 f(n) ∈ Ω(g(n))，就代表 f(n) 函數圖形的成長趨勢與 g(n) 相似或是更快的。其正式的定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ cg(n) ≤ f(n)，則 f(n) ∈ Ω(g(n))。

　　那麼 big-theta 呢？其實，big-theta 也就相等於 big-omicron 與 big-omega 的交集，也就是 Θ(g(n)) = Ο(g(n)) ∩ Ω(g(n))，代表 f(n) 函數圖形的成長趨勢與 g(n) 是相似的。其正式的定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀, c₁與 c₂ > 0，使得所有整數 n ≥ n₀ 都滿足 c₁g(n) ≤ f(n) ≤ c₂g(n)，則 f(n) ∈ Θ(g(n))。

　　而 little-omicron 與 little-omega 則分別為 big-omicron 與 big-omega 和 big-theta 的差集，即 ο(g(n)) = Ο(g(n)) - Θ(g(n)), ω(g(n)) = Ω(g(n)) - Θ(g(n))。以下為其正式定義：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ f(n) < cg(n)，則 f(n) ∈ ο(g(n))。

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ cg(n) < f(n)，則 f(n) ∈ ω(g(n))。

　　為了方便比較，我們可以將 f(n) 與 g(n) 比擬成 a 跟 b，則：

• f(n) ∈ Ο(g(n)) ≈ a ≤ b
• f(n) ∈ Ω(g(n)) ≈ a ≥ b
• f(n) ∈ Θ(g(n)) ≈ a = b
• f(n) ∈ ο(g(n)) ≈ a < b
• f(n) ∈ ω(g(n)) ≈ a > b

　　雖然存在這麼多種漸進符號以表達演算法的複雜度，但是一般來說，當我們分析一個演算法的複雜度，比較常使用 big-omicron 來表達估算後的結果。這是因為對於一個演算法，其所耗費的時間（或是記憶體）上限，通常才是我們需要關注的重點。

註1. 對於演算法所使用的記憶體空間，通常也是如此。

【演算】演算法簡介 - Introduction of Algorithm

　　演算法（algorithm）出自於數學用語，指的是：在有限步驟內，解決一個問題的具體步驟和方法。其接受零或多個輸入資料，並在處理過後產生一個以上的輸出結果。

　　經由整理，我們可以知道，演算法必須具備以下特性：

• 有限性（Finiteness）：演算法必須在有限的步驟內完成。
• 有效性（Effectiveness）：演算法中的每個命令都必須為可執行的步驟。
• 正確性（Correctness）：演算法所產生的結果必須是符合預期的。
• 明確性（Definiteness）：演算法中的每個步驟必須是清楚明白、不含糊的。
• 輸入（Input）：由外界提供的零或多筆資料。
• 輸出（Output）：經由處理所得到的一個或多個結果。

　　換個簡單一點的說法，其實演算法就是所謂解決問題的方法。



　　舉例來說：由於長假閒著無聊，所以你想要打電話給多年未聯絡的的老朋友「郝仁」聊天敘敘舊。但是當你翻開電話簿，發現其中洋洋灑灑百餘個人名，該如何從中找到你想要的電話號碼呢？

　　當然你可以依序，從第一個名字一路找到最後一個。但是，假設電話簿早已依照姓氏筆畫排序，你何不省點功夫？我們可以隨意找到某個位置，若是筆劃比「郝」多一點，我們可以再往前翻一點；若是筆劃比「郝」少一點，我們可以在往後翻一點。直到找到「郝」這個姓氏為止。

　　上述提到的「找電話」，就是我們需要解決的「問題」。而這兩種方法（依序找跟按筆劃找），就是解決「找電話」這個問題的「演算法」（註1）。對於這個問題的「輸入」，就是你希望查到電話號碼的人（郝仁）；而「輸出」理所當然是這個人的電話號碼了。



　　那麼，我們該如何描述我們所使用的演算法呢？

　　我們可以單純的採用文字描述。在上面「找電話」的例子，我用以描述這兩種「找電話」方法的方式就是文字敘述。換句話說，就是使用一般人較能接受的口語來描述演算法。

　　不過，由於用文字敘述容易造成文字太過冗長，且自然語言（如我們所說的語言：中文、英文、日文等，相對於程式語言等「人造語言」）的種類繁多，由不同的人來看可能會產生認知上的差異，而有所誤差。所以此種方式相較之下是比較不精確的。



　　既然用文字描述不太好，我們也可以直接利用實作出來的程式碼描述。如以下以 C 語言實作的「依序找電話」方法：

size_t index = 0;
char name[MAX_NAME_LENGTH];

scanf("%s", name);
while (true)
{
    if (index >= phoneBook.size)
    {
        printf("phone number not found");
        break;
    }

    if (strcmp(phoneBook.record[index].name, name) == 0)
    {
        printf("%s", phoneBook.record[index].phone);
        break;
    }

    index++;
}

　　雖然這種方法不會有文字描述上的「冗長」跟「不精確」等缺點，但是因為這種方式往往需要考量到實作上的細節，也就是針對不同程式語言特性所需的程式撰寫或演算法的修改，使得演算法的描述無法完全專注在實際上的「執行步驟」上。



　　所以，虛擬碼（pseudocode）便為此應運而生了。

　　虛擬碼通常包括類似程式語言的文法和特定的關鍵字，再加上一些較自由的自然語言敘述，可以產生極良好的溝通效果，有助於對程式的瞭解。於是，我們可以將「依序找」的演算法以虛擬碼表示：

Input name
While True do
    If index > phoneBook.size then
        Output "phone number not found"
        Break loop

    If phoneBook.record[index].name = name then
        Output phoneBook.record[index].phone
        Break loop

    index = index + 1

　　除此之外，我們還可以利用工業上經常使用的流程圖（flowchart）來描述演算法。流程圖使用各種標準化的符號、圖形來描述執行步驟與方式。如以下這個「依序找電話」演算法的流程圖範例：



　　相較於文字，顯然這種方式較容易看出演算法的流程，也比文字易懂的多。也因為圖形都經過標準化，因此在解讀上較不會出現解釋歧異的問題。

註1. 實際上，這個「找電話」問題就是典型的搜尋（search）問題，而這兩種尋找電話號碼的方法，則稱為所謂的「搜尋演算法（search algorithm）」。

【雜記】關於「近」況

　　顯然，這裡已經很久沒有更新了。雖然我還有持續在注意有沒有新留言，但是遲遲沒有貼新文章。總覺得偷懶也偷得夠久了，似乎該回來寫點東西XD。

　　其實這個 blog 平台用久了，總會覺得不太滿意，想要一個針對自己需求特化的一些功能(當然 blogger 這個平台也相當好，我用起來也挺順手的，但是我還是覺得缺了點什麼XD)。因為不太想用一些如 WordPress 或 Joomla! 之類的現成 CMS(Content Management System，內容管理系統)來修改，便瘋狂的想要自己寫一個(這種重複造輪子的行為千萬別模仿XD)。

　　原本我是打算，暫時停止 blog 的更新，專心寫一個 CMS 出來，再將現有的文章做個整理過去。但是事實證明，除了我對 Web Programming 不是非常熟悉之外，還有無止境的偷懶造就了現在的結果：blog 停止更新永無止境，想做出來的 CMS 卻連個影子都沒有XD。

　　前陣子，剛好在誠品書局隨手翻到了 IThome 電腦報的 IT部落客大直擊（上）。被標題吸引的我，就這樣順手買了回來翻翻，突然懷念起以前寫 blog 的日子XD。雖然我仍舊沒有放棄想要一個客製功能 blog 的想法，但我也不想繼續這樣把 blog 擺著。

　　經過考慮之後，我決定先從整理這裡的舊文章開始。也許有些文章會被我修改、或是分割內容成其他文章，或許有些文章會被我偷偷地砍掉。也或許，會「順手」新增幾篇文章吧XD。



　　太久沒有寫 blog，有點不知道自己在寫些什麼，感謝各位耐心看完我一整篇的胡言亂語XD。

【目錄】程式設計作品

程式設計作品一覽


C

‧猜數字 - Guess
‧多人聊天室 - Boy Meets Girl


C++

‧嗶嗶歌 - Beep Song
‧嗶嗶歌2 - Beep Song for Windows
‧記憶遊戲 - Memory
‧即時傳訊 - Messenger
‧奧塞羅棋 - Othello
‧大數運算 - Large Integer
‧Base64 編碼/解碼器
‧連結串列 - Linked List


PHP

‧擲骰子 - Dice
‧小小樂透彩 - Lottery
‧猜數字 - Guess (PHP ver.)


Javascript

‧奧塞羅棋 - Othello (JS ver.)
‧卡坦島 - The Settlers of Catan

【作品】連結串列 - Linked List

　　沒什麼，就只是個 Linked List(炸)。


程式說明

　　這東西是根據 C++ STL(Standard Template Library，標準模板函式庫) 的 list 函式介面寫出來的東西，所以使用方法也都相同。

　　要使用這個 Linked List 類別，需要先引入 include 資料夾中的 list.h 標頭檔。然後，不同於「正牌」Linked List，我的類別名稱採用的是首字母大寫的駱駝體(CamelCase)。詳細的用法可以參考檔案裡面的 main.cpp 跟 STL 函式庫說明。

　　總覺得這程式 bug 應該很多，請各位鞭小力點XD


程式連結




更新紀錄：

‧09/07/11 正式公開貼出。

其他

　　題外話：這程式是教授要我們回去練習寫的。

　　不過他要的其實只是個 character 型態的 Linked List 罷了(炸)。

【目錄】ACM Online Judge

ACM Online Judge - 試題解題一覽


相關介紹

What's This
How to Start
What's Wrong


題目中譯

Lucky 貓的 ACM 園地
星子 ACM 小窩
ACM problemset 題目中譯


Volume I

100：The 3n + 1 problem
101：The Blocks Problem
102：Ecological Bin Packing
103：Stacking Boxes
104：Arbitrage - coming soon...
105：The Skyline Problem
107：The Cat in the Hat - coming soon...
108：Maximum Sum - coming soon...
116：Unidirectional TSP - coming soon...
147：Dollars - coming soon...
166：Making Change - coming soon...


Volume II

272：TeX Quotes
275：Expanding Fractions - coming soon...


Volume III

340：Master-Mind Hints - coming soon...
357：Let Me Count The Ways - coming soon...
392：Polynomial Showdown - coming soon...


Volume IV

406：Prime Cuts
412：Pi - coming soon...
458：The Decoder
476：Points in Figures: Rectangles
477：Points in Figures: Rectangles and Circles
483：Word Scramble
488：Triangle Wave
494：Kindergarten Counting Game


Volume V

544：Heavy Cargo - coming soon...
572：Oil Deposits
579：Clock Hands
591：Box of Bricks


Volume IX

913：Joana and the Odd Numbers


Volume C

10018：Reverse and Add
10025：The ? 1 ? 2 ? ... ? n = k problem - coming soon...
10035：Primary Arithmetic
10038：Jolly Jumpers
10055：Hashmat the brave warrior
10056：What is the Probability? - coming soon...
10062：Tell me the frequencies!
10071：Back to High School Physics
10082：WERTYU


Volume CI

10107：What is the Median?
10110：Light, more light - coming soon...
10141：Request for Proposal


Volume CII

10209：Is This Integration?
10222：Decode the Mad man


Volume CIII

10300：Ecological Premium
10340：All in All
10370：Above Average


Volume CIV

10473：Simple Base Conversion
10499：The Land of Justice


Volume CV

10550：Combination Lock
10589：Area


Volume CVI

10673：Play with Floor and Ceil
10696：f91


Volume CVII

10783：Odd Sum
10789：Prime Frequency


Volume CVIII

10812：Beat the Spread!
10878：Decode the tape


Volume CIX

10903：Rock-Paper-Scissors - coming soon...
10924：Prime Words
10929：You can say 11
10963：The Swallowing Ground


Volume CX

11059：Maximum Product


Volume CXI

11172：Relational Operators
11185：Ternary