维基少年:少儿编程/编写算法

维基少年：少儿编程
自上而下还是自下而上？	编写算法	变量和数据类型

你可能对算法有所了解。它是计算机用来做某件事的东西。究竟是什么事呢？

什么是算法？

算法是一系列逐步执行的程序，用于执行计算或处理数据。算法独立于编程语言。这意味着算法可以转换为任何编程语言。在编写算法时，我们无需考虑我们选择的语言特有的元素。以下是一个描述如何玩石头剪刀布游戏的算法，你需要在三局中赢得两局

步骤 1：两个人都从以下选项中选择一个：石头、剪刀、布
步骤 2：如果两个选择相同，则重复步骤 1
步骤 3：如果两个选择不同
- 步骤 3.1：如果第一人选择剪刀，第二人选择布，则第一人得一分
- 步骤 3.2：如果第一人选择剪刀，第二人选择石头，则第二人得一分
- 步骤 3.3：如果第一人选择布，第二人选择剪刀，则第二人得一分
- 步骤 3.4：如果第一人选择布，第二人选择石头，则第一人得一分
- 步骤 3.5：如果第一人选择石头，第二人选择剪刀，则第一人得一分
- 步骤 3.6：如果第一人选择石头，第二人选择布，则第二人得一分
- 步骤 3.7：重复步骤 1 到 3，直到一个人获得两分

然而，上面的算法并没有以标准的方式表示。表示算法主要有两种方法：流程图和伪代码。

流程图

流程图以图形方式表示算法。在绘制流程图时，我们必须遵循一组标准规则。不要被这些描述吓倒：我们将在接下来的几章中逐一介绍它们。

符号	名称	描述
	算法开始	“开始”符号看起来像我们在前几章中见过的体育场。它表示算法的开始。算法中的所有内容最终都来自这个符号。
	输入语句/ 输出语句	输入语句从另一个文件读取或从用户接收输入。输出语句将信息输出到屏幕上。输入语句并不总是位于算法的开头，输出语句也不总是位于结尾。
	赋值语句	赋值语句将值赋给变量。
	过程调用	此符号“调用”一个预定义的过程或函数。
	条件/ 决策	条件表示算法中的“分支”，通常是“是”和“否”。到达条件组件后，传入路径会分成两条独立的路径。
	算法结束	“结束”符号的使用与“开始”符号类似。所有代码的“分支”最终都必须指向结束。

当然，我们不能只用一堆方框来制作一个流程图。我们还需要表示它们之间的流程。为此，我们使用箭头和连接器。

符号	名称	描述
	箭头	箭头从一个方框指向另一个方框，以表示方框之间的流程。它们被条件方框“分割”。
	连接器	如果箭头具有分支路径，则它们必须先汇聚在一起才能执行任何共同操作。连接器用于实现此目的。连接器通常被省略，只留下一个交叉点。

以下是一些示例


连接器帮助将分叉的箭头汇聚在一起。	它们有时被省略，但汇聚点仍然存在。	在先将它们汇聚在一起之前，我们不能将两条路径都指向同一个方框！这是错误的！

伪代码

伪代码是以叙述性方式表示算法的非正式方法。伪代码没有标准，但有一些我们可以遵循的既定约定。这包括关键字，它们通常大写，以及缩进等格式化功能。以下是一个伪代码示例

10 READ i, j
20 IF i < j THEN
30    PRINT 'i is the smaller one.'
40 ELSE
50    PRINT 'j is the smaller one.'
60 ENDIF

与流程图和一般算法一样，伪代码独立于编程语言。没有人会真正将其通过编译器。因此，如果需要，我们可以使用英语语句

PROGRAM find_square_area
10 READ width
20 IF width is a positive integer THEN
30    PRINT width * width
40 ELSE
50    PRINT 'Invalid input!'
60 ENDIF

上面的代码等效于以下代码

PROGRAM find_square_area
10 READ width
20 IF (width > 0) AND (width MOD 2 = 0) THEN
30    PRINT width * width
40 ELSE
50    PRINT 'Invalid input!'
60 ENDIF

如果你不理解这些算法，不要害怕；我们会稍后学习它们。

行号通常包含在伪代码中，以便于参考。它们每次增加 10。

编程范式和编程语言

编程范式是编程语言遵循的一种模式。目前存在许多不同的编程范式。其中一种称为声明式编程。在声明式编程中，命令被逐个写入并执行，没有流程图中的任何“分支”。命令以顺序方式呈现。查询语言和电子表格是很好的示例。以下是一个SQL的示例，SQL 是一种众所周知的查询语言

CREATE DATABASE Books;
CREATE TABLE FavouriteBooks(
   BookID CHAR(6) NOT NULL UNIQUE,
   BookTitle VARCHAR(100) NOT NULL,
   BookAuthorFirst VARCHAR(30),
   BookAuthorLast VARCHAR(30),
   BookPublisher VARCHAR(30),
   PRIMARY KEY(BookID)
)
INSERT INTO FavouriteBooks(BookID, BookTitle, BookAuthorFirst, BookAuthorLast) VALUES('000006', 'Pride and Prejudice', 'Jane', 'Austen');
INSERT INTO FavouriteBooks(BookID, BookTitle, BookAuthorFirst, BookAuthorLast) VALUES('000006', 'A Christmas Carol', 'Charles', 'Dickens');
INSERT INTO FavouriteBooks(BookID, BookTitle, BookAuthorFirst, BookAuthorLast) VALUES('000006', 'Animal Farm', 'George', 'Orwell');
SELECT * FROM FavouriteBooks WHERE BookAuthorFirst = 'Jane';

声明式编程与命令式编程形成对比，在命令式编程中，我们使用控制流告诉计算机执行一系列操作。与从“开始”到“结束”的单箭头不同，我们可以“分叉”箭头，并让它们返回到之前的方框。Goto曾经是描述控制流的常用方法，我们可以从代码中的一个位置“跳转”到另一个位置。然而，goto 已经开始减少，并被结构化编程所取代。结构化编程使用顺序、迭代和选择来描述程序的流程。我们将在后面的章节中详细学习这三种结构。过程式编程扩展了结构化编程，并允许我们将程序划分为称为过程、子程序或函数的多个模块。过程式编程有利于模块化和自上而下的方法。


声明式编程	结构化编程	过程式编程

过程式编程在面向对象编程中得到了进一步扩展，在面向对象编程中，程序由具有不同属性并执行不同方法的“对象”组成。主要有两种类型。在原型编程中，每个对象都有一个原型（例如，一本空白书）。原型定义了对象的属性和方法。然后，我们克隆该对象，并获得不同的成熟对象（例如，一本包含大量文本和图表、附有精装封面的厚书）。基于类的编程采用了不同的方法。在基于类的编程中，对象类型在类中定义。如果我们要向该类添加更多属性和方法，可以扩展该类。在这两种情况下，要创建新对象，我们需要调用其构造函数。以下是在 JavaScript 中的一个原型

var Book = function(title, pages, coverType) {
      this.title = title;
      this.pages = new Array(pages);
      this.cover = new Cover(coverType);
};

Book.prototype = {
   cover: new Cover();
   pages: new Array(1);
   title: "";
   currentPage: 0;

   flip: function(){
      try{
         if(currentPage >= pages.length - 1){
            throw "No more flipping!";
         }
         currentPage++;
      } catch (e){
         alert(e);
      }
   }
}

package {
   public class Book{
      public var cover:Cover;
      public var pages:Array;
      public var title:String;
 
      private var currentPage:uint;

      public function Book(title:String,
                           pages:uint, coverType:uint){
         this.title = title;
         this.pages = new Array(pages);
         this.cover = new Cover(coverType);
      }

      public function flip(){
         try{
            if(currentPage >= pages.length - 1){
               throw "No more flipping!";
            }
            currentPage++;
         } catch (e:Error){
            trace(e);
         }
      }
   }
}

JavaScript 中的原型

ActionScript 中的类定义

一些编程语言只支持一种范式。例如，Java 是一种纯粹的基于类的面向对象语言。JavaScript 是一种基于原型的语言。其他语言则支持多种范式。例如，ActionScript 可以是过程式的、基于类的，也可以是两者的混合。

方言是另一种编程语言的扩展，它与原始语言非常相似。JavaScript（最初为 Netscape 开发）、JScript（Internet Explorer）和 ActionScript 都是ECMAScript的方言，ECMAScript 是一种最初为 JavaScript 和 JScript 创建的标准。BASIC是一种为初学者设计的简单编程语言，后来扩展为各种方言，包括Visual Basic。最值得注意的是，C++和C#是 C 的常见方言，与 C 不同的是，它们支持许多不同的编程范式。

以下是分别用 JavaScript、ActionScript 和 PHP 编写的三个代码片段。请注意 JavaScript 和 ActionScript 之间的相似性。

var numberOfItems = 10;
var fibonnaci = new Array();
fibonnaci[0] = 1;
document.writeln(fibonnaci[0]);
fibonnaci[1] = 1;
document.writeln(fibonnaci[1]);
for(var i = 2; i < numberOfItems; i++){
   fibonnaci[i] = fibonnaci[i-1]
   + fibonnaci[i-2];
   document.writeln(fibonnaci[i]);
}

var numberOfItems:uint = 10;
var fibonnaci:Array = new Array();
fibonnaci[0] = 1;
trace(fibonnaci[0]);
fibonnaci[1] = 1;
trace(fibonnaci[1]);
for(var i:uint = 2; i < numberOfItems; i++){
   fibonnaci[i] = fibonnaci[i-1]
   + fibonnaci[i-2];
   trace(fibonnaci[i]);
}

$numberOfItems = 10;
$fibonnaci = array();
$fibonnaci[0] = 1;
echo (string) $fibonnaci[0]."<br/>";
$fibonnaci[1] = 1;
echo (string) $fibonnaci[1]."<br/>";
for($i = 2; $i < $numberOfItems; $i++){
   $fibonnaci[$i] = $fibonnaci[$i-1]
   + $fibonnaci[$i-2];
   echo (string) $fibonnaci[$i]."<br/>";
}

JavaScript

ActionScript

PHP

语句和表达式

语句指示计算机执行一个动作。它们类似于英语中的祈使句，例如吃蛋糕！睡觉！刷牙！擦黑板！这些都是伪代码中语句的例子。

Input x
Output y
Put x into y
Call brushTeeth

表达式则略有不同。表达式具有一个值。它们本身无法执行任何操作。

x
3
6+8
1/2
4.5 + y * 3

表达式可以是变量或常量。它可以包含运算符，也可以不包含运算符。接下来，我们将进入下一章… 变量和数据类型！