3月 05, 2010

【演算】演算法簡介 - 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)」。

5 回覆:

匿名 提到...

你這篇太晚寫了啦 ><
ma..寫得不錯就不追究了

整篇內容言簡意賅
沒什麼好挑剔的 (就算有 也是你的龜毛個性
很值得推薦 !!

Unknown 提到...

其實這篇老就寫好了

只是因為寫得不太滿意
最終貼上來, 還是被我刪掉了

這篇是根據那一篇重新改寫
假如有什麼錯誤就煩請指教了

Unknown 提到...

還有, 我的龜毛怎麼了?

匿名 提到...

你的龜毛被拿去種植了 ((喂~
沒有啦 ~
其實你已經先龜毛過了嘛 ~
因為..
你老(早)就寫好
不滿意就刪掉了
又重寫一次

至於錯誤..
ma..演算法聽你解釋我是聽懂了
不過至於是不是那樣我也不知道啦 ~
沒有去查過
所以應該算沒有什麼錯誤
總之這篇寫得不錯 ~~
因為字句很順又能讓我清楚的理解
強力推薦啦 ~~~

台GG 提到...

詳盡

張貼留言