11行伪代码告诉你什么是算法 某些程序设计语言会区分显式返回结果的具名

关于作者：帕诺斯·卢里达斯(Panos Louridas)，曼彻斯特大学软件工程博士，现为雅典经济与商业大学管理科学与技术系副教授。在加入高校之前，曾在投资银行担任高级软件工程师。

在任何时候如果一个算法看起来有些复杂，或者你不确定是否已完全理解它，就用纸和笔写下执行它求解某个例子的过程。这种方法会节省你很多时间，虽然它看起来有点老套。如果对算法1-1还有不明确的地方，马上尝试这种方法，当算法已完全清晰后再回到这里。

此时此刻，记住我们曾说过的关于算法、笔和纸的内容。理解一个算法的最好方法就是去手动执行它。

注意，初始时我们设定i=0和k=1。这意味着在最早的时刻第5行的条件必定为假。这是理所应当的，因为第0天的跨度只能为1。

第2～10行的外层循环在第10行结束一次循环时，我们在此将k的值保存到数组spans的正确位置。在退出循环后的第11行，我们返回spans，它保存着算法的结果。

第6行检查跨度是否结束。如果跨度未结束，则在第7行增加其长度。否则，我们注意到，第9行设置跨度结束，从而循环会在回到第5行后终止。

在开始计算每个跨度时，span_end为假，如第4行所示。第5～9行的内层循环计算跨度的长度。第5行告诉我们，只要跨度还未结束，就回退尽可能长的时间。我们能回退多远由条件i-k≥0决定：回退到索引i-k指示的这一天检查跨度是否结束，而索引不能为0，因为0对应第1天。

我们还使用了一个指示变量(indicator variable)span_end。指示变量取值TRUE或FALSE，指出某事成立或不成立。当我们到达一个跨度的末端时，变量span_end的值将为真。

我们使用变量(variable)k指示当前跨度的长度——在我们的伪代码中，变量就是一个引用某些数据的名字，那些数据的内容，或者更精确地说，变量的值(value)，在算法执行的过程中是可以改变的，变量这个术语因而得名。当我们开始计算一个跨度时，k的值总是1，我们是在第3行设置这个初值的。

CreateArray(n)创建一个能保存n个元素的数组。数组未初始化，即它不保存任何实际元素，但保存元素所需的空间已预留，可用来保存元素。
正如我们已经看到的，对一个数组A，A[i]访问其第i个元素，而且访问数组中任何元素都花费相同时间。若i<0，则试图访问A[i]会产生错误。
我们回到算法1-1。如前所述，算法第2～10行是一个循环，即一个反复执行的代码块。如果我们有n天的报价的话，循环执行n次，每次计算一个跨度。变量i表示我们正在计算跨度的当前这一天。初始时，处于第0天这一最早的时间点。每次执行第2行代码时，就会推进循环到第1，2，…，n-1天。

总结一下，数组就是一个保存相同类型项的序列的数据结构。数组支持两种操作：

一种特别有用的数组是字符数组。一个字符数组表示一个字符串(string)，即一个字母序列、一个数序列、一个单词序列、一个句子序列等。与所有数组一样，我们可以用索引单独引用数组中的单个字符。如果我们有一个字符串s=“Hello，World”，则s[0]为字母“H”而s[11]为字母“d”。

例如，可以创建十进制数数组、分数数组、表示人的项的数组以及另一个表示地址的项的数组，但不可以创建一个既包含十进制数又包含表示人的项的数组。至于“表示人的项”会是什么，由编程所使用的语言所决定。所有程序设计语言都提供表示有意义的东西的方法。

算法1-1使用数组保存数值。数组可以保存任何类型的项，在我们的伪代码中每个数组只能保存单一类型的项。大多数程序设计语言中也都是如此。

关于算法描述中的符号表示，我们用小写字母表示算法中的变量。但当变量表示一个数据结构时，我们会使用大写字母来令其突出，如数组A。但这并非必要。当我们希望给变量起一个包含很多单词的名字时，我们会使用下划线(_)，如a_connector。这是必要的，因为计算机不理解由一组空格分隔的单词构成单个变量名的方式。

我们假定无论i的值是什么，访问第i个元素都花费相同的时间。因此访问A[0]与访问A[n-1]需要相同的时间。这是数组的一个非常重要的特性：对元素的访问是一致的，都花费常量时间。当我们通过索引访问数组元素时，数组不需要搜索此元素。

在我们的算法中，当我们说某个对象的取值是从数x到数y(假定x小于y)时，意思是从x到y(但不包含)的所有值，参见算法第2行。

这可能令你吃惊，因为其首元素是第0个，而尾元素是第n-1个，可能你的预期是第1个和第n个。但是，大多数计算机语言中的数组都是如此，你最好现在就熟悉这种机制。这非常常见，当遍历一个大小为n的数组时，我们是从位置0遍历到位置n-1。

对数组A，我们用A[i]表示其第i个元素，访问该元素也是用该符号。一个元素在数组中的位置，如A[i]中的i，被称为索引(index)。一个n个元素的数组A包含元素A[0]，A[1]，…，A[n-1]。

CreateArray(n)调用做了所需的一切，它返回一个可容纳n个元素的数组，初始时其中没有元素，只有保存元素所需的空间。算法负责调用CreateArray(n)来将实际数据填充到数组中。

如果你熟悉数组，可能就会奇怪创建数组怎么还需要一个算法。但实际情况的确如此。为了获得保存数据的一块内存，你必须至少在计算机中搜索可用内存并标记它为数组所用。

数组之于计算机，就像对象序列之于人类。数组是元素的有序序列，这些元素存储在计算机内存中。为了获得保存元素所需的空间并创建一个保存n个元素的数组，可调用算法1-1第1行中的CreateArray算法。

在这个算法中，我们使用了数组(array)。数组是一种保存数据的结构，它允许我们按特定方式操纵其中的数据。我们保存数据并允许在其保存的数据上执行特定操作的结构称为数据结构(data structure)。因此数组是一种数据结构。

我们使用字符←表示赋值，用等号(=)表示相等比较。我们采用常用的五个符号(+，-，/，×，·)表示四种数学运算，后两个符号都表示乘法，这两个符号我们都会使用，基于美学考虑进行选择。我们将不会使用任何关键字或符号对伪代码分块，分块是通过缩进来表示的。

我们的伪代码中使用一些用粗体表示的关键字，如果你对计算机和程序设计语言的工作方式有所了解，这些关键字的含义就是不言自明的了。

某些程序设计语言会区分显式返回结果的具名程序代码片段——称为函数(function)，以及不返回结果但可能有其他副作用的具名程序代码片段——称为过程(procedure)。这种差异来源于数学，数学上的函数是必须返回值的。对我们来说，当一个算法编码为实际程序时，既可以是一个函数也可以是一个过程。

某些算法不生成输出，当然也就不会显式返回结果。取而代之的是，它们的行为影响上下文的某部分。例如，我们可能提供给算法一个空间，供其写入结果。在此情况下，在传统意义上算法并非返回输出结果，但无论如何算法是有输出的，即它影响上下文发生的变化。

一旦算法编写好，就可以将其作为一个黑盒来处理，可以给它一些输入，黑盒则会返回算法的输出。当用一种程序设计语言实现一个算法时，它就是一个具名的计算机代码片段——函数(function)。在一个计算机程序中，我们调用实现算法的函数。

每个算法都有一个名字，接受一些输入，并生成一些输出。在本书中，算法的名字将采用骆驼拼写法(CamelCase)，输入会写在括号中，输出用一个→指示。接下来的几行将会对算法的输入和输出进行描述。可以用算法的名字紧接放在括号中的输入来调用(call)算法。

顺便提一下，程序也应能被人类理解，但并非所有程序都是如此——有很多正在运行的计算机程序写得很糟糕，难以理解。

伪代码是一种介于真正的程序代码和非形式化描述之间的形式。它使用一种结构化格式，并采用一组具有特定含义的词汇。但是，伪代码不是真正的计算机代码。它并不是为了被计算机执行，而是易于被人类理解。

算法1-1展示了如何描述算法。我们并不使用某种计算机语言，因为那样会迫使我们处理与算法逻辑无关的实现细节，我们使用的是某种伪代码(pseudocode)形式。

spans←CreateArray(n) for i←0 to n do     k←1     span_end ← FALSE     while i-k ≥ 0 and not span_end do        if quotes[i-k] ≤ quotes[i] then            k←k+1        else            span_end ← TRUE     spans[i] ← k return spans 

输入: quotes,保存n个股票报价的数组
输出: spans,保存n个股票跨度的数组

SimpleStockSpan(quotes)→spans

算法基于我们提供给它的输入做一些事情，并生成反映其所做工作的一些输出。算法1-1实现了我们前面描述的过程。

算法(algorithm)就是一个过程，是一种特殊的过程。它必须描述为一个有限步骤序列，且必须在有限时间内结束。每个步骤必须是良好定义的，达到人类可用一支笔和一张纸执行它的程度。