What's an algorithm? - David J. Malan

人腦也可以執行演算法 - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

譯者: Jephian Lin 審譯者: Michelle Ho

What's an algorithm?

演算法（algorithm） 是什麼？

In computer science,

在電腦科學裡，

an algorithm is a set of instructions

演算法指的是一組 一步接著一步、

for solving some problem, step-by-step.

用來解決問題的指令。

Typically, algorithms are executed by computers,

通常，演算法是電腦在執行的，

but we humans have algorithms as well.

但是我們人類也是可以有演算法。

For instance, how would you go about counting

比方說，你會怎麼去數

the number of people in a room?

一個房間裡的人數？

Well, if you're like me,

嗯，如果你跟我一樣，

you probably point at each person,

也許你會指著每個人，

one at a time,

一次一個，

and count up from 0:

然後從 0 開始：

1, 2, 3, 4 and so forth.

1、2、3、4…… 一直下去。

Well, that's an algorithm.

這就是個演算法。

In fact, let's try to express it

事實上，我們試著用

a bit more formally in pseudocode,

更正式一點的「虛擬碼」來表示，

English-like syntax

that resembles a programming language.

它跟英文語法很像、

同時也很類似程式語言。

Let n equal 0.

令 N = 0。

For each person in room, set n = n + 1.

每指到房間裡的一個人， 就將 N 設為 N + 1。

How to interpret this pseudocode?

這段虛擬碼要怎麼解釋呢？

Well, line 1 declares, so to speak,

第一行是在說

a variable called n

N 是一個變數

and initializes its value to zero.

然後將它設成 0 作準備 （又稱初使化）。

This just means that at the beginning of our algorithm,

這意思是我們的演算法，

the thing with which we're counting

也就是我們的計數

has a value of zero.

會從 0 開始。

After all, before we start counting,

畢竟，在我們開始計數之前，

we haven't counted anything yet.

我們沒有數到任何東西。

Calling this variable n is just a convention.

把這變數叫作 N 只是方便起見。

I could have called it almost anything.

我也可以把它叫作別的名字。

Now, line 2 demarks the start of loop,

現在，第二行設定 「迴圈」的範圍，

a sequence of steps that will repeat some number of times.

它的意思是有幾個步驟 我們會重覆好幾次。

So, in our example, the step we're taking

所以在我們的例子之中， 這個重覆的步驟

is counting people in the room.

就是「數」這房間的人數。

Beneath line 2 is line 3,

第二行下面有第三行，

which describes exactly how we'll go about counting.

它敘述的就是我們要計數的方法。

The indentation implies that it's line 3

前端的縮排表示 要重覆的部份就是第三行。

that will repeat.

前端的縮排表示 要重覆的部份就是第三行。

So, what the pseudocode is saying

所以，整段虛擬碼就是在說

is that after starting at zero,

N 從 0 開始，

for each person in the room,

之後每指到一個人，

we'll increase n by 1.

N 就加 1。

Now, is this algorithm correct?

好了，這演算法正確嗎？

Well, let's bang on it a bit.

我們稍微試一下。

Does it work if there are 2 people in the room?

如果房間裡有兩個人 它是對的嗎？

Let's see.

咱們來看看。

In line 1, we initialize n to zero.

第一行裡，我們將 N 初使化為 0。

For each of these two people,

每指到這兩個人的其中一個

we then increment n by 1.

我們就將 N 加 1。

So, in the first trip through the loop,

所以，在迴圈的第一輪裡，

we update n from zero to 1,

我們將 N 變成 1，

on the second trip through that same loop,

而在同個迴圈的第二輪裡，

we update n from 1 to 2.

我們再將 N 從 1 變為 2。

And so, by this algorithm's end, n is 2,

然後演算法就結束了， N 就是 2，

which indeed matches the number of people in the room.

這數字正好符合這房間的人數。

So far, so good.

到目前為止還不錯。

How about a corner case, though?

不過如果看看極端的例子呢？

Suppose that there are zero people in the room,

假設房間裡只有 0 個人，

besides me, who's doing the counting.

當然在算人數的我不算在內。

In line 1, we again initialize n to zero.

第一行裡我們還是將 N 初始化為 0。

This time, though, line 3 doesn't execute at all

但這一次，第三行完全沒有執行，

since there isn't a person in the room,

因為房間裡跟本沒人。

and so, n remains zero,

因此，N 維持是 0，

which indeed matches the number of people in the room.

這確實也符合房間裡的人數。

Pretty simple, right?

蠻簡單的，對吧？

But counting people one a time is pretty inefficient, too, no?

但是一次數一個人很沒效率，對吧？

Surely, we can do better!

當然，我們有更好的辦法！

Why not count two people at a time?

何不一次數兩個人呢？

Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth,

與其算 1、2、3、4、5、6、7、8 等等，

why not count

何不試試

2, 4, 6, 8, and so on?

2、4、6、8，然後一直下去？

It even sounds faster, and it surely is.

這聽起來快多了， 而實際上也是。

Let's express this optimization in pseudocode.

讓我們將這項改進 用虛擬碼來表示看看。

Let n equal zero.

令 N = 0。

For each pair of people in room,

每指到房間裡的「一對人」，

set n = n + 2.

就將 N 設為 N + 2。

Pretty simple change, right?

這轉換很簡單，對吧？

Rather than count people one at a time,

與其一次算一個，

we instead count them two at a time.

我們改成一次算兩個。

This algorithm's thus twice as fast as the last.

這個演算法會比上一個快兩倍。

But is it correct?

但是它是對的嗎？

Let's see.

來看看。

Does it work if there are 2 people in the room?

如果房間裡有兩個人 它是對的嗎？

In line 1, we initialize n to zero.

第一行裡，我們將 N 初使化為 0。

For that one pair of people, we then increment n by 2.

每指到房內的這對人， 我們就將 N 加 2。

And so, by this algorithm's end, n is 2,

然後演算法就結束了， N 就是 2，

which indeed matches the number of people in the room.

這數字正好符合這房間的人數。

Suppose next that there are zero people in the room.

接著假設房間裡有 0 個人。

In line 1, we initialize n to zero.

第一行裡，我們將 N 初使化為 0。

As before, line 3 doesn't execute at all

而像之前一樣， 第三行完全沒執行，

since there aren't any pairs of people in the room,

因為房間裡根本沒有「一對人」。

and so, n remains zero,

因此 N 維持是 0，

which indeed matches the number of people in the room.

這也符合房間裡的人數。

But what if there are 3 people in the room?

但如果房間裡有 3 個人呢？

How does this algorithm fair?

這演算法會如何？

Let's see.

來看看。

In line 1, we initialize n to zero.

第一行裡，我們將 N 初使化為 0。

For a pair of those people,

每指到這裡面的一對人，

we then increment n by 2,

我們就將 N 加 2，

but then what?

接著？

There isn't another full pair of people in the room,

房間裡就沒有完整的一對，

so line 2 no longer applies.

所以第二行就不適用了。

And so, by this algorithm's end,

接著演算法結束，

n is still 2, which isn't correct.

N 還是 2，這樣就錯掉了。

Indeed this algorithm is said to be buggy

事實上我們會說 這個演算法有錯誤（bug），

because it has a mistake.

因為裡頭有些問題。

Let's redress with some new pseudocode.

我們再提出新的虛擬碼吧！

Let n equal zero.

令 N = 0。

For each pair of people in room,

每指到房間裡的一對人，

set n = n + 2.

就將 N 設為 N + 2。

If 1 person remains unpaired,

如果還有 1 個人沒辦法成對，

set n = n + 1.

就將 N 設為 N + 1。

To solve this particular problem,

為了解決這個問題，

we've introduced in line 4 a condition,

我們在第四行提出了新的條件，

otherwise known as a branch,

也叫作「分支」，

that only executes if there is one person

它只有在有 1 個人沒有被配對的情況下 才會執行。

we could not pair with another.

它只有在有 1 個人沒有被配對的情況下 才會執行。

So now, whether there's 1 or 3

所以現在，不管房間裡

or any odd number of people in the room,

有 1 個或 3 個人、或是任何奇數個人，

this algorithm will now count them.

這個演算法現在會算到他們了。

Can we do even better?

我們還能做得更好嗎？

Well, we could count in 3's or 4's or even 5's and 10's,

嗯，我們可以一次數 3 個、數 4 個、 甚至是 5 個或 10 個，

but beyond that it's going to get

不過再下去要指出一組人 就會變得有點困難。

a little bit difficult to point.

不過再下去要指出一組人 就會變得有點困難。

At the end of the day,

而在最後，

whether executed by computers or humans,

無論是電腦或是人在執行指令，

algorithms are just a set of instructions

演算法就只是一組 用來解決問題的指令。

with which to solve problems.

演算法就只是一組 用來解決問題的指令。

These were just three.

這裡只是三個例子。

What problem would you solve with an algorithm?

而你想要用演算法解決什麼問題呢？