3.1 我們對算法的理解

知識點講解：光盤：視頻\PPT講解（知識點）\第3章\我們對算法的理解.mp4

一個程序應包括對數據的描述。在程序中要指定數據的類型和數據的組織形式，即數據結構（data structure）。對操作的描述即操作步驟，也就是算法（algorithm）。Wirth曾經提出了一個經典的公式：數據結構+算法=程序。而根據譚浩強的總結得出：

        程序=算法+數據結構+程序設計方法+語言工具和環境

3.1.1 為什么是程序靈魂

當我重新審視自己走過的路時，我越來越能理解算法的重要性。算法不僅是工具，而且是程序的靈魂。在初涉這一領域時，就多次看過Wirth教授的《算法+數據結構=程序》。后來思想慢慢轉移到了方法論上，對OO、GP或者IoC這些知識超乎尋常地關心，卻冷落了程序的本質。很多實際問題還是要靠精心設計的算法才能有效解決。

筆者曾發現一本比較有趣的書：由Udi Manber所寫的 Introduction to Algorithms—A Creative Approach。此書的最大特點就是用數學歸納法貫穿全篇，我的理解就是“由一粒沙看世界”。復雜的問題，如何對其分解？在這本書中，不僅給出了一些具體算法，更重要的是要培養讀者的設計算法的能力。而這種能力的核心，在作者看來，就是對歸納的理解和靈活運用。

算法是計算機處理信息的本質，因為計算機程序本質上是一個算法，告訴計算機確切的步驟來執行一個指定的任務，如計算職工的薪水或打印學生的成績單。一般地，當算法在處理信息時，數據會從輸入設備讀取，寫入輸出設備，可能保存起來以供以后使用。

著名計算機科學家Wirth提出一個公式：

        數據結構+算法=程序

實際上，一個程序還應當采用結構化程序設計方法進行程序設計，并且用某一種計算機語言表示。因此，可以這樣表示：

        程序=算法+數據結構+程序設計方法+語言和環境

以上4個方面是一門程序設計語言所應具備的基本知識。在這4個方面中，算法是靈魂，數據結構是加工對象，語言是工具。算法是解決“做什么”和“怎么做”的問題。

程序中的操作語句，實際上就是算法的體現。顯然，不了解算法就談不上程序設計。本書雖然不是專門講算法的，但不會算法就達不到我們的目的——用C語言進行程序設計。

數據是操作對象，對操作的描述即是操作步驟，操作的目的是對數據進行加工處理得到期望的結果。打個比方，廚師做菜肴，需要有菜譜。菜譜上一般應包括：

（1）配料（數據）；

（2）操作步驟（算法）。

這樣，面對同一些原料就可以加工出不同風味的菜肴。

3.1.2 何謂算法

做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。計算機能夠執行的算法稱為計算機算法。計算機算法可分為如下兩大類。

? 數值運算算法：求解數值。

? 非數值運算算法：事務管理領域。

看下面的運算：

1×2×3×4×5

為了計算上述運算，通常需要按照如下步驟來計算。

第1步：先求1×2，得到結果2。

第2步：將步驟1得到的乘積2乘以3，得到結果6。

第3步：將6再乘以4，得24。

第4步：將24再乘以5，得120。

上述過程就是一個算法，雖然過程有點復雜。而在計算機程序中，對上述算法進行了改進，使用如下算法。

第1步：使t=1。

第2步：使i=2。

第3步：使t×i，乘積仍然放在變量t中，可表示為t×i→t。

第4步：使i的值+1，即i+1→i。

第5步：如果i≤5，返回重新執行步驟3以及其后的步驟4和步驟5；否則，算法結束。

上述算法方式就是數學中的“n! ”公式。

看下面的數學應用題：

（1）有80個學生，要求將他們之中成績在60分以上者打印出來。

在此設n表示學生學號，ni表示第i個學生學號；cheng表示學生成績，chengi表示第i個學生成績。則對應算法表示如下。

第1步：1→i。

第2步：如果chengi≥60，則打印ni和chengi，否則不打印。

第3步：i+1→i。

第4步：若i≤80，返回步驟2，否則，結束。

（2）判定1900～2000年中的那一年是閏年，將結果輸出。

閏年需要滿足的條件如下。

① 能被4整除，但不能被100整除的年份。

② 能被100整除，又能被400整除的年份。

在此可以設y為被檢測的年份，則對應算法如下。

第1步：1900→y。

第2步：若y不能被4整除，則輸出y“不是閏年”，然后轉到第6步。

第3步：若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉到第6步。

第4步：若y能被100整除，又能被400整除，輸出y“是閏年”，否則輸出y“不是閏年”，然后轉到第6步。

第5步：輸出y“不是閏年”。

第6步：y+1→y。

第7步：當y≤2000時，返回第2步繼續執行，否則，結束。

3.1.3 算法的特性

對于程序設計人員來說，必須會設計算法，并根據算法寫出程序。算法的特性如下所示。

? 有窮性，一個算法應包含有限的操作步驟而不能是無限的。

? 確定性，算法中每一個步驟應當是確定的，而不能是含糊的、模棱兩可的。

? 有零個或多個輸入。

? 有一個或多個輸出。

? 有效性，算法中每一個步驟應當能有效地執行，并得到確定的結果。