Tip:
Highlight text to annotate it
X
演算法(algorithm) 是什麼?
在電腦科學裡,
演算法指的是一組 一步接著一步、
用來解決問題的指令。
通常,演算法是電腦在執行的,
但是我們人類也是可以有演算法。
比方說,你會怎麼去數
一個房間裡的人數?
嗯,如果你跟我一樣,
也許你會指著每個人,
一次一個,
然後從 0 開始:
1、2、3、4…… 一直下去。
這就是個演算法。
事實上,我們試著用
更正式一點的「虛擬碼」來表示,
它跟英文語法很像、
同時也很類似程式語言。
令 N = 0。
每指到房間裡的一個人, 就將 N 設為 N + 1。
這段虛擬碼要怎麼解釋呢?
第一行是在說
N 是一個變數
然後將它設成 0 作準備 (又稱初使化)。
這意思是我們的演算法,
也就是我們的計數
會從 0 開始。
畢竟,在我們開始計數之前,
我們沒有數到任何東西。
把這變數叫作 N 只是方便起見。
我也可以把它叫作別的名字。
現在,第二行設定 「迴圈」的範圍,
它的意思是有幾個步驟 我們會重覆好幾次。
所以在我們的例子之中, 這個重覆的步驟
就是「數」這房間的人數。
第二行下面有第三行,
它敘述的就是我們要計數的方法。
前端的縮排表示 要重覆的部份就是第三行。
前端的縮排表示 要重覆的部份就是第三行。
所以,整段虛擬碼就是在說
N 從 0 開始,
之後每指到一個人,
N 就加 1。
好了,這演算法正確嗎?
我們稍微試一下。
如果房間裡有兩個人 它是對的嗎?
咱們來看看。
第一行裡,我們將 N 初使化為 0。
每指到這兩個人的其中一個
我們就將 N 加 1。
所以,在迴圈的第一輪裡,
我們將 N 變成 1,
而在同個迴圈的第二輪裡,
我們再將 N 從 1 變為 2。
然後演算法就結束了, N 就是 2,
這數字正好符合這房間的人數。
到目前為止還不錯。
不過如果看看極端的例子呢?
假設房間裡只有 0 個人,
當然在算人數的我不算在內。
第一行裡我們還是將 N 初始化為 0。
但這一次,第三行完全沒有執行,
因為房間裡跟本沒人。
因此,N 維持是 0,
這確實也符合房間裡的人數。
蠻簡單的,對吧?
但是一次數一個人很沒效率,對吧?
當然,我們有更好的辦法!
何不一次數兩個人呢?
與其算 1、2、3、4、5、6、7、8 等等,
何不試試
2、4、6、8,然後一直下去?
這聽起來快多了, 而實際上也是。
讓我們將這項改進 用虛擬碼來表示看看。
令 N = 0。
每指到房間裡的「一對人」,
就將 N 設為 N + 2。
這轉換很簡單,對吧?
與其一次算一個,
我們改成一次算兩個。
這個演算法會比上一個快兩倍。
但是它是對的嗎?
來看看。
如果房間裡有兩個人 它是對的嗎?
第一行裡,我們將 N 初使化為 0。
每指到房內的這對人, 我們就將 N 加 2。
然後演算法就結束了, N 就是 2,
這數字正好符合這房間的人數。
接著假設房間裡有 0 個人。
第一行裡,我們將 N 初使化為 0。
而像之前一樣, 第三行完全沒執行,
因為房間裡根本沒有「一對人」。
因此 N 維持是 0,
這也符合房間裡的人數。
但如果房間裡有 3 個人呢?
這演算法會如何?
來看看。
第一行裡,我們將 N 初使化為 0。
每指到這裡面的一對人,
我們就將 N 加 2,
接著?
房間裡就沒有完整的一對,
所以第二行就不適用了。
接著演算法結束,
N 還是 2,這樣就錯掉了。
事實上我們會說 這個演算法有錯誤(bug),
因為裡頭有些問題。
我們再提出新的虛擬碼吧!
令 N = 0。
每指到房間裡的一對人,
就將 N 設為 N + 2。
如果還有 1 個人沒辦法成對,
就將 N 設為 N + 1。
為了解決這個問題,
我們在第四行提出了新的條件,
也叫作「分支」,
它只有在有 1 個人沒有被配對的情況下 才會執行。
它只有在有 1 個人沒有被配對的情況下 才會執行。
所以現在,不管房間裡
有 1 個或 3 個人、或是任何奇數個人,
這個演算法現在會算到他們了。
我們還能做得更好嗎?
嗯,我們可以一次數 3 個、數 4 個、 甚至是 5 個或 10 個,
不過再下去要指出一組人 就會變得有點困難。
不過再下去要指出一組人 就會變得有點困難。
而在最後,
無論是電腦或是人在執行指令,
演算法就只是一組 用來解決問題的指令。
演算法就只是一組 用來解決問題的指令。
這裡只是三個例子。
而你想要用演算法解決什麼問題呢?