【演算】選擇排序法 - 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。