“Template: 伪代码”的版本间的差异

来自计算思维百科
跳转至: 导航搜索
(创建页面,内容为“算法最终是要用程序设计语言实现并在计算机上执行的。自然语言描述和流程图描述很难直接转化为程序,现有计算机程序设...”)
 
第47行: 第47行:
 
(16) 最后,以上标准只是建议,而目的是能够清晰准确地表达算法。
 
(16) 最后,以上标准只是建议,而目的是能够清晰准确地表达算法。
  
欧几里得 算法的伪代码 描述如下:
+
'''例 '''给出计算10! 算法的伪代码
  
''' 算法3.2 ''''''欧几里得 算法'''
+
'''算法 '''计算10!
 
 
'''Input:''' 正整数m、n
 
 
 
'''Output:''' m、n的最大公约数
 
 
 
'''GREATEST-COMMON-DIVISOR(m''''''、''''''n)'''
 
 
 
1    REPEAT                  
 
 
 
2        r ß m mod n      
 
 
 
3        m ß n
 
 
 
4        n ß r
 
 
 
5    UNTIL  r=0       
 
 
 
6    RETURN  m           
 
 
 
'''例3.1''' 给出计算10!算法的伪代码。
 
 
 
'''算法3.3''' 计算10!
 
  
 
'''Output:'''10!
 
'''Output:'''10!

2015年10月14日 (三) 13:58的版本

算法最终是要用程序设计语言实现并在计算机上执行的。自然语言描述和流程图描述很难直接转化为程序,现有计算机程序设计语言又多达几千种,不同的语言在设计思想、语法功能和适用范围等方面都有很大差异。此外,用程序设计语言表达算法往往需要考虑所用语言的具体细节,分散了算法设计者的注意力。因此,用某种特定的程序设计语言描述算法也是不太可行的。伪代码描述正是在这种情况下产生的。

一般来说,伪代码是一种与程序设计语言相似但更简单易学的用于表达算法的语言。程序表达算法的目的是在计算机上执行,而伪代码表达算法的目的是给人看的。'伪代码('Pseudocode)应该易于阅读,简单和结构清晰,它是介于自然语言和程序设计语言之间的。伪代码不拘泥于程序设计语言的具体语法和实现细节。程序设计语言中一些与算法表达关系不大的部分往往被伪代码省略了,比如变量定义和系统有关代码等。程序设计语言中的一些函数调用或者处理简单任务的代码块在伪代码中往往可以用一句自然语言代替。例如“找出3个数中最小的那个数”。

由于伪代码在语法结构上的随意性,目前并不存在一个通用的伪代码语法标准。作者们往往以具体的高级程序设计语言为基础,简化后进行伪代码的编写。最常见的这类高级程序设计语言包括C、Pascal、Fortran、BASIC、Java、Lisp和ALGOL等。由此而产生的伪代码往往被称为“类C语言”、“类Pascal语言”或“类ALGOL语言”等等。

经典算法设计教科书《算法导论》的作者Thomas H. Cormen提出的伪代码格式标准是最广为接受的伪代码标准之一,著名的排版软件Latex也提供了按照Cormen的标准的伪代码格式化库。本书采用的伪代码标准与Cormen的标准基本一致:

  1. 每个算法都描述为一个函数,函数的名字用大写字母表示,单词间用横线相连。算法的输入应以参数表的形式在函数名后面给出。必要的时候在算法前面对输入输出进行描述。例如:

       Input: 正整数m、n

Output: m、n的最大公约数

   GREATEST-COMMON-DIVISOR(m、n)

  1.  用“ß”表示赋值;支持重赋值语句,如ißjße等同于jße,iße;
  2. 在伪代码中,每一条指令占一行,指令后不跟任何符号;
  3.  给函数名以后的每行编号;
  4. 变量名和保留字不区分大小写,建议变量名用小写,保留字和常量用大写,以方便区分;
  5.  用缩进表示代码块结构,包括WHILE,FOR循环、IF-THEN-ELSE分支判断等;
  6. "//"标志表示注释的开始,一直到行尾(Cormen的标准是用▹符号,考虑到该符号输入不方便,故采用C++和Java都支持的“//”);
  7. while,for,repeat循环语句和if,then,else条件语句的语法与Pascal语言相似。但是在for语句结束之后,循环变量保持循环结束时候的值;例如:

1    FOR i=1 TO 10

2       PRINT i                 //依次输出1、2、…、10

3    PRINT i                    //输出11        

  1.  缺省情况下,变量都是局部变量。使用全局变量必须显式说明;

(10) 访问数组元素使用:数组名[序号]。“‥”标记表示数组中一组值的序号范围。如A[1‥j]表示A[1], A[2],…, A[j];

(11) 复合数据用对象来组织,对象由属性组成。一个特定的属性要用“属性名[对象名]”来访问。如:我们把一个数组A视为一个对象,那么要描述数组元素个数要用length[A]。代表数组或对象的变量被视为指向数组或对象所包含的数据的指针;

(12) 传入算法的简单类型的参数都是按值传递的,也就是说,在算法中操作的是传入参数在算法内部的拷贝,其在算法外部的变量不受影响。但是,对于对象类型的变量,传入的参数是对象指针的拷贝;

 例如,如果算法的参数是一个简单的数字类型x,则在算法开始时会建立一个x的本地拷贝,类似于算法的局部变量,操作x←3只会影响x的本地拷贝,而不会影 响算法外部的x的值。但是,如果算法的参数是一个数组A,在算法开始的时候会建立一个A的本地拷贝B。由于A和B实际上都是数组的指针,所以A[3]和B[3]都代表了存在于算法以外的该数组的第3个元素,所以如果在算法中执行:A[3] ←5,虽然实际上执行的是B[3] ←5 (因为B是A的本科拷贝),但是存在于算法之外的该数组的第3个元素还是被改成了5。

(13) 布尔操作 and 和 or 都是先计算左边操作数的值,然后按照需要计算右边操作数的值。例如,对于X and Y,会计算X的值,如果X是FALSE,则无论如何X and Y的值都是FALSE,所以Y的值就不会计算了;

(14) 不需要定义的函数调用或者简单的任务块可以用一行自然语言表达;

(15) 返回用RETURN

(16) 最后,以上标准只是建议,而目的是能够清晰准确地表达算法。

例 给出计算10!算法的伪代码。

算法 计算10!

Output:10!

FACTOR-10

1   sum ß 0

2   FOR j ß 2 TO 10

3       DO sum ß sum * j

4   RETURN sum

综上所述,伪代码是一种用类似于程序的文本来表达算法的方式。它比一般的程序设计语言简单易学,使算法设计者可以把注意力集中在设计算法而不是具体程序设计语言的语法细节上。用伪代码表达的算法容易翻译成程序,因此,伪代码往往出现在程序的注释中。需要强调的是,伪代码没有统一的格式标准,前面介绍的标准只是建议性的,只要能够简洁完整地表达算法就可以了。伪代码在算法描述中是使用得非常多的一种工具。