11行伪代码告诉你:什么是真正的算法?

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

算法1-1一个简单的股票跨度算法

SimpleStockSpan(quotes)→spans

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

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

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

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

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

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

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

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

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

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

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

数组之于计算机,就像对象序列之于人类。数组是元素的有序序列,这些元素存储在计算机内存中。为了获得保存元素所需的空间并创建一个保存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行。

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

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

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

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

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

CreateArray(n)创建一个能保存n个元素的数组。数组未初始化,即它不保存任何实际元素,但保存元素所需的空间已预留,可用来保存元素。

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

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

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

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

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

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

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

THE END
1.有哪些经典的人工智能算法?算法流程图和伪代码 为了使大家更好地理解,这边给出作者算法的流程图和伪代码,非常清晰!如果实在看不https://www.zhihu.com/question/38648973/answer/3600888761
2.KNN算法的伪代码51CTO博客已为您找到关于KNN算法的伪代码的相关内容,包含IT学习相关文档代码介绍、相关教程视频课程,以及KNN算法的伪代码问答内容。更多KNN算法的伪代码相关解答可以来51CTO博客参与分享和学习,帮助广大IT技术人实现成长和进步。https://blog.51cto.com/topic/c7b29299701394b.html
3.1.c语言:用伪代码表示算法卷积神经网络(Convolutional Neural Network,CNN)是深度学习中的一个核心技术,通过对输入数据进行卷积操作,提取特征,从而实现分类或回归等任务。本文将围绕卷积神经网络,探讨如何使用伪代码表示算法。 卷积神经网络的伪代码表示 卷积神经网络(CNN)主要包括以下几个部分:输入层、卷积层、池化层、全连接层和输出层。下面我们https://developer.aliyun.com/article/1457673
4.基于网络社区发现的标签传播聚类算法2.5 算法伪代码 根据以上定义, 本文算法分为4个步骤: 首先对数据集进行网络化; 之后, 利用节点相似度对节点标签进行预处理, 以提高后续标签传播的稳定性; 在标签传播阶段, 用节点影响力辅助标签选择, 进一步降低标签传播的随机性; 最后, 通过对社区的内聚度进行判断, 对内聚度较小的社区进行合并优化, 以提高https://c-s-a.org.cn/html/2020/12/7712.html
5.算法用模拟退火(SA,SimulatedAnnealing)算法解决旅行商问题2.4 模拟退火算法伪代码 相信通过上面的讲解,大家已经对模拟退火算法认识得差不多了。下面我们来看看它的伪代码是怎么实现的。 03 使用模拟退火算法解决旅行商问题 旅行商问题属于所谓的NP完全问题。精确的解决TSP只能通过穷举所有的路径组合,其时间复杂度是O(N!) 。而使用模拟退火算法则可以较快速算法一条近似的最https://cloud.tencent.com/developer/article/1424760
6.什么是伪代码?如何编写伪代码?C#伪代码是一种用于描述算法或程序逻辑的近似代码表示形式,它并不是一种特定的编程语言,而是一种高级描述工具。伪代码使用类似于编程语言的结构和语法,但更加简洁和易于理解。它的目的是帮助程序员和其他相关人员理解算法或程序的逻辑流程,而不用拘泥于具体的编程语言细节。 https://download.csdn.net/blog/column/12416302/133873748
7.伪代码是什么?如何写一个伪代码?野牛程序员伪代码是一种近似于编程语言的描述工具,用于描述算法或程序的逻辑结构,而不依赖于具体的编程语言语法。它的目的是帮助程序员以一种简洁易懂的方式表达算法的思想,而不必关注具体的语法细节。 编写伪代码的主要目标是清晰地传达算法的思路,使其他人能够理解你的算法设计。以下是一些编写伪代码的基本准则: http://yncoders.com/show/1179
8.科学网—模拟退火算法求最优解(转载)补充:模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。 三、模拟退火算法的代码实现 1)伪代码: while(T > T_min) https://blog.sciencenet.cn/blog-1813407-893984.html
9.MapReduce求解物流配送单源最短路径研究AET(5)如果每次Reduce后,结果收敛,则停止计算;如果未收敛,则继续发给下一轮的Map过程,多次迭代计算直到color值全部为2,得到最终的最短路径,算法结束。 MapReduce算法流程如图1所示。 1.3 MapReduce算法伪代码 (1)MapReduce的第一次迭代伪代码,Map部分为: http://www.chinaaet.com/article/218820
10.ID3决策树以及Python实现详细过程python二、决策树学习算法伪代码: 决策树的生成是一个递归的过程,在决策树基本算法中,有三种情形会导致递归返回: 当前结点包含的样本全属于同一类别,无需划分;当前属性集为空,或是所有样本在所有属性上取值相同,无法划分;当前结点包含的样本集合为空,不能划分; https://www.jb51.net/python/311079kt3.htm
11.TCP是怎样工作的PDF下载Java知识分享网本书理论与实践相结合,在详细讲解TCP原理后,还引领读者搭建模拟环境,使用Wireshark和ns-3等工具模拟TCP的运行机制,观察拥塞控制算法的执行,并辅以伪代码,帮助读者全面理解TCP技术。 资料目录: 第1章 TCP入门 确保传输可靠性 1 1.1 通信与协议 OSI参考模型、TCP/IP和RFC 2 OSI参考模型 2 TCP/IP 10 分层模型下http://www.java1234.com/a/javabook/javabase/2024/0329/25034.html
12.伪代码伪代码是不用于机器解释的程序代码,仅用于说明范例或算法。它主要类似于混合了自然语言和数学符号的高级编程语言。使用伪代码,可以独立于底层技术来描述程序流程。因此,它通常比真正的程序代码更紧凑、更容易理解。另一方面,它比自然语言的描述更正式,因此更清晰,也更https://vibaike.com/371954/
13.面向DTN感染路由协议的缓存管理算法表1MPBBM算法参数表 MPBBM算法在替换消息时,依据每条消息的MPBBM值进行降序排序,该算法认为优先级高的消息为活跃消息,而优先级低的消息为非活跃消息,因此排序的结果为活跃度依次降低的消息队列。表 2为MPBBM算法优先替换非活跃消息的算法伪代码。 表2MPBBM算法伪代码 https://www.juestc.uestc.edu.cn/fileDZKJDX_ZKB/journal/article/dzkjdxxbzrkxb/2015/3/HTML/201544403.htm