初識C語言之演算法設計篇——帶你走進編程世界的小院！-有解無憂

演算法

什么是演算法？

演算法的特點

演算法的歷史

演算法的描述

自然語言案例

流程圖

3種基本結構

N-S流程圖

演算法舉例

每文一語

演算法

什么是演算法？

演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出，如果一個演算法有缺陷，或不適合于某個問題，執行這個演算法將不會解決這個問題，不同的演算法可能用不同的時間、空間或效率來完成同樣的任務，一個演算法的優劣可以用空間復雜度與時間復雜度來衡量，

演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出并停止于一個終態，一個狀態到另一個狀態的轉移不一定是確定的，隨機化演算法在內的一些演算法，包含了一些隨機輸入，

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，并在其后嘗試定義有效計算性或者有效方法中成形，這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別于1930年、1934年和1935年提出的遞回函式，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機，即使在當前，依然常有直覺想法難以定義為形式化演算法的情況，

演算法的特點

有窮性

確切性

輸入項

輸出項

可行性

一、資料物件的運算和操作：

計算機可以執行的基本操作是以指令的形式描述的，一個計算機系統能執行的所有指令的集合，成為該計算機系統的指令系統，一個計算機的基本運算和操作有如下四類：

1.算術運算：加減乘除等運算

2.邏輯運算：或、且、非等運算

3.關系運算：大于、小于、等于、不等于等運算

4.資料傳輸：輸入、輸出、賦值等運算 [1]

二、演算法的控制結構：

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

演算法的歷史

“演算法”即演演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自于9世紀波斯數學家al-Khwarizmi，因為al-Khwarizmi在數學上提出了演算法這個概念，“演算法”原為"algorism"，意思是阿拉伯數字的運演算法則，在18世紀演變為"algorithm"，歐幾里得演算法被人們認為是史上第一個演算法，第一次撰寫程式是Ada Byron于1842年為巴貝奇分析機撰寫求解伯努利方程的程式，因此Ada Byron被大多數人認為是世界上第一位程式員，因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行，因為"well-defined procedure"缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義演算法上出現了困難，20世紀的英國數學家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機，圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要作用，

演算法的描述

自然語言案例

自然語言就是人們日常用的語言，這種表示方式通俗易懂，下面通過實體具體介紹，

【實體2.1】求n！，

（1）定義3個變數i、n及mul，并為i和mul均賦初值為1，

（2）從鍵盤中輸入一個數賦給n，

（3）將mul乘以i的結果賦給mul，

（4）i的值加1，判斷i的值是否大于n，如果大于n，則執行步驟（5），否則執行步驟（3），

（5）將mul的結果輸出，

【實體2.2】任意輸入3個數，求這3個數中的最小數，

（1）定義4個變數分別為x、y、z以及min，

（2）輸入大小不同的3個數分別賦給x、y、z，

（3）判斷x是否小于y，如果小于，則將x的值賦給min，否則將y的值賦給min，

（4）判斷min是否小于z，如果小于，則執行步驟（5），否則將z的值賦給min，

（5）將min的值輸出，

流程圖

流程圖是一種傳統的演算法表示法，它用一些圖框來代表各種不同性質的操作，用流程線來指示演算法的執行方向，由于它直觀形象，易于理解，所以應用廣泛，特別是在語言發展的早期階段，只有通過流程圖才能簡明地表述演算法，

【實體2.3】 從鍵盤中輸入3個數分別賦給a、b、c，要求按大小順序把它們列印出來，流程圖如圖所示

3種基本結構

Bohra和Jacopini為了提高演算法的質量，經研究提出了3種基本結構，即順序結構、選擇結構和回圈結構，因為任何一個演算法都可由這3種基本結構組成，這3種基本結構之間可以并列，可以相互包含，但不允許交叉，不允許從一個結構直接轉到另一個結構的內部去，

整個演算法都是由3種基本結構組成的，所以只要規定好3種基本結構的流程圖的畫法，就可以畫出任何演算法的流程圖，

順序結構是簡單的線性結構，在順序結構的程式里，各操作是按照它們出現的先后順序執行的，如圖所示，

在執行完A框所指定的操作后，接著執行B框所指定的操作，這個結構里只有一個入口點A和一個出口點B，

【實體2.4】輸入兩個數分別賦給變數i和j，再將這兩個數分別輸出，

本實體流程圖可以采用順序結構來實作，如圖所示，

選擇結構也叫分支結構，如圖所示

選擇結構中必須包含一個判斷框，圖中所代表的含義是根據給定的條件p是否成立選擇執行A框或者是B框，

下圖所代表的含義是根據給定的條件P進行判斷，如果條件成立則執行A框，否則什么也不做，

在回圈結構中，反復地執行一系列操作，直到條件不成立時才終止回圈，按照判斷條件出現的位置，可將回圈結構分為當型回圈結構和直到型回圈結構，

當型回圈是先判斷條件P是否成立，如果成立，則執行A框；執行完A框后，再判斷條件P是否成立，如果成立，接著再執行A框；如此反復，直到條件P不成立為止，此時不執行A框，跳出回圈，

直到型回圈是先執行A框，然后判斷條件P是否成立，如果條件P成立則再執行A；然后判斷條件P是否成立，如果成立，接著再執行A框；如此反復，直到條件P不成立，此時不執行A框，跳出回圈，

N-S流程圖

N-S圖是另一種演算法表示法，是由美國人I.Nassi和B.Shneiderman共同提出的，其根據是：既然任何演算法都是由前面介紹的3種結構組成，則各基本結構之間的流程線就是多余的，因此去掉了所有的流程線，將全部的演算法寫在一個矩形框內，N-S圖也是演算法的一種結構化描述方法，同樣也有3種基本結構，下面分別進行介紹：

順序結構的N-S流程圖