1.1 算法概述

1.1.1 什么是算法

算法研究是計算機科學的主要任務之一。利用計算機解決一個實際問題時，首先是選擇一個合適的數學模型表示問題，以便抽象出問題的本質特征，其次就是尋找一種算法，作為問題的一種解法。那么什么是算法，算法有什么基本特征，算法的組成有哪些？

1. 算法的定義

算法是解題方案的準確而完整的描述，也就是解題的方法和步驟。下面舉兩個例子來說明算法。

例1.1　有10道數學應用題的作業，必須一道題、一道題地解答，解答每道題的過程是相同的：看題→思考→解答，然后驗算檢查有無錯誤，若沒錯就做下一道題；若有錯，就重做。直到10道題都解答完，這次作業才算完成。解題的方法和步驟如圖1-1所示。

一個學生做任何作業都可以按這個“算法”執行，每次執行都產生相應的結果，這個算法的執行者是人而不是機器。

例1.2　求任意兩個整數m和n（0<m<n）的最大公約數，稱為歐幾里德算法，記為gcd(m, n)。

作為例子，這里用了三種方法來解決這一問題，用以闡明算法概念的以下幾個要點。

（1）算法的每一個步驟都必須清晰、明確。

（2）算法所處理的輸入的值域必須仔細定義。

（3）同樣一種算法可以用幾種不同的形式來描述。

（4）可能存在幾種解決相同問題的算法。

（5）針對同一個問題的算法可能會基于完全不同的解題思路，而且解題速度也會有顯著不同。

【程序1-1】歐幾里德遞歸算法。

void swap(int &a, int &b)
    { int c;
      c=a; a=b; b=c;
    }
int rgcd(int m, int n)
    { if(m==0) return n;
      return rgcd(n%m, m);
    }
int gcd(int m, int n)
    { if (m>n) swap(m, n);
      return rgcd(m, n);
    }

【程序1-2】歐幾里德迭代算法。

int gcd(int m, int n)
    { if (m==0) return n;
      if (n==0) return m;
      if (m>n) swap(m, n);
      while(m>0)
          { int c=n%m; n=m; m=c; }
      return n;
    }

【程序1-3】gcd的連續整數檢測算法。

int gcd(int m, int n)
    { int t ;
      if (m==0) return n;
      if (n==0) return m;
      int t=m>n?n:m;
      while (m%t || n%t) t--;
      return t;
    }

計算機科學中討論的算法是由計算機來執行的，也可由人模擬它用筆和紙執行。算法中最低層的操作是對用存儲器實現的變量進行賦值，這樣整個算法就是一個信息變換器，對任意一組給定的輸入值，產生一組唯一確定的輸出結果值。

對算法（Algorithm）一詞給出精確的定義是很難的。算法是用計算機解決某一類特定問題的一組規則的有窮集合，或者說是對特定問題求解步驟的一種描述，它是指令的有限序列。

也可以說，算法是將輸入轉化為輸出的一系列計算步驟，它取某些數值或數值的集合作為輸入，并產生某些值或值的集合作為輸出。因此，算法是將輸入轉化為輸出的一系列計算步驟。計算機科學中，算法已經逐漸成了用計算機解決問題的精確、有效方法的代名詞。

簡而言之，算法就是有效求出問題的解，對問題的求解過程進行精確的描述。那么一個算法應該具有哪些基本特征呢？

2. 算法的特征

算法通常具有以下幾個特征。

（1）輸入（Input）

一個算法可以有零個或多個輸入。這些輸入是在算法開始之前給出的量，它們取自于特定對象的集合，通常體現為算法中的一組變量。如【程序1-1】中有兩個輸入m、n。當然，有些算法也可以沒有輸入，如求10以內素數的算法。

（2）輸出（Output）

一個算法必須具有一個或多個輸出，以反映算法對輸入數據加工后的結果。這些輸出是同輸入有某種特定關系的量，實際上是輸入的某種函數。不同取值的輸入，產生不同的輸出結果。沒有輸出的算法是沒有意義的。如【程序1-1】中的輸出是輸入m、n的最大公約數。

（3）確定性（Definiteness）

確定性指算法中的每一個步驟都必須是有明確定義的，必須是足夠清楚的、無二義性的，不允許有模棱兩可的解釋，確定性保證了以同樣的輸入多次執行一個算法時，必定產生相同的結果，否則一定是執行者出了差錯。例如，b=2a，多次輸入a=2，b一定為4。如【程序1-1】中的兩個輸入m、n一定是從正整數集合中抽取的。

（4）可行性（Effectiveness）

算法中所有的操作都必須足夠基本，使算法的執行者或閱讀者明確其含義以及如何執行。它們可以通過已經實現的基本運算執行有限次數來實現；每種運算至少在原理上均能由人用紙和筆在有限的時間內完成。如“增加變量x的值”或“把x和y的最大公因子賦給z”都不夠明確，前者不知增加多少，后者不知如何去操作。

（5）有窮性（Finiteness）

算法的有窮性是指算法必須總能在執行有限步驟之后終止，且每一步的時間也是有限的。如果一個算法需要執行千萬年，顯然就失去了實用價值。如【程序1-1】對輸入的任意正整數m、n，再把m除以n的余數賦值給n，從而使n值變小，如此重復進行，最終使n=0，算法終止。再如1除以3等于0.3333…，如果規定保留小數點第幾位后，按照四舍五入的方法計算，就可以確定一個值，而不是無窮計算下去。

3. 算法的基本要素

一個算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是算法的控制結構。

（1）對數據對象的運算和操作

在一般的計算機系統中，基本的運算和操作有如下四類。

① 算術運算：主要包括加、減、乘、除等運算。

② 邏輯運算：主要包括與、或、非等運算。

③ 關系運算：主要包括大于、小于、等于、不等于等運算。

④ 數據傳輸：主要包括賦值、輸入、輸出等操作。

（2）算法的控制結構

一個算法的功能不僅取決于選用的操作，而且還與各操作之間的執行順序有關，算法中各操作之間的執行順序稱為算法的控制結構。

一個算法一般都可以用順序、選擇、循環（當型循環或直到型循環）三種控制結構組成。如例1.1中，“看題→思考→解答”是順序執行，“驗算檢查”對錯是選擇控制結構，對就繼續執行，錯則重做是循環控制結構。

4. 算法的描述工具

描述算法可以有多種方式。

（1）自然語言

自然語言就是人們日常使用的語言，可以是漢語、英語或其他語言。自然語言描述方法就是直接將設計者完成任務的思維過程用其母語描述下來。用自然語言描述算法非常接近人類的思維習慣，是一種非形式描述方法。初學者可以首先使用這種方法描述完成任務的步驟，然后再轉換成其他描述。

（2）流程圖

流程圖是用規定的圖形、流程線、文字說明表示算法的方法，是一種圖形方式的描述手段。流程圖可以清晰地描述出完成解題任務的方法及步驟，它是使用最早的算法描述工具。它的優點是非常直觀。

（3）N-S流程圖

N-S流程圖是1973年提出的一種新的流程圖形式，其名稱來源于提出它的兩位英國學者I. Nassi和B. Shneiderman。N-S流程圖也是圖形方式的描述手段，N-S流程圖簡稱N-S圖。

在N-S圖中去掉了容易引起麻煩的流程線，不允許隨意使用轉移控制，全部算法都寫在一個框內，框內還可以包含其他框。這種流程圖適用于結構化程序設計，能清楚地顯示出程序的結構，是一種結構化的流程圖。

N-S圖的優點是簡潔，但當嵌套層數太多時，內層的方框將越畫越小，從而會影響圖形的清晰度。

（4）偽代碼

偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法，是一種描述語言。它不用圖形符號，因此比較緊湊、簡潔，也比較好懂，與程序語言的形式非常接近，也容易轉化為高級語言程序，是常用的算法描述方法。

偽代碼只是一種描述程序執行過程的工具，是一種在程序設計過程中表達想法的非正式的符號系統，是面向讀者的，不能直接用于計算機，實際使用時還需轉換成某種計算機語言來表示。

無論采用何種算法描述方式，若最終要在計算機中執行，都需要轉換為相應的計算機語言程序。

5. 算法與程序和數據結構的關系

（1）算法與程序

算法的概念與程序（Program）十分相似，但也有很大的不同。

算法代表了對特定問題的求解，算法是行為的說明，是一組邏輯步驟。而計算機程序則是算法用某種程序設計語言的表述，是算法在計算機上的具體實現。執行一個程序就是執行一個用計算機語言表述的算法。因此算法也常常被稱為一個可行的過程。

算法在描述上一般使用半形式化的語言，而程序是用形式化的計算機語言描述的，是使用一些特殊編程語言表達的算法。算法對問題求解過程的描述可以比用程序描述粗略些，算法經過細化以后可以得到計算機程序。

一個算法可以用不同的編程語言編寫出不同的程序，但它們遵循的邏輯步驟是相同的，它們都表達同樣的算法，它們不是同樣的程序。例如，對于同一個菜肴的制作步驟，可以分別使用英語、法語和日語寫成。這是不同的三個菜譜，但是它們都表達同一個操作步驟。

程序并不都滿足算法所要求的特征，例如，“操作系統”是一個在無限循環中執行的程序，不具備“有窮性”的特征，因而“操作系統”是一種程序而不是一個算法。

（2）算法與數據結構

不了解施加于數據上的算法就無法決定如何構造數據，可以說算法是數據結構的靈魂；相反地，算法的結構和選擇又常常在很大程度上依賴于數據結構，數據結構則是算法的基礎。算法與數據結構是密不可分的，二者缺一不可。因此有人說：“算法＋數據結構＝程序”。

1.1.2 學習算法的重要性

算法是計算機科學的基礎，更是程序的基石，只有具有良好的算法基礎才能成為訓練有素的軟件人才。對計算機類專業的學生來說，學習算法是十分必要的。因為你必須知道來自不同計算領域的重要算法，你也必須學會設計新的算法、確認其正確性并分析其效率。

隨著計算機應用的日益普及，各個應用領域的研究人員和技術人員都在使用計算機求解他們各自專業領域的問題，他們需要設計算法、編寫程序、開發應用軟件，所以學習算法對于越來越多的人來說變得十分必要。

計算機的操作系統、語言編譯系統、數據庫管理系統以及各種各樣的計算機應用軟件，都要用具體的算法來實現。因此算法設計與分析是計算機科學與技術的一個核心問題，也是一門重要的專業基礎課程。

通過對算法設計與分析這門課程的學習，讀者就能掌握算法設計與分析的方法，再利用這些方法去解決軟件開發中所遇到的各種問題，去設計相應的算法，并對所設計的算法做出科學的評價。無論是計算機專業技術人員，還是使用計算機的其他專業技術人員，算法設計與分析都是非常重要的。