「第7節」算法的基礎知識（一）

大家好，本節穿插一段小插曲，讓大家瞭解、熟悉下算法方面的基礎知識，進一步讓大家在今後的程序編寫中，有所悟、有所得。學會算法，我們就可以是程序設計師，而不僅僅是程序員了！

一、什麼是算法？

在計算機編程中，一個程序由算法和數據結構2部分組成。數據結構表示程序中用到的數據以及數據類型和數據的組織形式。關於數據結構，以後會詳細講解。

至於算法，簡單來講，就是要求計算機進行操作的步驟。而且，並不是只有“計算”的問題才是算法。再通俗些說，為了解決某個問題而採取的方法、步驟、思路等就統稱為“算法”。通過算法，可以將輸入迅速轉化為輸出。

範例：

判斷1999-2348年中的每一年是否為閏年，並將結果輸出。

分析講解：首先，我們得了解什麼是閏年以及閏年需要滿足什麼樣的條件。

簡單來講，一年中有366天或者說2月份有29天的那年就稱為閏年。閏年必須滿足下列2個條件中的1個：（1）年份能被4整除，但不能被100整除；（2）年份能被400整除。

於是，本範例的算法步驟可表示如下：

第1步：1999→year，把首個年份1999賦值給year

第2步：如果year不能被4整除，則輸出year的值和“不是閏年”。然後跳到第6步，檢查下一個年份

第3步：如果year能被4整除，不能被100整除，則輸出year的值和“是閏年”。然後跳到第6步

第4步：如果year能被400整除，輸出year的值和“是閏年”。然後跳到第6步

第5步：輸出year的值和“不是閏年”

第6步：year+1→year，把下1個年份賦值給year

第7步：當year≤2348時，跳到第2步繼續執行，否則算法終止

這個算法用流程圖可表示成如下：

大家可以自己思考思考這個算法的妙處！

二、算法的特點

根據上面所述，我們知道，算法是用來解決實際問題的。不能用來解決實際問題的，就不能被稱為“算法”。要想讓設計出來的算法能夠解決好實際問題，就得符合以下3個特點：

1、有窮性。也就是涉及出來的算法是能夠得出結果的，是能夠結束的。如果一個算法是無休止地運行下去的，那麼該算法就毫無意義可言的了。而且，算法在能夠停止的同時，必須步驟有限度，如果步驟超出了計算機能夠承載的範圍，這樣也是不行的。

2、確定性。也就是算法設計的每一個步驟都具有明確的指令，能夠讓計算機清清楚楚地知道該幹嘛，1是1,2是2，明明確確，不能有任何含糊不清的情況，這樣計算機才能將算法執行下去。

3、有效性。正如前面所言，算法必須是能夠解決實際問題的，是能夠得出結果的。要想讓算法能夠解決實際問題，一方面，必須要有有效的輸入，就是要讓計算機能夠得到所需要的信息；另一方面，必須要有有效的輸出，就是能夠得到想要的結果信息。

三、算法的分類

常用的算法設計技術有查找、搜索、排序、迭代、遞推、遞歸、貪心、分治、動態規劃、回溯等。其中，查找、排序、遞歸、貪心等算法是最為重要的，需要重點掌握好！

關於查找算法，又可主要細分成線性查找、二分查找等2種。關於排序算法可細分成冒泡排序、堆排序、歸併排序、快速排序、基數排序、插入排序、選擇排序等等很多種。

二分查找算法示例

冒泡排序算法示例

關於查找、排序等常用的、實用的算法，我將在之後的章節裡繼續深入講解。