維基少年:少兒程式設計/編寫演算法

維基少年：少兒程式設計
自上而下還是自下而上？	編寫演算法	變數和資料型別

你可能對演算法有所瞭解。它是計算機用來做某件事的東西。究竟是什麼事呢？

什麼是演算法？

演算法是一系列逐步執行的程式，用於執行計算或處理資料。演算法獨立於程式語言。這意味著演算法可以轉換為任何程式語言。在編寫演算法時，我們無需考慮我們選擇的語言特有的元素。以下是一個描述如何玩石頭剪刀布遊戲的演算法，你需要在三局中贏得兩局

步驟 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

表示式可以是變數或常量。它可以包含運算子，也可以不包含運算子。接下來，我們將進入下一章… 變數和資料型別！