函数伪代码_11⾏伪代码给你讲明⽩什么是算法
算法(algorithm)就是⼀个过程，是⼀种特殊的过程。它必须描述为⼀个有限步骤序列，且必须在有限时间内结束。每个步骤必须是良好定
义的，达到⼈类可⽤⼀⽀笔和⼀张纸执⾏它的程度。
算法(algorithm)就是⼀个过程，是⼀种特殊的过程。它必须描述为⼀个有限步骤序列，且必须在有限时间内结束。每个步骤必须是良好定
义的，达到⼈类可⽤⼀⽀笔和⼀张纸执⾏它的程度。
算法基于我们提供给它的输⼊做⼀些事情，并⽣成反映其所做⼯作的⼀些输出。算法1-1实现了我们前⾯描述的过程。
算法1-1 ⼀个简单的股票跨度算法
SimpleStockSpan(quotes)→spans
输⼊: quotes，保存n个股票报价的数组
输出: spans，保存n个股票跨度的数组
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        els
算法1-1展⽰了如何描述算法。我们并不使⽤某种计算机语⾔，因为那样会迫使我们处理与算法逻辑⽆关的实现细节，我们使⽤的是某种伪
代码(pseudocode)形式。
伪代码是⼀种介于真正的程序代码和⾮形式化描述之间的形式。它使⽤⼀种结构化格式，并采⽤⼀组具有特定含义的词汇。但是，伪代码不
是真正的计算机代码。它并不是为了被计算机执⾏，⽽是易于被⼈类理解。
顺便提⼀下，程序也应能被⼈类理解，但并⾮所有程序都是如此——有很多正在运⾏的计算机程序写得很糟糕，难以理解。
每个算法都有⼀个名字，接受⼀些输⼊，并⽣成⼀些输出。在本书中，算法的名字将采⽤骆驼拼写法(CamelCase)，输⼊会写在括号中，输
出⽤⼀个→指⽰。接下来的⼏⾏将会对算法的输⼊和输出进⾏描述。可以⽤算法的名字紧接放在括号中的输⼊来调⽤(call)算法。
⼀旦算法编写好，就可以将其作为⼀个⿊盒来处理，可以给它⼀些输⼊，⿊盒则会返回算法的输出。当⽤⼀种程序设计语⾔实现⼀个算法
时，它就是⼀个具名的计算机代码⽚段——函数(function)。在⼀个计算机程序中，我们调⽤实现算法的函数。
某些算法不⽣成输出，当然也就不会显式返回结果。取⽽代之的是，它们的⾏为影响上下⽂的某部分。例如，我们可能提供给算法⼀个空
间，供其写⼊结果。在此情况下，在传统意义上算法并⾮返回输出结果，但⽆论如何算法是有输出的，即它影响上下⽂发⽣的变化。
某些程序设计语⾔会区分显式返回结果的具名程序代码⽚段——称为函数(function)，以及不返回结果但可能有其他副作⽤的具名程序代码
⽚段——称为过程(procedure)。这种差异来源于数学，数学上的函数是必须返回值的。对我们来说，当⼀个算法编码为实际程序时，既可
以是⼀个函数也可以是⼀个过程。
我们的伪代码中使⽤⼀些⽤粗体表⽰的关键字，如果你对计算机和程序设计语⾔的⼯作⽅式有所了解，这些关键字的含义就是不⾔⾃明的
了。
我们使⽤字符←表⽰赋值，⽤等号(=)表⽰相等⽐较。我们采⽤常⽤的五个符号(+，-，/，×，·)表⽰四种数学运算，后两个符号都表⽰乘
法，这两个符号我们都会使⽤，基于美学考虑进⾏选择。我们将不会使⽤任何关键字或符号对伪代码分块，分块是通过缩进来表⽰的。
在这个算法中，我们使⽤了数组(array)。数组是⼀种保存数据的结构，它允许我们按特定⽅式操纵其中的数据。我们保存数据并允许在其
怎么给数组赋值保存的数据上执⾏特定操作的结构称为数据结构(data structure)。因此数组是⼀种数据结构。
数组之于计算机，就像对象序列之于⼈类。数组是元素的有序序列，这些元素存储在计算机内存中。为了获得保存元素所需的空间并创建⼀个保存n个元素的数组，可调⽤算法1-1第1⾏中的CreateArray算法。
如果你熟悉数组，可能就会奇怪创建数组怎么还需要⼀个算法。但实际情况的确如此。为了获得保存数据的⼀块内存，你必须⾄少在计算机中搜索可⽤内存并标记它为数组所⽤。
CreateArray(n)调⽤做了所需的⼀切，它返回⼀个可容纳n个元素的数组，初始时其中没有元素，只有保存元素所需的空间。算法负责调⽤CreateArray(n)来将实际数据填充到数组中。
对数组A，我们⽤A[i]表⽰其第i个元素，访问该元素也是⽤该符号。⼀个元素在数组中的位置，如A[i]中的i，被称为索引(index)。⼀个n个元素的数组A包含元素A[0]，A[1]，…，A[n-1]。
这可能令你吃惊，因为其⾸元素是第0个，⽽尾元素是第n-1个，可能你的预期是第1个和第n个。但是，⼤多数计算机语⾔中的数组都是如此，你最好现在就熟悉这种机制。这⾮常常见，当遍历⼀个⼤⼩为n
的数组时，我们是从位置0遍历到位置n-1。
在我们的算法中，当我们说某个对象的取值是从数x到数y(假定x⼩于y)时，意思是从x到y(但不包含)的所有值，参见算法第2⾏。
我们假定⽆论i的值是什么，访问第i个元素都花费相同的时间。因此访问A[0]与访问A[n-1]需要相同的时间。这是数组的⼀个⾮常重要的特性：对元素的访问是⼀致的，都花费常量时间。当我们通过索引访问数组元素时，数组不需要搜索此元素。
关于算法描述中的符号表⽰，我们⽤⼩写字母表⽰算法中的变量。但当变量表⽰⼀个数据结构时，我们会使⽤⼤写字母来令其突出，如数组A。但这并⾮必要。当我们希望给变量起⼀个包含很多单词的名字时，我们会使⽤下划线(_)，如a_connector。这是必要的，因为计算机不理解由⼀组空格分隔的单词构成单个变量名的⽅式。
算法1-1使⽤数组保存数值。数组可以保存任何类型的项，在我们的伪代码中每个数组只能保存单⼀类型的项。⼤多数程序设计语⾔中也都是如此。
例如，可以创建⼗进制数数组、分数数组、表⽰⼈的项的数组以及另⼀个表⽰地址的项的数组，但不可以创建⼀个既包含⼗进制数⼜包含表⽰⼈的项的数组。⾄于“表⽰⼈的项”会是什么，由编程所使⽤的语⾔所决定。所有程序设计语⾔都提供表⽰有意义的东西的⽅法。
⼀种特别有⽤的数组是字符数组。⼀个字符数组表⽰⼀个字符串(string)，即⼀个字母序列、⼀个数序列、⼀个单词序列、⼀个句⼦序列等。与所有数组⼀样，我们可以⽤索引单独引⽤数组中的单个字符。如果我们有⼀个字符串s=“Hello，World”，则s[0]为字母“H”⽽s[11]为字母“d”。
总结⼀下，数组就是⼀个保存相同类型项的序列的数据结构。数组⽀持两种操作：
CreateArray(n)创建⼀个能保存n个元素的数组。数组未初始化，即它不保存任何实际元素，但保存元素所需的空间已预留，可⽤来保存元素。
正如我们已经看到的，对⼀个数组A，A[i]访问其第i个元素，⽽且访问数组中任何元素都花费相同时间。若i<0，则试图访问A[i]会产⽣错误。
我们回到算法1-1。如前所述，算法第2～10⾏是⼀个循环，即⼀个反复执⾏的代码块。如果我们有n天的报价的话，循环执⾏n次，每次计算⼀个跨度。变量i表⽰我们正在计算跨度的当前这⼀天。初始时，处于第0天这⼀最早的时间点。每次执⾏第2⾏代码时，就会推进循环到第1，2，…，n-1天。
我们使⽤变量(variable)k指⽰当前跨度的长度——在我们的伪代码中，变量就是⼀个引⽤某些数据的名字，那些数据的内容，或者更精确地说，变量的值(value)，在算法执⾏的过程中是可以改变的，变量这个术语因⽽得名。当我们开始计算⼀个跨度时，k的值总是1，我们是在第3⾏设置这个初值的。
我们还使⽤了⼀个指⽰变量(indicator variable)span_end。指⽰变量取值TRUE或FALSE，指出某事成⽴或不成⽴。当我们到达⼀个跨度的末端时，变量span_end的值将为真。
在开始计算每个跨度时，span_end为假，如第4⾏所⽰。第5～9⾏的内层循环计算跨度的长度。第5⾏告诉我们，只要跨度还未结束，就会退尽可能长的时间。我们能回退多远由条件i-k≥0决定：回退到索引i-k指⽰的这⼀天检查跨度是否结束，⽽索引不能为0，因为0对应第1天。
第6⾏检查跨度是否结束。如果跨度未结束，则在第7⾏增加其长度。否则，我们注意到，第9⾏设置跨度结束，从⽽循环会在回到第5⾏后终⽌。
第2～10⾏的外层循环在第10⾏结束⼀次循环时，我们在此将k的值保存到数组spans的正确位置。在退出循环后的第11⾏，我们返回spans，它保存着算法的结果。
注意，初始时我们设定i=0和k=1。这意味着在最早的时刻第5⾏的条件必定为假。这是理所应当的，因为第0天的跨度只能为1。
此时此刻，记住我们曾说过的关于算法、笔和纸的内容。理解⼀个算法的最好⽅法就是去⼿动执⾏它。
在任何时候如果⼀个算法看起来有些复杂，或者你不确定是否已完全理解它，就⽤纸和笔写下执⾏它求解某个例⼦的过程。这种⽅法会节省你很多时间，虽然它看起来有点⽼套。如果对算法1-1还有不明确的
地⽅，马上尝试这种⽅法，当算法已完全清晰后再回到这⾥。