什么是算法？ - David J. Malan：英语精读讲义

What's an 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 zero. 短語動詞

从零开始数。

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 zero. 語法

让 n 等于零。

For each person in room, 語法

对于房间里的每个人，

set n = n + 1. 用詞

设置 n = n + 1。

How to interpret this pseudocode? 表達脈絡

如何理解这段伪代码呢？

Well, line one declares, so to speak, 講解

嗯，可以这么说，第一行声明了

a variable called n and initializes its value to zero.

一个名为 n 的变量，并将其值初始化为零。

This just means that at the beginning of our algorithm,

这只是意味着在我们的算法开始时，

the thing with which we're counting has a value of zero. 語法

我们用来计数的东西的值为零。

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 two demarks the start of a 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 two is line three,

第二行下面是第三行，

which describes exactly how we'll go about counting.

它确切地描述了我们将如何进行计数。

The indentation implies that it's line three that will repeat. 用詞

缩进意味着要重复的是第三行。

So, what the pseudocode is saying is that after starting at zero, 講解

所以，伪代码的意思是，在从零开始之后，

for each person in the room, we'll increase n by one. 短語搭配

针对房间里的每个人，我们会把 n 增加一。

Now, is this algorithm correct?

那么，这个算法正确吗？

Well, let's bang on it a bit. 習語

让我们来测试一下。

Does it work if there are two people in the room? 語法

如果房间里有两个人，它能行得通吗？

Let's see.

让我们来看看。

In line one, we initialize n to zero.

在第一行，我们将 n 初始化为零。

For each of these two people, we then increment n by one. 用詞

对于这两个人中的每一个，我们将 n 加一。

So, on the first trip through the loop, we update n from zero to one. 習語

所以，在第一次循环时，我们将 n 从零更新为一。

On the second trip through that same loop, we update n from one to two.

在第二次同一次循环中，我们将 n 从一更新为二。

And so, by this algorithm's end, 短語搭配

这样，当这个算法结束时，

n is two, which indeed matches the number of people in the room. 表達脈絡

n 就是二，这确实与房间里的人数相符。

So far, so good. 習語

到目前为止，一切顺利。

How about a corner case though? 用詞

但是遇到极端情况会怎样呢？

Suppose that there are zero people in the room, 語法

假设房间里有零个人，

besides me, who's doing the counting.

除了正在计数的我。

In line one, we again initialize n to zero.

在第一行，我们再次将 n 初始化为零。

This time though, line three doesn't execute at all, 用詞

然而这一次，第三行根本没有执行，

since there isn't a person in the room,

因为房间里没有其他人，

and so n remains zero,

所以 n 仍然是零，

which indeed matches the number of people in the room.

这确实与房间里的人数相符。

Pretty simple, right? 語氣意圖

非常简单，对吧？

But counting people one at 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 等于零。

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 is thus twice as fast as the last. 語法

因此这个算法比上一个快两倍。

But is it correct?

但它正确吗？

Let's see.

让我们来看看。

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

如果房间里有两个人，它行得通吗？

In line one, we initialize n to zero.

在第一行，我们将 n 初始化为零。

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

对于那一对人，我们将 n 增加二。

And so, by this algorithm's end,

这样，在这个算法结束时，

n is two, which indeed matches the number of people in the room.

n 就是二，这确实与房间里的人数相符。

Suppose next that there are zero people in the room.

接下来假设房间里有零个人。

In line one, we initialize n to zero.

在第一行，我们将 n 初始化为零。

As before, line three doesn't execute at all, 表達脈絡

像之前一样，第三行根本没有执行，

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

因为房间里没有任何成对的人，

and so n remains zero,

所以 n 仍然是零，

which indeed matches the number of people in the room.

这确实与房间里的人数相符。

But what if there are three people in the room? 語法

但是如果房间里有三个人呢？

How does this algorithm fair?

这个算法表现如何？

Let's see.

让我们来看看。

In line one, we initialize n to zero.

在第一行，我们将 n 初始化为零。

For a pair of those people, we then increment n by two.

对于这些人中的一对，我们将 n 加二。

But then what? 表達脈絡

但是接下来呢？

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

房间里没有另外完整的一对人了，

so line two no longer applies. 短語搭配

所以第二行不再适用。

And so, by this algorithm's end,

这样，在这个算法结束时，

n is still two, which isn't correct.

n 仍然是二，这是不正确的。

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 等于零。

For each pair of people in room,

对于房间里的一对人，

set n = n + 2.

设置 n = n + 2。

If one person remains unpaired,

如果有个人落单，

set n = n + 1.

设置 n = n + 1。

To solve this particular problem,

为了解决这个特定的问题，

we've introduced in line four a condition, 用詞

我们在第四行引入了一个条件，

otherwise known as a branch,

也被称为分支，

that only executes if there's one person we could not pair with another. 語法

只有当有一个人无法与别人配对时才会执行。

And so now,

这样一来，

whether there's one or three or any odd number of people in the room, 語法

无论房间里有一个人、三个人还是任何奇数个人，

this algorithm will now count them.

这个算法现在都能将他们数出来了。

Can we do even better?

还能做得更好吗？

Well, we could count in threes or fours or even fives and tens, 短語搭配

嗯，我们可以一次数三个、四个，甚至五个、十个，

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? 語氣意圖

你会用算法解决什么问题呢？